12493
144043348 186536063 458481139 511430893 336883404 84031729 179787448 210283707 587464605 578376740 781267866 200929765 844259511 458569405 124405974 410390270 337560005 300185624 282617847 185094811 424958558 309846275 616264142 602034800 614327541 793929761 508711799 158460014 839229814 955573944 923192534 676915543 883219471 105581037 125188193 715342216 821918999 99267765 828830107 836665611 57371049 578202782 716365466 764209271 13383099 436245564 951348980 126717389 308942095 1664707 697462426 248305726 117847017 798673561 112602546 532984748 568173338 312923789 434013934 446235781 179104973 891460748 172854584 929227769 963951232 666625341 742829094 607307167 667781397 372066193 53586620 45068266 634017675 215926100 900638382 828097639 87157932 473160825 202845156 400431361 462380867 654424220 556733530 189297954 791618477 743448511 463768224 197965403 426141549 999183739 93340653 97451380 325643080 493816353 897613027 516788381 456651324 422488829 52911149 931782497 179500622 261978765 176573250 815822586 347770071 309832641 40988944 115685567 222075539 258000251 128481196 35475402 661344834 348241836 329380973 113562240 740930979 791458037 708540630 653872158 952659248 280436522 721864651 49949103 145453239 607989393 313981495 525093078 349094521 810390828 191101004 202835112 238044870 543721553 111430296 480351001 779786810 313062532 269784348 260363244 672898953 348613008 478918939 520920766 734529311 294716946 73619288 458495430 340020346 105688512 624463446 327735722 974481883 500616503 813388568 719795513 882679124 519553155 718709439 534780983 408545905 434113674 764625854 485038064 963741680 646579188 691528253 694996698 311616184 453322972 390897786 311187772 762636415 77277662 299443716 536095599 730333235 172846728 250883570 977525336 108295182 432531297 880479015 232757752 459759826 421265311 462980749 86383376 21069693 739841189 917847184 548383498 509539300 548026988 233592277 557788672 555901616 281642158 143441619 263684023 448572980 265957430 812585241 373061713 3683197 574546822 196225162 169959442 352931752 847091338 441978541 807411061 916593574 807889277 741693594 255268058 482223735 344409587 738527983 732297399 158516010 725762770 275487721 267038370 842580536 805069156 724732305 807198116 68180734 300350495 354851726 212652138 273567245 104148697 659139785 408582573 787784910 797912081 43662693 432205553 696167038 813126661 568711595 411031692 857879750 663424233 144153516 361976852 979115755 846612329 720098849 740358608 741515430 371294152 395932062 380662125 241204953 533823073 490799200 45991173 957001249 601305665 798534376 521782177 398390049 973966185 411523403 93913658 365897891 184750650 680469418 647112039 702795343 422134760 73363654 961288276 684644465 522343703 541570800 771588735 924354025 764821866 293100996 279552865 929141845 196699754 228479316 796612992 599065618 719491358 972111333 423532916 250899064 791143708 53427792 571599462 480174751 703613840 838024879 111414481 146175977 185703049 419560323 67664528 228371065 147351121 981998002 762056335 843814332 204364392 462701919 840932520 642524606 418166536 622317494 326488512 689448287 514589027 630928340 185376013 210153706 651878900 395228599 855171380 2375841 114959718 154965639 425345407 44155506 363677286 916005817 130163419 129262058 793564214 115526455 933425477 506691928 352965177 170944966 936188203 813909116 222943466 505120205 843627770 211259022 537863409 115125154 35763572 542854941 603507544 994904296 53775911 958043316 967760060 382489579 756538120 251240417 155288929 211058883 246059459 500181754 494114964 825446269 762994427 501850441 729439589 880267927 101453473 393633732 424356711 812594816 301181454 477187746 880932408 870225253 163955533 59327411 796464992 606883905 119853520 725327124 479726416 24381704 283231969 665056094 317376659 211222543 219007930 505873361 459753878 168657999 116048370 366177518 125700317 978227465 68041287 286569189 354134679 450754584 655280427 36128394 643857880 544157767 305307203 367155593 105681047 265590473 227358126 735074539 628733997 553040002 996070680 29488277 47171323 125509122 443792014 44010559 378274369 615356848 613140386 652388148 783831154 926820993 990611942 446789867 580236975 118263441 256239432 756056304 552138213 232021684 571592305 528170553 58888737 259525800 367370708 343866658 311941012 841162881 275447764 600180140 918907960 90106486 885163905 425086465 794388558 493073698 816108084 591999991 748865952 536697106 173233618 9234859 319143954 717898047 366562374 962511434 329180402 920224819 544529677 422756641 268592703 855173404 25413067 318141544 274998948 825805143 659148073 859695439 549788862 348514668 702829951 840705321 662377594 491328323 807813616 646936091 425524059 814670464 141936094 108041898 904695197 208400955 658970521 30850062 146046568 663992596 442425467 111116002 641870033 154118278 99955026 783969875 330257966 716023123 851467191 472185448 641159758 563191346 761632469 856608819 767690150 108410817 67375368 180347133 178129744 802424864 818446403 893204299 326165580 170536425 473873232 747321772 799069023 379345294 911951750 429452614 422997451 445457969 685736454 898192628 806737688 236927542 816679036 786669355 243103079 559158657 877636226 430242712 788576827 365012453 31864252 800786020 90654988 274777891 705015617 11788939 909795009 637207912 539787327 704362796 716226870 902577362 468297540 973382306 217652186 274941693 854050783 594001681 2398485 87677943 234313990 334045001 264751545 635672158 596815147 995136995 548265927 188641915 711332564 5726509 286139812 234721851 651492098 559743655 973151396 227858420 907012670 321518 978827878 340226853 841448926 390992421 723427052 500667223 459562663 133597961 102778208 131534906 325422040 625272618 475430928 927435080 850121505 741944802 25715488 51605038 101870708 687732948 308471434 959735020 832791179 218372214 456632503 63816228 60841147 838850752 368926508 200098308 312977646 985721816 316684849 745880541 135367452 80001227 674189542 40138097 285554516 919224941 781806690 454331977 605060995 444119236 717434441 694571297 680580339 210083735 4302992 92922075 774924789 845749929 107409679 81516153 829388679 359979587 158276668 644956650 762121548 334788114 547633496 464757508 847860082 970463982 338698060 323386171 631441747 968253265 401227415 396196413 752955535 226302089 789376393 773162264 748513416 719726610 172327091 354011799 725792407 373448058 772627919 880330136 278698436 519492774 959621013 757591115 144719991 495090522 623832987 254269828 640838237 927526971 624466763 602667997 152914420 855438442 756770600 565886128 985705252 91374512 952015187 956260355 319040188 565447235 16304805 29045116 949554886 629294179 996253119 416119440 618902017 252870561 553794861 15388982 904600758 896485446 711471167 618374575 162796574 18993598 87094834 517185241 42322285 455472336 722900954 483618190 937326986 371708937 715976801 89781327 517626015 148551578 561306392 618069190 447774857 917644154 313132627 859876900 810529893 992453293 948721032 710267679 584469454 56598781 698401611 452551491 276014203 704936012 21824653 326577155 880068751 428279403 74909916 576363989 355290948 378987728 282805384 75172308 192569494 897527114 497429950 167192056 90861782 803620751 575965166 560939423 256051721 905466411 720906562 100309319 224159043 618032455 837481892 242929359 580872950 726422085 427125441 846582227 898988143 85623038 899672256 931758983 427655936 85765481 521491709 662139504 408565076 541416588 621572843 104315146 175178524 670825180 386922972 555416518 169001345 101236513 657137115 979013891 820019217 719478312 321579183 223633422 67870521 305207096 544892694 578027766 14636100 559088498 758093296 389913225 726508786 893158709 799728463 926573648 684388524 411839500 359686681 375873708 61500753 961375542 310669568 319096769 371506112 403803155 984843198 333380371 230877168 298581977 380675637 708942135 494562847 264212427 420522950 9234536 157037007 848926185 301081699 846601955 2915832 399842329 114077972 722599436 367150414 627112307 650552315 411627045 818044164 382039843 418607079 207589260 939690617 699912961 702220099 27545154 851394032 461943757 475663281 834940537 641672855 846755644 620656597 513217428 112228125 826187481 815545160 263904282 770431644 648813060 649243061 668250071 405544482 726573241 796971473 349515803 22642678 939922514 408444438 526444775 857944835 543117320 83211667 847692277 529366634 565339840 317878925 657745682 562123787 714607425 952634791 643604209 381499725 112961442 235780813 957022645 313373265 692659944 541429813 274918816 303993367 542311806 321594296 52459750 279734967 406519224 973852143 536651770 451701956 817118826 305733367 190471004 380592862 319911691 872125040 199644283 955834841 555821948 543008695 328945837 14752634 85332486 527188238 700613322 544822948 254246697 62204676 888687605 604504579 909866467 781001729 193524213 823618910 713086087 189241667 164839949 989618715 553676530 288316036 546525168 52853246 150269483 562392525 409517340 615324961 606148669 606576387 542621014 172803100 23898394 20964490 682217276 91047282 130273964 254197989 645174986 319706790 827268015 679754969 27372108 263306707 744148417 95484345 525487819 91335487 702648577 557722145 125204638 787352425 451963269 595310236 146968797 307740355 678101991 894123819 710319657 274770099 383708714 47405540 864322419 299046169 828752685 461966880 938503582 797051956 992974 485663313 468503945 387324017 874790264 384234262 594534500 455606208 208153673 604083998 130732706 588365201 76892846 377836257 391516843 649085670 313176866 666618318 408172890 35133042 554039585 968837746 501457628 746383445 320713088 915194429 992893958 691923734 464956116 321272931 807728936 314346943 298373758 265375098 756008781 448565738 953117129 804477132 745590827 858136821 569521796 19987032 782907299 302163923 495925983 518649977 233105412 610051801 346345291 161902093 684596529 710639691 357055057 437851561 535273171 602926613 322159088 533357344 133763706 858188036 363437881 556650482 232569799 440441107 519003925 16137841 830168333 649346408 318248490 686310238 981756808 507237312 5523346 567127234 922307352 692918996 864684690 764643425 618082662 610266612 258677900 759167755 372558434 514080172 506362663 909730737 864413304 345654023 202892706 174956009 3039684 631300924 928084645 992921213 128435183 114243151 184619974 103551313 630630258 673981036 582652415 861751601 870149638 370304147 490438462 792948927 59255119 581709249 698678626 100000069 619540009 569744898 657025967 856946873 157466337 963368090 448140530 815430089 883340487 700626580 195418727 447806118 80849251 664999090 242038714 615803332 335930111 108829371 508041708 99576328 118366305 769456440 423341900 541673252 289723780 871004166 539360975 270385778 223759777 114245060 696070045 655028504 473366540 822165451 869666877 175238495 619393810 621705935 971215628 111594496 269613539 901613005 71991960 748770195 29481640 622572105 401389569 689880598 926800137 360623641 611486213 308378245 458260724 853030048 767426395 729701456 404575925 862211057 578154931 998184511 884734308 273581467 20214758 995175737 569153780 143228532 84139509 799404588 963005416 206907075 956737025 858936791 446715192 227159020 684603961 739764466 689406387 681255071 492687126 415024327 682468344 501652706 995683524 935991299 944945398 686401156 134861066 157492773 95612800 823370664 439535913 974956967 319265588 712657049 566552014 46044195 641608600 152444413 372350634 710759989 298598458 136612725 430455159 688778183 842918373 897526003 739210163 4957846 531471106 698376105 999145141 721357469 754706652 123876503 949059494 700142110 194826449 574425289 16937162 411259736 775881773 963361514 160177690 815472829 858373361 29337242 671669562 959178440 515297982 543964719 744163956 175308229 527733181 298882572 746803697 994760737 693941248 646475827 300732663 342162235 713570707 665780480 960086303 901023323 152505958 193079371 102377951 882375988 197547087 702164388 185860467 208182818 236081737 920159427 640794563 149038690 415370505 38460982 886307117 805347517 963231390 171252989 126438189 383556117 611348080 485569993 589706101 327686529 404260658 271132087 278991100 257531982 756147365 672991032 413011793 21926644 422237926 111390528 232663656 99756656 792183594 950236864 622324665 50722051 659931866 925015860 195977216 735350351 470371955 239193265 919622726 13919604 363299683 171809709 35337874 554995127 257749009 633325779 615176352 626832378 418856583 321704812 229179443 567361196 466047914 314396508 446600595 787526899 815910807 483902053 224853724 131479492 17368862 302665261 590639881 533406798 595632149 975920395 996201096 443572710 15765741 815112469 384238826 55805807 56018520 906028337 876895237 498959880 734819232 10111999 488336499 408064724 72769749 636641178 870106413 876861330 701600511 518039812 340300194 635505214 203603911 418829103 869917423 266606596 911086634 803235027 638860205 993348584 728109152 807674005 740744799 36149247 213266598 430503845 448543138 354873701 401158934 808815062 563117719 53032543 160176779 781517576 184313151 588206782 97675990 201466409 258654744 125316155 802255499 630194873 559108432 758924251 745017871 138804783 864957653 655461303 938597071 108566764 720000927 170100319 276113479 902273975 43747146 349843894 397657145 497569249 592454743 123296324 924342439 889848745 617102631 160912220 655386150 793821 832724217 216860345 295030877 280346883 461390369 628393 227947430 293282355 862116516 695541208 767342398 424254754 775154461 937732194 89917547 915277603 350109763 339934425 802193817 928094039 997780609 441269018 345047959 492837091 395267767 988352170 128807628 784690877 485880052 401505415 103555584 345138767 467679761 643318356 858980295 671682031 93137968 512130479 750013205 984302307 532651243 691796297 938175012 219349954 943382802 957467776 835384890 837654599 903474785 689691415 245076670 149225076 848304432 751018252 800085650 163750402 399966119 866667760 588014285 139403911 693624305 903891881 398832795 20051368 948340277 261169637 278711423 574184254 704321590 706437372 648936880 476845737 734856712 482168145 813315625 79791249 234960352 329316253 799067842 154630744 954569014 756345532 569097862 393334912 426950673 957914695 210081239 405117347 765759148 987342777 101092198 43995364 837694920 119448585 322154872 467683423 291635697 250667456 9897057 595401801 799660872 551864124 673202333 875087079 482928337 604921732 577892151 823094058 806674945 670596830 411186897 644308196 67095915 772568565 533896222 69766959 120803322 63127635 244243756 595582663 840741316 52451275 95977423 413538780 566719480 296156333 700726919 641360349 779723264 295107127 577203403 617691321 100223622 81151235 87701192 693954051 118208786 57116461 847197826 476160022 810705050 734559594 684213780 776873462 855110210 147387979 891386476 504292088 675619752 299213065 460510636 873122426 65756703 593659856 805219634 687244438 173725427 368223654 244875780 85761472 599680263 231576244 423875680 819586865 817251219 640229310 395877144 810209549 503842164 7028832 289518045 710790187 147975597 38898511 83774700 417952592 812680908 714116129 156187626 221966861 20808565 491741357 283711232 237219764 433717435 951630900 64942589 770209955 115107485 670984290 821957018 768006014 640255203 911617954 191402510 594205430 42055762 55428866 596594129 245893972 898942599 457688120 695977351 962385822 250200495 198822875 553509571 210417349 761006280 406745709 723177306 364668751 166601607 447151004 721333586 797528339 552680805 788989527 809690185 719529003 637913575 465883209 962962618 806283679 895448097 727597377 344330424 772322758 377769953 196295473 661080168 138843416 326766771 313168032 850226110 39887018 915538142 293205427 403654987 644879956 584413866 289698178 515786541 152255572 811648219 204744145 117821429 64402903 151731366 637084942 527024781 45647707 32783138 999479890 843247068 726184541 408221028 557526922 893971184 114176314 514223504 446748101 466575289 390587311 135656139 926584616 422004981 839539090 78397225 623870556 201750064 832891047 959627424 836366109 624734571 55125064 772501982 451954366 180906995 46544292 606772229 854657036 106683914 713787103 239014138 423880080 900080651 698776791 763935646 635317682 727164309 92103430 941966331 388911321 658638486 380426025 12007394 649232280 615760998 767894426 114815385 96703823 846061985 576473451 402121355 794379554 224743752 411330022 679331754 451258784 779694075 8509621 395012440 840400679 813702186 352679503 979226770 491534476 717432666 613235137 91772992 910266441 119179206 606800128 462220990 175178334 727719143 45675252 514445482 528866987 505331651 416338447 868329219 736700188 94586865 757337555 595761210 401299201 328173069 357725784 243885215 915016740 105400373 105731647 314627167 343374330 425860079 601957020 787624924 232140926 816315415 560811691 293239220 241694919 880238245 731472371 159718833 719691598 644571480 742022387 86148201 852404267 211587629 607710718 803181307 797184677 780912709 466808272 927800651 809170412 924785164 849059194 1233065 435165433 337580021 832820446 679164115 921016001 808652333 907637011 553075481 368524045 702996539 63899919 774208406 756100217 50084753 17682390 384019314 408822534 523268340 407041734 594095094 817194254 775456468 253324865 779637088 800650743 32538904 729791704 302072830 917610472 258890534 885586767 570247740 549279088 292663032 232973110 304275793 388032422 372269892 118091714 897436165 845214421 247024125 386965115 919761232 722605897 273395408 988443232 772148640 84060161 629734321 791211375 118366532 295936693 982073109 279536025 803987927 227568511 608273276 218023654 129863464 639362088 954083962 215239302 791246294 706961980 42294626 191371168 129021283 645179746 695081694 219571056 298631073 468892393 740566871 139506847 958298065 381917365 478154394 323678940 479418117 624356231 825478506 893559872 630368274 23099544 507178734 809554123 279186647 167546951 32682488 937434164 500771960 494194970 756997598 305191684 391153202 895145721 96287378 416020029 172334421 199038739 26818409 165978317 898898890 704315667 924707403 511757826 109989292 153978565 821546643 677348888 669396991 997847276 864302691 478131399 398153776 412124958 758224401 468751973 100710661 821778401 48853455 792321552 446196494 31607358 49461998 71179019 631780364 566151197 470329593 144101649 73644833 174089669 998956899 136248337 602416705 707959715 60993041 646285368 468901299 261106497 107049178 71305225 29932476 530302881 137802971 340992884 972390593 375212459 998440365 239932562 336889254 363360650 574594710 672618011 667773252 295076287 170101638 31398560 765059323 829053127 798968255 745395691 475483016 976633161 380073029 448364080 376569935 570335148 676923450 580393047 633578588 905513665 34411178 776559570 345007418 931741438 916081486 952549448 642142004 661084788 298146734 506500469 588895003 594946996 865779584 693756481 301207453 181322508 727603576 5581161 64974833 694529321 769810537 219325947 482621133 809159817 10799077 851317289 892634711 841894636 18623722 929987464 135394949 884907257 616319906 912189988 892760588 690168214 923201534 485197036 811997633 602109907 529674187 455394464 35235814 963916703 430694019 35463336 469799079 229956463 582172709 24408082 15044204 188889570 165015174 36948262 265140232 370603083 873629606 855911968 649808356 803936679 365218871 495505983 110964944 643540180 126363417 545415233 836162903 119050081 272269154 595289135 157918294 979731988 557876807 195421583 821947993 372362040 987040637 94986673 271219233 8258561 208344484 76531075 584990005 475001006 283170268 977300637 485894316 828534924 871720797 353439995 743401719 555218265 659430007 888572019 900241632 585853352 780397402 148889641 924542529 190478207 711734621 137753754 623911766 980763629 534092760 482300063 280592133 207461227 521198824 901066688 99353428 604636892 254851405 446642352 590452809 45655267 761896376 585765075 560682703 62451798 488179227 69712844 228337835 220192052 583524392 224950153 592022811 863491844 798921849 98068971 897789466 70161751 957379398 454350812 234410220 313330305 141347154 567954924 365956861 749593787 874743356 765070164 704618165 876123134 841188086 975178457 159227020 459301450 597047196 207325729 115422948 637047426 60186968 784273287 905182489 770480245 18724705 4218604 475255386 934254054 103102145 932149041 709707797 672794222 305108413 74369578 64589374 184159455 80161095 468189730 84998676 767456223 1800034 26295659 211939636 904348687 499381841 542355278 461080528 7690285 939458420 246752864 655409670 918543958 94901494 185170602 885166673 346087939 874244111 243393831 177332849 768944987 340478970 92733398 170974003 105832000 716074856 96295888 694960561 4178819 372553673 140929802 846470416 673189735 602509557 143572201 946864006 224505070 562266541 949078689 346152847 997977495 212170735 750039677 214463651 99654893 131301768 518465030 225192113 166686418 628542573 8379439 220574203 165420223 89752688 558670035 6711541 190575004 845347013 859427959 978342682 209284075 699646012 507331962 394602776 513120279 104051468 150944737 74709331 291053572 600636211 509718056 795020361 257786275 830468531 419299145 217277373 418294349 728436023 936360254 82628249 685147623 631481982 264504947 870114335 637074033 154867077 844412363 537456164 570706606 127692891 490466011 853684613 110170897 122383996 370351 427493926 514179564 384972828 698481590 957482812 698184245 641305425 367852404 277823309 959584458 9381124 362737887 769930008 923998321 963185631 914340152 907302915 686821118 405273283 639680211 487246464 777068910 248724133 383021184 834520064 363614410 929594922 413846220 617017206 286748290 265427138 213160046 369351443 91015659 107883976 736655870 431462 282410485 249380360 475239504 543264450 246380111 529246399 647746956 348085654 471202663 295283445 392198401 227901652 950512812 727450735 66694725 907420995 679178199 603020122 359746576 165886131 820988627 209257883 579976460 169790143 637756295 545224221 37788087 688884262 769415934 721223272 16402354 18978674 623726972 51072647 357646259 580206659 242313392 632154475 980532618 886546694 81769334 446148978 512327279 659213535 682252979 805484940 577296345 293425035 648840897 909700197 214393654 191555563 836202751 56381625 13216643 315958636 829549708 372159633 641291744 462727810 298497815 517681672 931377858 785101151 510922698 938408682 170393911 349659181 313983455 747283284 33668300 931794423 533283319 685456068 704306154 563209910 538766418 921083438 349853191 236101678 946667144 481021865 645973751 697782702 642073830 181351645 618553572 623538607 123662187 538924146 564851315 519842681 409691537 570543882 970735113 381009901 757643828 783422956 39077696 253992468 306860506 423810539 452526852 410168692 125462774 971202487 936035414 60820993 192790033 742663715 959687813 189948793 622123556 935403115 204215185 975793803 267000250 89305354 890707548 667182000 437960315 543666146 782250414 214777809 184534976 306998762 899128560 601109737 423751373 198015621 178965736 366214587 881872401 568018154 12928461 958983476 869272137 704328512 892154508 813947667 551979261 564530993 267204186 614049693 428244490 552053946 871100739 282274400 892113289 175580958 928534215 42862365 450949040 505228122 680445662 169758433 664650560 922385118 450016123 115231926 166626920 361842939 958075068 444820038 43364993 666450930 179056682 548096428 626820696 124852748 365634149 339302992 249395673 223681270 611813756 723857751 39270987 979647796 779048324 523018146 796215785 443341087 600903158 65681856 472873699 500506001 733293893 947066985 615142058 819045664 301811976 109239443 352224098 305352829 180656541 293944413 942003905 225881561 226190912 263119355 192151933 212928657 526674377 377951992 849681883 933823923 388452297 865008403 498327728 899195639 374031460 292005038 730507827 369504029 173626609 325986567 517205851 600648042 472890963 588646382 794028454 569047730 741215336 260153936 663903501 446766062 793935583 895484718 283092113 338339382 795500099 985253859 441491314 550762385 174865330 151256922 293260299 623394929 221091627 211945816 168076607 838635237 379543356 487050930 155061417 544193008 29746538 373794804 697517086 197469565 295674426 894585235 268591673 346866615 742387366 480323041 774923394 628597720 34093986 263455737 75897730 393567441 505832519 817573520 528056609 417953466 45298891 274475675 219224103 215902887 957499815 516702440 716448198 574133256 179108353 529786507 850227069 984257989 372639198 836754297 422763356 901031621 292591038 253083611 615515661 172171742 301612901 777904846 991088548 937359635 415469683 981723445 897305881 680989684 62061918 265630315 386782433 346393905 981354060 204979196 44535817 685441981 961888390 318506479 281171293 710717647 649378904 505384936 826116661 789543455 746980661 113637696 192291177 760591074 740312927 266103743 277954394 912371297 459528177 703646032 127217509 272344513 453705567 344779253 503150170 76362415 160465596 376194242 688648965 363053443 200017824 434259008 240300329 718588322 724202927 630631693 312821051 400519168 638582279 415873089 973263439 730033446 293506692 355487239 423553483 206750670 142537030 885733703 785012343 359128688 275911785 500502403 690888439 687165404 139424539 733624799 680568378 643199493 248438410 650994086 496760087 987908176 145635058 303979440 700002706 646807966 881600567 827419902 935968726 412893462 675111777 218313932 549693474 31489021 942010785 277082162 396245549 750627330 757339941 913662803 748307385 604148871 708386526 457330644 300384631 220050381 429188359 825303013 865339335 986725446 414719276 388985049 903217710 826037244 35709352 37973231 188831067 117996483 137076663 679301249 50597425 616720063 588697813 412374367 668024190 773282180 810374847 304345218 121503523 535430617 133116185 625943449 921170267 723367326 81471041 607020532 413137339 497632145 717361420 435540833 17228616 644946472 498053178 483316517 626974874 889628745 550602220 438825827 375985911 689157148 543080573 317904947 680140607 481196888 464722934 872456771 793228847 345791340 982756201 416567519 541825492 905805117 839078742 645649684 350815181 889410176 818837031 963061714 53277803 34652876 742349720 862376311 209846487 175519256 191401037 635271803 537508235 937637536 324737226 38984425 688725822 291749579 710285188 352093534 671424442 387333944 551121486 770115647 85612443 46370727 638525284 738873520 102356751 648439010 14374484 935229695 788027554 370383777 960097408 169003343 69432528 464938478 77333680 225175594 269364919 640654887 945756677 674563990 379924089 936794565 947144731 359003567 314511107 346796907 111228997 453765092 102660543 904819324 338789823 919214705 513504127 275533875 861165259 710092537 47900159 529596533 230672593 674382898 756626716 14855749 246841864 819155352 986827864 827999414 952181735 568340473 481873572 469895775 31202638 589242200 121563785 879350502 498234848 403866299 714766857 681714088 973744407 918954224 997910787 821338838 558994238 434074510 109939552 501820762 759662565 753715896 79984772 490350198 33931131 659839779 931912546 839379068 740664495 381260022 648446970 369289023 289960610 80822096 897367051 390225605 108324251 285385611 836426222 299020770 867755393 828153290 72759251 965199871 886212367 679200611 390462995 44928598 933893909 103353837 876184491 761294114 882349233 919294658 505169031 541147183 128447160 624706090 896209637 982449866 233187148 455002225 128657886 761061701 668593338 104215506 798396998 147748653 885076608 171530549 528730335 427131238 139026961 320451749 75096405 801375128 747104140 569067053 725464104 928463113 180085680 174685640 707567242 957313298 470127191 3168607 585639192 582127240 719538378 563670166 791294687 786472771 309687007 744462075 28628570 521749558 888570684 891028399 121007552 13885672 311714394 893737087 474250076 855880619 840233600 748779566 758213082 325426961 610304852 545014609 673996331 802014098 190789151 181193143 748109431 479780130 385591723 401069777 897608875 982265895 120279825 135807864 203192674 115181505 441738772 621296676 231625657 4984838 14105531 182569170 26056538 315158824 24155281 680300726 640811465 189852764 958044773 426025784 698804513 760211112 913094233 349343380 385855371 28941127 393495948 538555135 380450041 565056372 467340793 81912133 416796669 705333678 204192847 725610444 500844527 947211501 307074123 535321270 98947570 593890909 686711159 948438743 549439892 813247227 354890660 499387761 637357431 839697879 683071812 458659365 965313521 851990609 225418133 659183789 391020058 853889390 738562590 40105726 405256712 565338504 370746006 969199153 443955303 135216673 304116277 758936288 984961639 929673140 680759231 457900165 557722047 514288885 261652786 158457873 306848501 727084053 300575170 105536638 293097388 87623751 629461774 181228494 706614776 181146347 301692995 133819086 470795245 185777189 604482673 839195785 809141996 512485100 64678912 547009943 731745205 47356171 266796574 785017081 429480517 543503596 139230466 445282585 894748426 200518349 68794285 510738393 103946310 656040891 414706607 908646837 509152614 486301751 587443034 613361150 689381665 591329854 585023187 348250297 363527847 604217965 578466822 897130472 121414328 240913023 211428631 699014333 755433121 24640406 984709074 124718373 982647280 710375821 179872153 237871325 273578247 612999633 11259809 652772711 433250531 285358013 120806264 366538121 608867998 454971774 615737439 736966846 208564694 673930713 584253295 963014612 415656559 378680746 18424425 942244027 709524582 873665461 958088872 383461067 915488559 92185360 613861907 961619617 297841708 362358811 483643569 894905353 386175438 309666663 451390652 983221068 115440690 414025628 148314589 145003949 668021513 950002251 645689953 321080936 400532674 669330006 561485506 995221741 37394943 761506617 431794955 859582072 376304188 682095972 23287304 276835422 128834156 205773009 574950595 201295457 365801806 224850984 667144403 278154788 358224443 603723335 322475026 423844587 255916948 462985964 37080166 413512574 763466885 719511337 299391916 595072812 331770211 974842089 370262616 832266426 30758898 54903469 579980514 533429069 35774573 503679476 667382530 608641583 214980643 681071071 754549866 595536808 164973373 481266243 17225933 172752431 958122326 647549491 523115922 515278529 596083099 243442427 287278769 152194525 57611567 448478779 126159337 680995256 626071140 80183166 673946082 436075743 852569634 578187550 408851774 820119646 227843493 28018175 687949284 925627401 773239875 343023953 21827463 381333629 543716383 138561486 127095308 192779010 690102300 755373017 41872289 622287519 887229325 386935961 748723508 906721024 433790353 525224857 133990101 529882897 42059249 716892700 713478665 761715576 121729045 777408182 741357994 690844027 476204156 989443982 355716445 498511554 184834561 860443664 518620557 16574060 836290730 595247991 32458735 592228854 769898765 148033125 176968292 868732825 403383659 367049048 836822522 689050991 44140202 846483255 113190387 92761926 329436593 913160945 101997731 836110238 404472001 118718942 674836472 361993514 415129765 695875111 320865969 250671887 398352173 374973008 456494998 336303765 937812388 436337672 147304696 88968997 905455887 798667502 371001550 962467943 641264332 807020093 509886449 780373211 417224638 303540454 515919115 820378604 153932324 27150291 846427348 776260675 3785492 615678375 862796989 491289281 901891729 106699337 421877492 381700988 778147307 7184257 71640978 710359205 655192617 979470272 665747062 258069768 320751441 488482161 232748261 696139421 104646930 100494589 639974883 676428628 184858659 746941517 642890067 113325963 838867490 450417595 678090635 70386373 921506169 111696408 273723002 428369539 69092678 416889596 681132609 146006241 450295027 461644079 755865013 160637424 32039194 205996319 42778259 744056273 693245535 325121583 760451381 992406698 913541465 33695686 508074338 345129775 196091273 626829362 146342667 334971998 844319061 397981341 231511265 461934266 611205287 686405670 77763454 355933436 709541896 524638724 754177566 598970016 738938981 944732002 433633923 402881914 20682908 95479654 527503198 85226967 452765407 823914809 173437289 175780686 187411184 779170627 928730142 732451948 798759274 896217307 348284965 232484936 840106860 465619082 419516684 480228922 453097730 454396709 537911949 424251386 992029690 129915907 918209713 117543963 952971776 18710629 65224581 27470543 594949732 457200042 163689507 206720593 838940135 970308503 345905023 879110343 435100530 295115298 561539180 607322706 204211991 480229161 392525877 471975169 267733767 505296637 969701626 811434320 901186154 347853745 801495273 900774930 646949867 142307645 146234517 17439488 200800033 876564124 67257404 658392090 360350493 808482793 622864502 897453596 721045227 650313863 88503177 852579312 833248121 536469065 580990644 695086259 187003610 832511401 676809058 118279128 696522084 184334281 842904599 713755985 791296477 892694346 960470339 263005121 980199595 470346979 456206554 830196874 844952190 694155579 797567869 174192017 742600595 188504063 679302720 115041091 323178578 517935131 92745746 644384181 871821309 954018925 173032228 646663982 277946938 756037913 432792616 340885092 559910637 813631493 199232571 239498767 4472417 67690605 554932371 162422364 959913422 380083810 444511797 117052605 427218082 109849647 659105161 442212216 338856202 262722257 953867318 113761249 649397324 848039252 837622371 796895565 571042207 24126659 788408761 387985939 13534282 755610262 622540640 258140545 601772487 574962054 600941969 941654821 266985662 282163946 497413313 361622023 324730274 562870570 344432002 655222534 523651515 875502470 416778684 629559132 596758908 759095534 360871015 265308395 814218763 379823276 23834452 272247288 136815141 489759996 605296390 521769506 545339799 665890368 422509310 899110930 257380575 912701116 499294189 743363684 339512657 621803145 116013927 466369602 967216552 506483747 386779695 33280371 835575705 350206245 673600435 429107041 145597404 710270055 268911512 758402334 605790169 831179321 633208243 352849309 500914638 160397903 79397072 905446819 643420576 511334447 27571753 67129169 910932041 196531409 553093604 748386954 393600096 866458144 956208486 32570027 893144060 153336348 334108508 554007876 995993055 257697721 328824142 454398314 428722829 17396991 592729370 891320079 477876643 500220538 877551445 141589657 818472864 780248227 776844671 446676757 528215940 682280301 468120845 457756569 249206432 881087830 879692408 533494655 754190927 435089534 347354663 385556706 906017886 247512159 369273889 68498409 291184206 398199678 75689550 436344073 112900765 806737369 381765132 594685037 924613370 250661522 3606963 763635472 761468467 954300843 53500283 521778615 935155561 869481744 468894813 816474086 146450770 836174520 560422842 980896062 76768225 250811340 952540848 398372061 53129337 186754363 827528023 9892405 312331952 967841112 637288187 594165508 727948169 700709916 693465492 389996868 545335601 623708882 735676146 540825686 12329668 360661280 320034495 939434907 749632671 149271421 486477127 921668463 736180513 222979817 739985290 361998392 888638259 893683442 551982942 152461583 441364171 685257493 720682241 282640042 292496585 691527191 170776725 70508209 89603077 374574403 334310183 246639990 260358878 264290860 765431290 446151387 675886720 71265662 471949971 324028657 958786162 612479942 409537775 644877140 144262064 548159112 358885813 5530116 656812087 172551915 790746682 859356306 42107861 137848393 566007628 976023383 134022452 148984695 457785718 908896701 831082795 89576398 252227804 730805783 138807148 529481979 890185763 948190278 17794731 425913576 402906030 799122510 185573264 358599802 646919550 59524519 810853169 232590697 39666250 438258144 855506132 818330136 994201234 847771794 100200638 828378089 627932934 52779080 899663424 496918081 908105913 582185695 78927403 937779720 160186485 536162408 689499207 603581636 184658674 408192873 726703378 494212891 56409572 568139257 123643918 275966479 672970342 889110447 862425098 883331057 599161772 607618265 507527023 839362746 378222262 122054303 535059449 839345456 688850210 869141786 22642600 301785173 680126805 808923777 79153337 392534687 151707717 218480674 822826768 309704712 69213249 465540483 804449123 872688367 4853585 735311602 698032267 207476291 959154538 315511624 417653985 489419589 303518836 286783386 676678375 890090965 818556814 456559690 163473810 498381591 732308618 890222019 34927886 246542838 137565758 127490933 210357161 928605384 476072472 58818807 137214885 959001838 374080868 580051994 733268952 213353699 652520298 498456102 600527401 179231681 166494984 427103624 699070791 413237829 643219653 442215510 822739838 619436536 68561363 603073712 827384951 535345807 803013132 411185123 997030122 966763338 507910877 852916381 198591806 394919273 317359690 299010211 107043230 878843184 342740559 774340100 711248064 962556016 108584074 670941370 87298337 683504235 36622746 712528851 872915185 707368664 474826394 276747629 561787892 175313793 728904674 554813991 168792229 732904817 82979991 465718276 83826946 246452014 84523032 772826946 709420704 364472483 583399110 984261198 597008610 928991630 638729560 675021687 744789700 268017281 165213708 167029106 680969740 248489490 48282678 253748682 446706028 88020302 744469313 837480776 459676133 58515161 995201740 144832823 740908845 206644960 873717285 492915460 690352069 133255351 733779686 144742506 799757149 850590529 121595853 339198090 485247778 239482737 98986581 173820722 515633363 527907325 520652256 212094583 493019045 8847413 762814338 551408327 561039530 639050833 427830507 610703418 807258822 251556775 890468524 583267655 895476842 631501607 766995160 816779226 481517337 122603017 478136610 986136592 371523237 132358842 776099589 61557118 495180135 198327433 103132140 54594439 863300734 61275377 293420884 268220250 994395428 812514554 673045290 863176540 400652291 998153204 21569976 470617775 749049551 682178784 919064599 921626458 156742720 53938972 863267210 891112880 686489253 743688164 691793123 857143199 871464094 135276173 947977241 871169325 892100563 238583520 947136161 633676869 896472943 275647189 377629025 677014338 470423085 22866385 808054623 376790389 415992267 16584983 187538223 3313222 517872205 853939528 619861392 398413636 635121088 885590546 538957766 467427489 404358436 76638860 707276855 503643725 70354394 302590222 193018069 118020148 245129430 550509351 496554816 265443218 748902211 245765890 638066284 326743647 703771190 864455697 163955724 911028868 420213810 428382762 94956779 145588738 926521917 573152143 901944294 832007790 653323185 653041831 12216516 590089732 707369438 446912393 840818075 633185351 588995962 213885908 173225838 355829174 452649243 176404331 14079828 200774132 220627647 55453337 349654798 374970842 671193305 621101226 485587532 288091505 229210587 15333569 320989012 582854200 219224869 21884105 629113579 374120203 109294445 649449326 829475543 785716668 894414772 392810013 579853358 237489292 681873551 53938865 660662236 936500598 924950966 162516920 963390504 422995969 678765851 303333878 806288310 742139611 803572936 619279223 927035528 963074187 959909575 284898931 443697808 455802499 430644018 34007775 409875578 167768881 13968299 252717999 276502134 478112047 164067814 328425798 315575027 783282969 299197312 616930275 601012303 767102336 963600843 877764662 493781590 216418201 596839507 148345304 657850428 57085297 262770932 681491668 45240748 851468954 389544284 980455274 290138912 155291650 603893787 81828051 461914111 644489136 9980468 398703728 924587513 694671873 327759205 532612000 324228635 239731911 286261331 236134544 998161275 668200520 607932411 392329135 404032833 462426289 390898924 296194283 166362550 849862420 741756886 824255687 802488934 944189168 237032934 510712220 48978858 536574329 289057547 261736488 503564917 242474898 796893309 413626211 445660526 289874263 557670431 527504539 505807523 147729325 730104519 121542699 566632938 401546157 28181739 708944599 819676457 37521102 902138882 794747927 920415322 860943405 447204854 511080311 172762017 491985487 444248434 487971159 218590758 81864172 789803424 901180700 887540952 216713238 976222914 808256693 119782782 338487015 730335142 623145273 260046519 138029085 6201202 363105013 363194628 963934089 634496006 968167698 289192376 196182839 141058715 507476878 967979531 366100623 932314045 42832051 238608147 542003233 816152397 697988664 232268441 149199264 84284441 288276102 950026246 210371727 861932956 939222973 536324254 742008444 783409582 203341528 556910207 351798333 71571996 640028082 724368345 986232945 403569531 368615689 440861617 545457592 726602276 684179613 745453211 682215136 667591996 925376045 808520609 976446087 308079053 42936785 639724633 847033741 630354057 767566392 852860891 33773568 289103838 714528473 628688813 355652590 821851738 999284139 713773696 102849592 619551347 685046477 603413603 754411613 992839811 646503653 453057755 95928605 775892073 732331231 117411998 723373021 243620583 270341117 134480469 539442331 388887369 399458925 528550957 617397509 423956573 214886376 667866132 140981356 673155291 756994878 402260298 521708125 381041031 764183482 342240508 7556920 585889876 61583358 99141598 921024872 332683544 142140992 538109297 923239133 151149248 698788980 498746275 398789285 500926360 735907550 228924394 764691751 164096220 407720071 853670534 717759455 666623965 767921409 289260415 877602823 415600269 607055862 561203905 185057722 132157708 978461035 344810256 38947157 167486954 367144640 754247872 911400399 242541087 440428826 86376202 511276519 742855254 418867193 192890086 771794149 762595083 846865596 360575974 240076773 175897374 669811117 608886532 723238240 242394746 966056775 383648996 792055087 560118738 497101353 240285968 284924036 165941842 30647219 897351826 781868180 635708014 128501734 451137891 536898060 716038633 323603340 408624423 962083295 459200822 699789778 727373765 68733316 587582373 616815364 823324316 489755067 317898846 558856933 836148495 239854267 773251442 540812985 529147933 732996450 676660550 703534280 327806682 882910295 527400845 945575086 619185691 583528723 977117627 238506172 659766881 917230835 948430436 52307916 662760341 429571734 130099263 270786082 112657948 778234367 292219672 23858559 465756067 955045280 480875979 616749105 458485718 754132265 528571643 203628395 244318031 516509278 317414272 951946286 536060887 165895472 2526728 433174483 235125273 729232283 407407384 134303615 326639767 9409223 874763369 685232057 429399180 618844502 126004608 285926251 469419494 363049761 12255819 902727880 855063941 973098147 373580208 847455002 214121247 430490586 618532351 366808484 340385927 691662600 749223576 449562952 883594550 694328962 994593190 817041211 892654409 568376946 138477670 534275346 609029837 648006995 982926649 305279275 928944415 724290949 342651624 313107464 362956487 813336911 959331019 516512245 208910216 445742626 154916389 767463041 749279211 686290801 951780369 199710143 387118293 112243539 85525127 220689477 920657705 878567165 484004055 902776216 220940411 371440577 9558073 148712483 709834619 203383958 853140586 897005312 285966452 224715024 751970543 8138131 675777178 852869773 432378365 289817844 893009285 545168736 144859701 152758129 194691287 776299704 753828738 946797895 468416893 612541194 552148679 546580188 938055733 386700250 379246311 615606780 360609340 570062235 845267862 320688029 345218652 523917263 937020823 481467355 517451960 523285599 767374475 765535974 240918164 725847679 476562072 477418489 918622196 468867274 292503990 811703975 111065818 482495205 89680635 6798039 254135049 408642216 20258250 745008407 19314347 492303985 643921577 362219517 173273656 773841409 847495423 36887385 974999133 277077687 254330313 753338600 487149327 562171836 362593864 742240388 787874608 397190544 808801397 609971872 793539161 972362796 946568502 931895923 246270757 769191334 38271056 44399519 375583512 788173496 567250636 53492081 877366597 625181593 480954007 998738144 487669261 982561655 452025214 10654705 880788676 924945679 879181226 500370338 250952444 85725856 325171902 766433220 253599669 896119220 268892444 652164897 868800006 212602254 394406450 390952007 866124917 211971535 272205119 833336463 501260298 734688531 517171553 686102894 465881272 411389993 384161582 180406874 519984661 686305996 78856674 97365645 779912321 144839997 787292730 518293176 29049627 43217138 100940655 302839610 419381474 238379957 653154442 525440880 860244560 798454164 514813276 37980544 326894237 670803406 308212902 479745102 161274447 393841577 309779967 373833514 466865303 284152525 43110375 19621035 930841509 886408034 656916268 527271556 45514325 755857453 637155389 359628099 948818144 427837958 285171438 414308198 863787968 57583396 719760671 61031826 343428240 148816239 643506104 622036154 127593745 587552080 506907427 54675776 275175204 915656976 528733597 918998104 337381335 958358987 39103875 140830372 222922353 488566455 617418067 896178701 614157265 849875475 162879534 760659553 87353150 339180119 526038466 954635706 974318254 610785699 401338513 88425946 277612695 255627184 69889573 245511753 690630840 454027601 323247617 944500681 430649252 507906385 738528577 754917045 257280781 423584391 534555000 658521939 33977734 971144465 239035884 765132392 603554396 521723084 609126373 798543761 308796106 737315660 9087010 783278314 664925615 414722638 495763193 533978084 660745295 642332744 723924340 538264944 386322169 120194542 186031031 139111139 194016740 236588959 495247258 467319996 307963959 763096958 730192043 9372038 73799509 112208137 968587531 422536884 943443787 640823276 274188755 746159019 320623636 878480541 715839730 894057592 169230843 517448338 346127465 374467873 267553086 918727683 868741260 53097262 418198685 374401462 259840270 751364925 265324210 809407698 915690638 585958725 307094475 936045616 569353493 744056308 606740471 967411509 356782247 495211721 744111594 997968115 702875125 198980254 729540224 280672941 122494616 112899584 992719802 378272279 685075988 638059792 199628057 549710256 815436337 674205194 562473897 813545112 773751145 909930945 597028883 97856714 750901914 145624528 708138587 115401133 951082181 379520337 404441395 451838924 143839129 598008111 455612321 330684497 65540941 951217722 653267758 650758046 758878332 438893902 444679979 11101937 706131509 352337435 779837461 563010040 730163774 595437952 978140593 194642695 343551542 919727894 279394557 151859008 334321313 190500031 37415366 143513768 971857367 516640818 976187784 119138492 45560461 685637350 261907340 731149398 51384345 668803777 966550236 298738740 229119710 372584130 257996205 432292603 761815323 49700672 816433359 491228170 806319362 492800663 84777305 939436431 88154584 849445502 543548247 821876782 884583935 593578119 491281072 789287024 160220117 815988764 203505297 533419322 314485141 411799767 104343850 209131236 441523985 434314173 401249519 307627216 32672065 359369834 276746366 395544383 521982356 188226673 974843282 547480147 631774245 795517319 285864752 737208093 731416463 67969454 287123198 79596973 4164700 726527144 325209134 144669350 998433853 315644243 106178252 64554173 280142302 939890367 119540127 861927971 223644068 751391668 168129434 552582254 730159424 571856557 148305020 961351714 740280396 135435716 341764366 288028448 272459135 162026080 828249793 250218420 804932845 243723597 885017541 463913118 457538368 948920768 509188107 987721114 625265294 74353439 412648862 81966210 567136305 309881677 839998246 568745708 374726606 903173312 396786353 878583211 406183581 375955449 405342180 993594986 396556881 330232259 727222632 858733611 81456286 375737879 899375590 326061767 754995479 605049135 161539670 515078823 221006288 837429398 494693740 743772409 638437923 467490977 108261380 974456006 659198108 304915784 541340277 338244963 995480858 518144245 879207706 474901983 784941734 430205086 91267461 680028698 242878686 132505630 646977439 899736651 395999026 777974985 719813509 886001365 125364866 588485821 497976171 340589092 632226822 572219913 428333138 716920861 414881200 301891137 63460915 781070858 666352738 784203797 312634199 137652567 949925820 495122550 743348001 131081516 817894375 717925062 117196830 75657357 67486728 606410962 512638961 378370376 771660909 634364321 577636852 751947359 816629008 560235881 881111887 449515352 135899441 165611078 783756194 360324289 647034405 844842990 753965203 178795695 535105942 731290677 947434419 122106188 75498572 495288841 324630276 974810634 566311022 437127272 872054189 717826712 290522031 656489019 180147448 967515907 155664892 973971289 273066692 557175549 446909964 958429132 962383987 679972531 910063781 961343572 680939061 11969777 121881405 364482443 87221269 316258199 227559957 248836344 695121343 246265259 548611446 83332341 239835972 220828612 537964834 29156764 996107405 680729640 808930354 256238455 881926313 376664865 456719168 937164778 424580175 567918575 566811938 287191545 925363067 285100876 260266137 355236523 382167462 447564874 40998548 626994516 731059970 409627664 202633388 143982493 584306717 443744705 355071589 942171604 893569813 300987546 664283878 909523609 990584199 217975942 156630224 556297437 413565492 335294276 374213430 533353749 74604929 918952374 672619289 196538597 797443545 233773022 831861892 655580179 852871663 368191164 708253840 964721398 205986033 251030496 704484346 445861406 586907991 770596825 551252485 741690958 982938979 765096737 454530885 57278270 485330693 374416886 477930588 944399916 887917471 510958965 628498431 70690276 776035631 169662603 145480851 904134037 655926242 48464493 775698149 454299938 890863705 923385616 734657388 725897191 828399990 54256933 66998115 288019818 429962289 795352208 936314136 874077347 880836533 550234772 305354120 410339834 548627697 740010587 607583446 499602935 283756597 893221152 68593677 698670682 862397287 762841058 156422039 740765386 640999603 10787284 767531651 207283748 545056473 827877855 30816394 260290435 805597684 83002943 241753245 713532639 468204550 567021186 811465720 141226953 166607461 469948672 108572982 509484542 229558323 102654359 985261298 818306462 934432647 928844984 426704069 353506534 698707710 869061491 60360158 755676025 515427829 972177084 15858095 505986542 889551798 118565604 25064214 32455897 430816415 716027917 192731783 754478160 175755798 507309102 926603787 499484777 481779187 338309630 539918869 813417008 933334574 966958136 868632438 197499230 506930912 952319053 597547312 723757367 82485435 230022909 494886047 488919720 780438952 254631178 611327541 75049949 921544523 914361069 593536093 465316224 290075828 583889602 67514283 14653000 167820410 71465306 153218227 530751714 73116578 972704400 119956249 20322662 83022243 236864881 993357793 610209486 991418191 164688620 780854693 282005098 492263238 870183624 301512864 502655035 671923316 68851086 613909028 378370595 635122611 80425018 818751464 349700725 772145971 763752846 845831474 381728176 641633480 700413640 491730749 355717199 529715141 939675812 24839811 387003266 44609149 445014181 270445912 939553791 548664430 651163408 145141842 929782688 361733769 497151408 446103115 984837450 480069230 407094770 433710204 806589815 547877164 849269580 697887119 532919463 886100481 325399935 675604293 93181094 633939981 963553458 550587745 463187069 504095959 230557564 666486958 129386279 376726600 980560013 561098635 448416285 904329143 656492186 288828705 507943208 360422387 24619413 380388533 746860075 321456435 350076471 642145711 965443210 968309216 469132269 436186620 641958520 592699533 952936443 215312137 424992812 550394159 641859982 980139082 94292352 890474876 379764477 470775166 358066810 891657846 678304451 496910404 398864317 635476035 595981282 214962863 48768188 971111161 569051559 318277020 637739953 842709756 369279900 465629054 172155711 918365572 952819363 223565693 755365858 776392231 57285678 955921878 344384725 571028972 248434170 150157079 518260229 373482374 234942972 114304383 30816564 793920900 63033746 431200671 702873561 778987943 549782663 925398997 415792110 429719540 49940552 558255807 339094099 197690988 134414510 282544713 651730345 374456253 640633026 557061105 492166925 908199772 12970579 217134462 757085409 390865782 72450333 969643056 411434264 175386283 871211918 220424770 384039251 879964030 466763460 418858333 370600022 302205402 68193710 502600070 72072701 610270919 264291844 661291921 421030186 890156087 329325371 689256026 379262191 180928831 225022357 230892859 114481962 77475119 91708632 449864882 778016159 368589297 697373840 580621151 86569807 751492565 783968220 459870894 553241787 189229043 922249342 292745038 913125331 669730133 276120789 276466271 999680188 40860901 690891056 304204113 741870534 29355005 330042921 650324325 782764461 840022131 60661757 962512537 695166621 28378893 514253221 405477264 962333164 53976788 941764250 422952338 390246470 47947922 400339311 893028358 638418673 100552539 48613669 436832087 252468487 926169516 776008763 591781456 760809501 7753649 393525937 18368442 218524592 237946590 744868454 595647165 946521362 645574549 29630226 621870083 347213364 880886747 476921689 789482741 253032341 99383542 797396361 388747942 831039910 375484272 269538882 776809039 280661433 348259934 513999852 256121332 532054752 104142334 778932078 533502665 655564581 702812588 765691971 130456020 248112484 60640783 184560578 126420176 37116008 385963191 349979521 642193138 863081551 591456843 762861404 650166583 148847780 523111003 115092486 832595445 327663657 197950277 946848156 581450516 384328761 905363588 33204567 292288271 863484681 722374261 496213116 420410371 993624182 430546035 337154914 928608015 600976804 928498401 664198121 1990382 588407878 264291666 838795084 666609324 991983452 138086043 850106330 286478106 348686030 920000837 762052329 993509804 208215048 613968736 763948824 761839595 255760138 148769920 177915668 943709001 850148610 666766022 246760014 809813317 329552620 499422688 792613107 185807380 115619378 244543957 890708376 789408651 564739223 13261631 461168701 125718228 135802964 82680125 50262859 665092876 238443456 185655626 621291822 324001097 825537930 925348798 169660629 75683382 859400582 471394109 482749060 522156876 578598314 573287394 137073483 195507607 163237990 628059601 881386383 488948085 36586838 903395887 690280240 462798422 690783478 650212373 121226188 566989467 12514707 579965189 162551660 316199954 374201237 957361737 303800856 913576601 370227247 650409076 158532739 664531340 363385581 101339173 342037681 256123707 386037301 921948683 176957120 409131679 24831528 118346522 744440143 281441132 217299917 376855762 964872885 81698860 684495003 919913751 33758137 967541868 693176974 363810363 986946788 590513812 478669665 415406291 508994100 288200997 637692610 820810474 314809954 135985751 988879508 841185344 899129153 866554956 625128417 483845630 273419544 617175611 658124210 875934110 503832614 408516936 986308931 417881291 293218363 321058616 928584065 899250280 899324588 440208438 904310707 107708940 7724710 773868201 231853752 218848423 676022752 138173323 594925225 591587144 716999433 781903915 30723614 45191044 301085728 771868270 483455231 389609180 951745384 929692634 789671594 472136990 47248563 875523119 267801785 310309843 824656610 163181578 279676120 698804591 253087017 833736373 730313419 279690111 52958644 933821166 621155734 974629915 228281886 354868026 128935437 822488788 949985729 54811293 145759352 486767174 603541963 333179912 293916407 369410987 635349384 452258347 232664273 983026387 731632412 628897347 678853426 435185060 124031519 896469820 843448959 931796756 97742519 879172565 501224475 678044458 624807916 248338640 897594852 273918992 137500358 847758828 620658008 664574434 187288272 42539937 463359886 782713496 783442109 722771971 2727259 480436778 931652674 312816347 329511895 950950513 893735226 3261935 131598554 145612874 8547624 975316215 511162602 287953564 820198951 125694868 479451092 406094781 939935810 502063734 319841764 178583044 58621535 415068729 112354085 495070182 241696391 684968235 150282199 69681190 515230586 152862594 482797252 181981507 325345478 133232745 857991122 464175727 38821352 759357926 932033851 566658697 109303535 377359426 345924119 303501260 941574940 771377455 296134888 842014309 194696846 44418933 556162184 782300332 602258653 396788634 887557838 934144047 777702208 318099819 771257980 326097645 715434245 608510904 999884907 561499209 251347704 776485176 545165739 53210157 772189335 784325099 818547610 333490868 545817767 443123292 227798589 298042312 246521071 270035070 462873032 899710777 752484554 679671063 49965380 555921628 334218400 982490722 84259288 12647483 145867929 249037710 924732837 785167476 744810384 602151041 805244084 69932736 374798185 461673162 956601334 870178176 928024119 937051605 702224874 838772714 945793382 153118923 708819516 776759602 733910031 905014124 176678008 618177761 865431483 287150821 714165126 156998445 842339751 856325932 981166498 940938689 304158264 163700036 601024094 622990529 951128432 165466435 584644399 330249793 273357658 746699301 978304897 928282630 210951105 442606553 47018760 234418597 629187156 996867124 921426572 616779209 72924773 259003064 920318971 548973322 683774553 461187414 350533165 638888622 366417810 718170277 235277925 354377783 689796381 192475062 315558489 743841567 27521565 336843229 937175396 118060763 405846794 331431051 675179815 129726667 263134782 303488939 294824104 84431676 503304305 685844561 27056363 972211866 398008447 407878774 519003341 377918440 723329955 373544 745127132 495636724 90278910 618943141 734433677 297425631 725533140 631668198 927988548 792655927 169112543 134869321 34620893 272978114 924705314 241265098 508551990 75279038 595661950 365903242 969380774 475036179 13094817 149375841 932250274 168291502 237712120 206523095 274370589 715491515 395124855 201079804 561590953 791487973 379121766 291710044 648371758 310880443 952176560 709407379 630880583 636650760 828669850 572167262 471534503 506720505 620994301 967539499 813680785 205668758 571515316 939562061 592217829 684826642 874102841 889127786 833466851 948358066 658017424 166166752 170073641 416754145 819591554 55535186 303523807 414723614 717127300 912589553 530138381 8124055 206630165 643124666 499754703 374016979 982740726 919602131 400250306 74841856 498455129 569126664 907086700 619051057 454897537 755279120 743029668 163002641 526492921 754156736 263090721 997917206 459146209 95052368 77063003 683199133 204834892 141486673 360882173 989228808 288689292 980618162 454012294 496853906 904867345 683750316 508109989 396973828 920963723 551802010 444146683 568487793 837984926 123200881 282082645 644323027 769228670 671603115 392920880 433982966 604239139 167783997 977129627 274009394 713071917 622871567 168385531 15827836 700752644 440306466 61092563 110765819 720911703 931612080 869734014 861294140 426430484 504596386 588670154 469740891 564875746 684323434 989356261 15775339 625319169 839963267 735858819 999341556 639303262 99670718 681356191 649963171 57964542 903265388 991223862 679999708 708507823 613104161 53577355 620524897 240579788 547246350 148672806 520668788 273125888 792412238 729686795 97992492 485229510 535124060 635723383 751259857 560939153 306975333 129700925 363073969 953345573 184328352 313102079 449377415 98604283 375941445 304902193 475812605 63990333 433271261 349042832 39417577 433613516 600571743 629185469 131146398 690822000 448482138 81031712 361222266 93611781 484180330 462694106 366427420 870413478 531177204 168046040 278782921 63642599 628840347 771347846 722908168 642142483 767080346 996048161 744570165 795387308 895158957 538801047 549160039 605414508 50848852 143965683 274394233 592742766 769534753 624589443 731165410 362597797 540161549 315613383 882293062 831689657 945883676 707147979 789167479 851415878 432523959 905099194 563218273 871571818 150838512 627335276 606816656 529619676 556037471 411300189 168994637 664231802 308801590 726386017 775250284 997676406 30223263 34370114 728921961 721024169 908265546 899570230 942874664 806412804 112558505 692288094 688510461 157199172 725331920 268616635 341774411 514875351 273942758 209190523 875529343 584959408 193152044 826318792 467452267 143584815 951592492 110844508 403843583 610514166 612623831 722116675 109917155 752324584 361896415 12598407 306280539 88341955 486885902 22962551 69994344 589487846 639997789 521940069 63275168 761843351 164665496 765755012 662327007 77246022 166332696 369754322 875891735 516033962 552870602 888429702 994577299 984110713 801234091 921788915 275559528 558168887 733894440 96881505 585637851 96956142 511366920 499458958 695266326 817406667 444154365 864329624 709799478 319503812 681008013 80571595 938662601 592547251 503057967 893758467 710708183 486948205 363335989 491421378 581062446 466788804 153077944 379736995 50415110 576833173 893246779 522370688 951952818 443773184 979739405 565590225 978159887 527250433 757759275 769908385 44717777 45172480 832635453 760256187 885087352 15462776 393376888 157755957 307314830 150855206 547955849 773972361 50712731 600234178 318026237 526942456 645077719 683261514 909611489 176507747 167583640 690384739 824664849 847531479 724465485 484822393 236257264 25193617 188572389 250463024 105701932 877825429 479098150 458933362 730432452 50391221 905176324 840866947 563601705 580833657 49183646 16780963 205076099 986658748 105874547 456663535 488793326 561985717 396179953 237561874 261662227 595436875 689828372 652236104 526314485 451069812 790230958 903758558 710776240 15288639 856603080 323438959 375223041 369611369 402491267 375717646 465439842 543390152 580430725 565597093 768585543 474519071 211102133 349973080 328060778 375505288 977604518 12630143 830184673 24104658 816739258 940459615 632908006 190357432 498122975 72125340 513695520 789874720 203958597 747255529 410981468 663779529 329931846 951926512 753787296 219060904 397813310 448090152 344477565 389370444 713340829 223183435 298450834 925881574 521524111 956433425 855885622 586206610 431802330 146088967 624991403 712509915 227793490 718155946 618040030 964238011 771013631 514668610 358007986 181870421 590448137 54463679 125878187 762997444 358427579 296422531 346441797 114552429 173428672 849528557 513262954 363009516 891875404 593702616 149173718 737633715 888810977 381687256 728930485 75456243 162858401 259293770 797750430 429071007 293199630 903510450 427303663 352638527 194180086 889007054 993325301 886234456 81649435 699333712 261626965 651999549 701905189 523876948 980875794 141284607 52931118 67561721 596070625 893762885 388608634 158144469 265617827 215318173 842393905 396152941 676159545 345881620 75289346 179555422 986124124 718833244 430269173 998127255 88143634 669002085 533510082 714635281 382424365 553681990 842116228 502450215 636580483 307329087 75062139 850589739 926984306 915254088 456902923 70913488 913868988 153588101 213932399 251351192 752091978 458123247 249199095 356707891 683625880 463265896 636189388 441459661 140897341 859050481 880647808 87610800 179470774 308395035 509814791 566810546 358234320 186226610 405307072 188074137 159157913 937215520 340779958 960140998 936216882 655874574 243128088 795208641 369904748 482392230 973091935 535846886 42208323 96601141 582088851 883353626 804177666 59780435 991715720 183684667 265224120 385477251 531375048 171188869 870728189 782210220 304105373 626314143 301364880 997373111 723533017 29347668 182421844 93430766 946070178 235743875 473739628 180946486 262140506 57318511 272467796 548368208 132853589 879779406 338051755 685160393 583744312 950580227 652037611 874681029 714190796 171342930 418738370 32298957 234826500 428402673 843617630 452087885 377571216 421856173 347571261 29664401 343033079 747010360 677091820 419320671 917790162 295079169 213903090 892860581 517299083 705617691 876996224 525124802 890797132 855653471 813788519 393229915 484829198 675545505 336426249 442781 155971031 540737043 864974297 649340752 458509513 262810598 196158084 531106059 831994461 87431688 56777999 528993629 278877066 276783556 878192 377794357 109298814 770093818 557048265 693109020 119173999 574307563 603932076 323767956 874928231 432989921 95769432 704676309 69654134 10670620 456183441 614726883 513396017 177828119 30175961 696480735 625643430 82809327 856840115 979752024 874629855 890877149 816461067 928723452 790650343 375774787 117418061 435753751 119661848 545191457 850893037 131707840 771372050 208422193 868204732 910869775 423624571 532973073 73197364 318098696 917215752 670382674 289321699 283792992 439196704 190924870 370356702 613791693 717558048 155936466 309468941 885231834 889415768 982100502 525050759 314450694 923641306 749983625 382980929 467291414 947454469 544119387 452600642 722531072 861117961 722309460 256170471 514571745 40794669 469542026 169537670 829242711 496244791 246567295 137191793 282882589 665828960 656235561 228362190 572415807 743520625 954694301 886325791 781768914 288440635 885465896 255838029 950067030 16880927 723144465 716979019 440338859 196251595 568411432 238756309 193138757 592882039 367107822 835622655 663685864 627084101 270201800 923014225 713340367 408136684 80023453 812752771 621372729 993043920 254359723 980900201 910062709 35822430 735597709 916561490 330713139 74468606 16699672 86315866 432234328 475146501 122022716 726019720 299988321 207149982 662549874 386477814 155404896 912750433 632625637 597918079 78431566 434954344 899428389 414687013 559855630 316229165 738498675 979128886 700292699 517304377 629477751 629561151 292935754 63989078 395130114 467559540 395375030 110621323 778622469 210829611 563261085 20600880 171324012 922604195 38120008 439048150 862678661 626881167 305418729 302134096 478349432 648766844 464232655 777893308 753418925 722758364 540296520 103472648 376356352 291167922 203855101 315751719 495176651 573326436 407650873 206202409 730214153 512148723 611211343 55270009 610948505 922337254 238875681 156886972 698681100 395408507 549769398 923532435 405191380 242120243 194351878 717703247 872353079 635198717 275700080 237891157 853861329 650175497 52550823 664482323 500274808 987410511 615053916 932010994 94229357 552828200 76559186 304406505 613457643 310821947 893475533 834309704 932367257 426829810 113545862 829061928 279305108 15436576 200955563 772373901 115039811 593263359 498345888 327857189 630845373 665858261 42371693 250602845 420816706 869663744 958768808 837680063 250619429 148160483 537504599 275352568 181397040 994338567 81893633 279699359 141549243 305445930 559150431 889584715 114453880 774633382 865982925 111446216 498257325 600776781 659684809 530234075 658152710 816484110 66064458 798664155 60829084 808399884 110647628 744959551 127927476 616472326 453970884 432312601 590591916 500094562 472329174 592025962 353796759 760363925 869117158 47386375 870753413 600611566 333263888 328151563 740218502 870613170 776480703 654753109 341901970 917236451 801339048 641421515 182136203 763896978 662248160 196989053 185047359 384188768 545232302 88576946 809831264 158896197 608985486 320318304 666539373 920430035 48003716 62637177 116462551 43493969 109806828 370262102 154632613 655250017 695008031 632334329 306931492 791209227 247389297 482757546 273018376 535520365 523652900 376841358 903331050 28514795 63892331 435059208 854683269 853039885 688143419 464182879 949289093 427707752 257754152 254301418 901560346 667653940 123287085 199008410 253885956 17371285 780892630 991795711 417498843 535205228 330376413 844607229 224251949 557546357 582534412 964180897 890251249 284352768 435384772 63531203 332317478 218264028 221140185 481851299 121876736 214267165 899946348 391020188 548210751 502044657 174961033 919922757 972013482 108281596 740329460 339354119 597201446 643572091 465847462 197992765 145758076 82779033 243059673 382033750 343237589 760253062 270244194 597846597 866201949 940695017 15275317 443282874 472362721 130895149 525161157 89054786 637880517 761963691 467922249 382793948 266097657 541436591 311130467 292528868 646981473 699297842 230111073 682080148 179663484 391506248 192331455 329906918 664726533 593549649 574767701 652556225 448026595 55337887 622485809 262058893 803594224 510883493 840777399 850932699 680753774 447783800 175422253 317174759 558822975 902269561 398638189 547537245 625406532 599874811 220656403 664239754 642894486 336093252 606665271 648909870 415422847 985837137 709180516 852922007 98968238 60071132 388934220 958014484 489631719 410826239 47086560 807477233 280677275 736433734 326507455 201444837 641679997 897322246 954297345 859812207 724838338 479827278 30061648 117780875 550759111 2748070 458188009 94043883 548117723 148775259 364329594 848410566 754572775 653032237 338627745 284181740 343362734 689190886 937955351 264153155 202527676 898892963 403198777 682605464 561331159 329544957 541500334 228200122 595885288 188756627 662137218 173520346 947164757 242733803 719694062 933748577 490224418 746530844 473231671 565650005 608202725 248414175 15009542 87701272 248327930 663991470 415459885 348501503 361613502 572891792 637952813 691334694 99191612 418877437 102420121 806283954 623311513 780586183 397603381 956226448 660947432 686147343 427323013 66966639 665354877 707814217 975464693 988233186 61655803 670632281 969841891 411606651 495966774 178168339 416125228 586739629 868401799 662502930 769103364 960652512 732522829 112592518 649259204 55996245 463407227 107197869 976367874 40142519 981573122 873870688 946975481 628154364 962784309 870176343 839859455 872607823 406410575 753461267 330604240 874028497 47169511 596178785 139839506 679609117 154700546 848166539 303185378 19826199 418322465 610445549 121635884 712708084 905838538 265641762 157874033 244004682 665462180 107301391 902174138 92999178 434708543 883429447 513189898 496917024 543326707 343792416 813588152 620999662 406891697 716270500 809674023 432720810 773931283 136095626 905363321 669875094 699277270 796119931 469505139 851294081 182842877 498069325 386048790 775177058 832535310 222113740 499178611 378334572 561552204 227962531 824401379 115328921 852937045 462468395 597243766 21348202 376519584 226947956 931685624 346184465 805118148 968578912 585421546 803115170 247392912 845675909 552310347 912552214 863947999 831882495 142882409 664774816 142128998 959006170 75538881 175268970 649325832 675091713 676314784 665091494 142458262 75841104 619338728 680069241 835260309 426615965 597780257 570331435 140215759 475920183 365019041 973112417 863853141 204484794 453978625 373725261 616005717 42137426 455380544 652214319 535849881 844692428 930011689 704964470 854648237 572011186 1597295 399746286 977779720 139816185 188484218 38157684 697658735 600816303 796384884 958550130 202354550 524321459 697344668 140989542 117047165 21954015 888081067 214724204 298465623 413483476 252491588 669700522 386459095 503961436 543272280 963375297 429392433 3492404 404292303 454564879 677688396 61024642 568372700 468935473 418631675 571951465 435961353 924300792 443197037 398486558 193384579 465341945 722213093 303206832 903987561 299997087 713766224 757964312 690209742 205957596 135090564 245274360 675634198 638164682 609321482 703710541 915585293 450602522 876291313 314332690 585442387 619357843 924958771 782241749 941321186 344313833 946274910 590041962 60217700 457459413 66647044 709096788 206875019 137106242 365418869 4687979 959710278 459238945 237189096 122902893 595430596 701454227 517355490 564431304 248798896 373012712 82005875 156775381 959416043 873430948 914163352 593806325 755050435 210104180 708369843 848418713 555421264 493656657 954100219 974671977 973377865 219211315 248004712 503204358 780317128 196058172 226189698 928738595 559812889 139846135 491555610 395180827 250359827 854184918 22496497 121738196 820827656 650599701 640445943 33053916 318328653 974921350 172068139 935403419 321732926 473002748 799440373 435295255 750194968 759612532 219057223 417672300 426393520 176672079 92239809 873044915 294940679 110635185 171170394 543195905 336971915 952573267 848209456 88079747 554106375 920086628 942509844 421461395 613763990 278982619 278156264 190811278 956967412 23477090 287963935 687521067 303918241 189493113 835832674 705233353 55517721 109437558 73259621 307776868 525115722 527536527 481514958 68070050 594046222 54611168 849655948 520746916 780505149 389094024 722079094 719624453 983548492 283108439 827699485 665333953 217660747 769015356 35754611 84979801 745647900 740003729 462958809 491570878 6812920 780003215 252640303 572838745 562087660 476107634 973018065 686691874 499894101 473817974 436427840 569423554 299302544 125763253 357228322 145622920 722535645 412566218 492796621 684102333 70532654 193022984 849165336 597502629 900026448 778188882 582966422 995550770 601744371 460832328 961013857 944233055 503132135 318843895 496483053 434609294 408958914 710077981 771696991 220017221 667977224 126436297 105101781 190923924 460757168 602094397 343585308 132545239 526075894 656155372 195401186 767302418 889958271 420063203 892936714 894191087 689214967 283065406 76893710 380168935 296622977 319025388 350156684 354534532 342863787 558564153 506954454 996169864 712438470 490896198 213379306 300367693 446904132 968405146 442253698 635301566 235616154 448243571 406465720 762289240 328611986 749246859 157818921 950742231 24155927 269004390 742223447 714421339 41594956 80931540 629494429 343896996 950605853 697910624 327438694 561197537 894593203 567951111 735084759 959517737 564305096 119457353 630130993 653130461 826560718 45811660 73717950 730121723 764810183 257480779 692066965 669879145 973601787 50890833 659835980 240976614 303350911 316831789 884521979 300488980 852084998 607381356 397644704 598396751 938371637 339011410 433794209 384279363 328831196 76058362 185426199 676420559 655317747 211400767 440655578 145835201 569649119 290715900 383829217 146541852 409306431 947581359 339035141 465775066 416576215 918438924 13462436 93757870 901025428 944945123 936168928 783020792 379983099 900095366 918052292 716797902 24664366 165388681 886624408 451976714 287405420 326481234 812225444 715933365 784288576 972892137 369205277 932318828 558376066 81775112 651401110 935880513 856444158 695244399 183127471 127803731 42901687 496778425 953266884 391819152 901051992 315022899 414914082 507299177 949692344 894098523 44885968 700005575 23045994 89672013 532572843 240825023 941196066 293724602 958352146 782989614 162828088 718521524 607846550 366142056 23721988 620650383 617788647 564946126 800788553 802685868 493499769 155051750 341565342 166676818 446285452 837209312 666176790 736737418 715703942 720670172 202251420 243879770 491387842 680768967 224294537 38051107 18004332 296872000 772679576 27739371 708867111 231214306 914979936 890831811 403995944 63637003 397239240 535077672 828444722 22644023 973590233 922281698 130053842 313182982 534920231 392849535 261625 601716369 670677601 790615420 968742120 761347578 622971932 824565295 853390640 544255610 405914592 934555736 990037171 204143289 397917189 643529994 800427766 761679371 491935736 825334173 200908762 585237392 133904224 492459919 145405354 939306867 114881969 994097213 213427471 563356175 445043268 929702017 967081157 3197151 507128017 83140184 198959031 97678105 421660609 831587292 876255229 296114809 488417002 642541740 211319966 946123131 96327920 502593697 1115716 746106282 34304340 392032422 72020574 516231573 695787644 689577332 256219180 758385151 190729143 416573823 996027823 377872091 307552332 886616133 387621292 952141541 557584072 58706505 940718698 617418447 314005681 375503690 187960865 690568459 353362020 99075451 281852683 893638022 89767190 562245558 243459820 354051572 717643961 343643520 665332273 44527700 347297575 997185707 673014231 11413491 698218582 998393453 948974730 397155512 164875623 919803475 779720713 233928149 714899043 926649968 442908838 857464047 661788770 348581138 401400021 723097881 574312563 650002471 793314359 188829693 228227583 168520170 441780221 396193690 236927876 400856380 20168633 63241725 758615045 652303100 980957325 288088619 42928388 552554693 314934379 862412865 3510463 490266244 537617631 411300029 79850696 153257178 541640010 596101860 2194833 108972869 37663165 68929403 741343690 267387239 281046574 970888039 564841442 668231282 519896714 972144644 239471795 682745455 673934305 517029488 346697775 402732661 128571624 324097432 633571351 103547824 953189019 250463951 847205964 195892575 621495464 911762580 440022877 294208024 851846822 749497845 642836782 595718432 203598175 526875704 325247017 929857590 825762689 826434849 995625664 602810257 847133479 328677103 865251142 503408161 225631001 244726346 439032787 604860512 48304477 195899798 522055414 732417452 441517426 93935158 193248362 732747998 879304865 65545233 375951106 374103746 981634084 823338035 947693620 717461331 103949729 595328535 97524285 30448958 377032715 643275842 369985802 374255952 356730636 544908815 933450940 526971044 576119810 614102449 456151313 566743597 950507100 217005527 338960225 723097436 530082967 391728423 967170630 246183040 750339121 856981922 549818254 822521318 703230854 262029669 371406778 710382775 742893934 707093684 261771261 904130767 755004906 940896012 212028819 829983533 590806577 693106156 329669377 349878794 249420585 905712844 698095711 265522564 833540664 886529880 844691171 198998005 55362744 80789650 624824627 403116406 874536985 73792861 975995283 144768737 698465915 331922833 737048230 214013859 776702011 371141283 804854717 597784340 131970985 691322100 480248111 984981918 866110674 265203911 498692887 206406006 986086996 716461360 328248504 757926579 411923259 268988552 434926394 663406999 534865358 695568575 313017235 369913436 452763815 562509697 623623236 412024019 141715038 360705205 321029013 478105109 827308087 328296719 857573227 547557710 88602 592984728 977755345 547405141 209885024 972288317 57874660 607549177 488199063 895171829 523849094 999976876 547801575 316856281 853220216 743760251 459854851 650747142 463034955 302883192 26668198 916207000 661598570 586363837 47506238 758201306 782289619 745187825 327975542 283942962 127675140 207996253 300551854 586035667 998113892 827743038 964739355 852089367 181710334 117514478 717496630 435621377 935524104 470854431 469736005 576073300 822366772 686812084 871998370 803669860 278687741 385180899 974096701 955355430 204428021 728401545 381502902 438098799 101488604 561120175 492321499 830370128 852293803 335831201 652453858 213597811 107465011 637136032 500255139 823898444 127828711 835916268 635711185 84850088 729991610 118462312 696562653 178540388 632150419 510101300 253555389 14199443 631760998 855776968 670863651 86598344 196757300 633916485 240937521 616699546 150215198 548276870 238629376 413447451 813165880 999489291 122727742 174591323 60328958 741663028 411530215 728886596 366194897 174678159 143598667 935968535 953438646 800981096 516378552 777606314 55771252 736496573 917239276 238847899 965592616 495119533 517516881 857534519 455950604 595488356 426301788 333156657 120068720 90855556 41481186 884824239 456023958 27103458 691623248 237286864 230686802 558793185 142062708 287432881 133865889 89019778 266265007 252409706 53289257 904697389 696363000 754099695 432076055 398781615 617291535 680624487 764313519 449921225 463955435 395188343 733235825 652126116 337934495 820412925 842354136 213305049 469181858 860490227 864119039 349781923 964044050 13955956 634719898 336826432 782837984 273701740 600607420 207072236 712670663 892563690 803555074 930471562 967098987 408182414 696893184 577876009 974503733 599101308 34438886 284419365 14847786 72527488 128290383 141558677 357699368 612025641 690315666 726394159 168358835 286822998 435410022 748479900 552152916 250579675 925727982 797724694 512018026 618002190 927981099 735810646 559172386 901147124 660244861 692921233 326765582 932237565 873545379 845335038 665883324 458024271 307967079 276011772 953360541 559468885 899660875 714759721 818995516 291394432 15184409 356726934 815698465 648307117 154442275 938643689 182062122 808894324 803832181 869697169 987906319 859006880 533599695 483148192 471608670 601853919 358877467 769988977 651715166 487451495 186268650 445675050 780558273 309261958 184961383 173057520 272701471 389012437 208650511 124948500 257564222 199575148 883544422 19718788 44453896 193773012 614304512 432435087 279612659 700801753 911081208 13063247 351908870 803700095 369467787 772065650 884912945 628631007 441245953 59691837 898481802 718636714 585615820 347066476 771513580 420869833 103431670 714826955 32932734 898816215 183788534 960639296 176407131 365550563 66964691 10139786 657156722 406352688 704039965 545080726 581739420 483094939 900099863 844019392 151968635 136377351 68095467 22575296 499641382 732387658 820996596 999888460 43781470 860178138 731920725 489896932 84870718 696126609 424343093 982238487 987852551 578013961 406868205 445039046 125074500 462332111 161115087 504424701 645076087 766638963 639692121 4876863 114550848 187850849 387149656 864972333 726620411 160767970 541997577 734454671 402433643 704140526 8866906 609810295 328571633 693106933 299025655 316845272 307809750 638704572 982735060 893785920 935293641 897623289 947779848 542356599 47470432 511329684 153059171 706947324 974743410 457312551 619984436 503598542 63604383 309225877 315474284 479637104 237144373 211738717 280094414 332540284 779343975 183084123 901413741 95462706 813490912 524518076 500384781 264693572 286575046 251424307 820188952 475471141 271063091 354948407 372834639 675045890 531677366 227002076 946924720 166620630 345173731 862137268 896095871 544106088 841480983 971433531 962221991 16489491 518346568 721808769 46593980 623391078 507329474 701052478 79792113 343649092 496240526 309695172 145640313 108633058 678652964 664865249 289476119 409491465 709014632 21316521 141624807 367833326 191209323 816337132 544416378 922616585 51787908 166946257 439805926 245672640 578359929 486893542 308485468 808829800 9450871 63006201 611736807 792557552 85223257 758781009 133826898 907377978 891868784 911941308 857066247 905361598 428764894 154816250 598897412 858807553 695471312 922104026 776496833 657860714 272204940 417384735 367291092 473165616 169163380 892387085 27629118 99103526 195118605 779525150 589507831 281798313 62057324 360380827 180914474 25597485 22086170 1032793 806957255 515539669 621392661 925859615 76110370 477205160 322783116 986298164 186370955 84654318 992310697 450030009 985279415 189061540 688604997 343857548 769687801 589748926 421557506 652919767 457530889 404933888 41087169 136336791 331800970 492342358 109848936 325167905 907004203 97030788 61620331 409909340 517782260 649163366 803571446 611711052 768374600 50937855 2492049 342732875 860687625 535935047 889876382 480452400 715209695 193066299 576845183 910481303 901995972 713213950 394275239 19911453 423022393 802573314 110442923 866158626 282789518 465633991 358085303 295431575 283641326 839844411 665261667 105269989 219216461 662092694 977907195 980266099 557438672 169702030 100378250 463118339 806416664 477501356 186043387 48827457 879629799 727486591 910605262 688206765 353661201 778344027 711542079 849168931 547917074 423745291 87522486 587532313 575873722 98911561 653091482 331203060 718971497 816918335 162302036 167875294 847786737 159053903 580719269 693905132 111997713 735928476 532796693 512175532 234111301 250285507 643739866 523003655 546637314 616228154 236967807 758117088 307878069 664436722 712028110 616283206 439584382 686116594 727712430 419385826 211372431 512597860 227355390 930498596 443138729 455562616 430923749 273837676 724410038 830147329 155243365 874173026 193505440 434628628 62989285 814701452 326781764 915634596 28607381 488693546 760946896 983823215 785446422 430792996 308279346 943564940 736624866 776378801 937240665 717210918 859511002 287725475 309338383 663208573 641182923 298313487 662066609 642896296 345095365 996779253 815068693 549171787 20735464 291473672 212225373 654690771 689603093 738229309 478826921 99632198 89384092 824313767 554561327 376761760 700233163 96935163 134612270 339879302 826187210 581457676 488012201 953367073 32551264 618411309 459383673 851098401 174982209 889390426 604863982 682487128 854018419 319095763 429526222 578725022 989789427 363789808 823897123 108182981 691761387 818259424 531998045 40989102 833260268 968442450 834468916 870391237 18092766 921698804 433722482 86672380 439443007 636504112 969559383 747838800 51445895 898845144 894446145 922437837 457747757 219056654 95287463 434706414 275004874 234873880 566889473 103390541 216914490 895252096 638320749 606837544 161886848 949226978 3235025 748286169 759962644 902729265 622070734 419215956 665612987 177211563 455860509 116369826 510696001 959629517 965202926 247841766 984713165 608528171 461080118 956651533 971773686 759992161 732294792 602341989 572571795 588801522 299219145 980792100 325390022 624186185 985655310 316441665 674370169 185690458 310495739 402224815 188228384 259191719 896992629 510332721 301384432 605470148 115777618 879441588 382471774 60797682 15316505 856852553 169255852 537052339 452710737 983463127 96620679 654765908 609077069 270351709 341404916 294034907 757263936 386996243 937321685 995860307 933594853 356598432 110202815 323037644 621552835 112425987 644929176 789191100 67726668 556975314 511688352 268385071 507781079 537720204 153802767 562430893 392601442 207553531 24367179 970362872 491089705 264172891 126587913 900578146 430172493 363235778 33236437 348067258 745893634 675751185 267901122 460499739 833640338 186724093 418066710 673332500 200258738 453726762 487238073 387987663 543430909 828385383 406756648 861239674 80723087 109310182 424431418 510477440 875423400 377068851 51501471 180228283 603167870 4443556 102669545 620849595 68840125 115308004 296774380 397243942 684689134 610535370 643960948 3043951 343359733 383330260 792650919 307956571 651111762 634429683 881312933 898467635 951681415 883530517 349539913 405462992 342167624 65306030 785618417 842902967 951880478 130018937 449871255 809850292 211742509 726695719 208780437 403410293 882738523 258650891 620625301 916081752 222117754 135691757 601160228 199232160 503254862 224477312 706126360 564449902 183479188 431426250 35665634 561921991 497623762 750766655 996301042 852960845 514952965 846624834 606751203 754454056 401089447 573839741 469378681 724281522 955223603 189522356 914634698 624489749 565177061 613166123 122350167 94705839 307153402 549152910 845121670 608572429 649539795 724787507 471438979 411712938 525701793 288046038 381463158 684640721 459198283 519140066 395151438 317908005 314126596 884759071 895306788 490127348 265754325 160040091 870725267 272523652 678565269 107854227 396844430 193982634 609018253 742642697 69144496 937126723 270377436 378903298 239275888 728109808 308322823 933075570 306515809 516603161 503831883 681440931 291855893 157478731 887154311 985586532 43403976 593293673 63611654 410167030 917116948 516932922 148709978 73290770 458957204 310415900 811853836 411354584 906167795 187100786 344448364 516750806 875898099 531727511 763574303 114268085 120032863 319208155 169430128 52573799 744596989 189714077 80159100 441038385 165832519 499987890 708966982 361229031 832693295 298151884 78027061 50908005 451158623 905410255 828822000 812734557 956966451 173376176 115757146 346366396 634405375 431250418 490910390 378584690 307725901 871120271 271031424 647550217 712803612 739842411 903758943 750688843 375706449 302193902 214677065 265262992 127897774 51281776 619459087 394481751 468065915 41123790 296893686 737028593 693889191 401827324 264284818 318908459 283807066 309587628 80105008 615808243 189533735 475604640 229990477 155321806 402841188 361997667 462002771 399341979 17678086 36839851 847843374 460033155 151631446 23303139 40530731 869504683 906013294 804682736 431396811 42180543 942802412 773330486 364763918 200942181 371139695 572661548 177750705 507592494 887309804 786942312 478822225 569410713 171249558 60158384 651119781 340630662 885491448 417510544 272552676 947207373 20443722 549709501 824856883 543698375 419358668 819714740 116695665 411835575 3115629 259223867 355843378 522249089 937068990 729092823 489034248 799716102 897730987 130479663 962545865 486769486 203810461 51417454 448820770 884755275 684441526 619250061 127644473 440127399 358167457 648908911 988174165 75363105 51686520 876358022 858823822 63060664 673123666 924752803 953528196 138622770 348202177 999186061 871916309 113919617 21506930 676906915 251968150 733271462 119481339 554772602 568299158 509168929 241103802 562816042 298885895 492747044 843952559 58950911 707749004 601674911 584007032 203297835 665989846 551504509 891597617 951858520 40954641 791866372 808118543 334675522 403340543 143972512 31982586 110104625 317918272 198854257 983483593 474768908 737921649 981236761 75874489 429382526 354811038 372483262 360801610 537437218 550172907 867121073 701373097 469402054 244304277 532565336 567720692 408559641 798457622 567518148 651541248 827766956 132234066 207620719 680795634 156578283 656754292 460440806 803161312 504480928 172282782 384598703 718655330 771933644 331439221 969855634 536471276 180627560 624395504 483215835 289017458 721892627 76419889 847414245 670439480 317754203 226581729 624104698 526822417 420198594 663737479 199954497 354405038 704383957 113903491 659777782 739580231 784224383 909691026 60401604 353525526 573093751 250331105 340985689 419049486 994503687 426536312 908815546 940458662 79899882 337528469 719758577 266380133 1529367 255484881 118871251 452346180 306744111 984813466 303327834 437236130 165394646 77469818 353295031 779422011 157900500 201928818 540543076 791147131 209118966 970995541 666630295 650351045 725557978 488930529 785915504 853204320 429349709 146509705 266517748 700622325 113210311 244937646 577955613 308664795 422010634 654547344 17749342 128462878 565003450 37443607 248025601 942971275 437622943 371779559 321941016 318181868 824425344 5518018 431017559 823495381 165200036 992652808 581807347 865651316 833234860 58358382 850993436 205144648 390351936 14405916 497422834 775648379 549878162 456274422 15910110 498249176 833358486 134269409 468661720 940349163 819828341 857533476 977582457 951961035 873429598 520721085 701931014 838925702 870853753 364844174 908465445 728496539 262419623 559522171 418053493 555779565 343601304 896707499 574218500 709862171 981217882 383253231 412348261 207043447 721877585 33702217 94151407 900146618 637581650 819460876 369652481 534828553 708709026 578171446 132169080 130493235 507923022 563752675 944917348 281139174 358854205 678805841 416062392 247047612 271475991 639195998 830354355 673102100 261550120 386388641 309607755 310121673 389678590 290705833 599627899 959002668 885448869 401434729 453268761 904647684 20856914 28661774 516225724 117405700 168009071 431246165 877885128 786632813 160181167 623549063 352738646 475564426 586381561 457288479 841153325 54551508 825816256 340346891 575431647 668976160 496694304 14711713 741525943 673036525 755382860 100256178 337154057 482525479 726033768 967272831 526982847 581133876 512482968 598575427 539664967 441148977 456550645 38259200 305302467 101945883 807223130 505859265 980968003 617089398 900073300 878997304 745110398 600955314 292748315 928354944 897594545 986417172 525464773 297012929 273913567 788832508 214223882 242921671 816113986 517412807 28763991 514146123 193860054 605422014 66343795 537149423 467521058 346350073 267140089 482737472 618503491 457273914 8994474 487943902 147690406 791703937 957795200 299024635 687203074 305186583 986294946 661683979 907279835 754057006 798007354 943425417 41857519 216223064 705586542 692384721 300493541 433318385 273962771 721129858 531265679 149313663 245502290 163505761 721912016 500885688 201836337 393380090 891232194 348542730 597226253 345990025 168840103 900113682 150372118 377854400 493900098 199680023 101256192 899605617 136430378 257675408 194548467 686174146 630065688 466697839 217046696 999561045 760798200 855902403 164744619 473201957 446615310 904114567 157512764 764680544 264626693 504352905 167828548 81928092 772497840 800263757 304483643 217188564 767259204 881349945 587641649 454477008 805833121 186651510 974652297 219113989 209212792 576204426 533706935 629489471 656466693 264656780 463032975 977242076 33482714 659686372 525379392 178993928 735430496 344088914 90376901 626418719 684776978 678653166 132522768 841274415 19535101 579903670 30447044 405969646 832053600 855889392 782543148 149601538 289312315 520752271 948281133 306408498 844425628 728101963 609145441 48660241 880738481 328550913 150707309 604413850 957738706 381682237 103502201 990932504 320062873 579846497 364093179 816616657 665144896 195798250 872766563 972366829 381272419 488092576 199397984 245543593 63745998 876227750 254425989 977695630 145395480 355741333 687448277 252814733 849907717 376902614 534418773 398565841 683688469 287689855 668056205 406538966 544871926 453340892 156283243 871164701 769684190 45568145 969821735 786252728 948365078 765963722 605753938 768792087 521504414 470098419 582275537 142160541 363840878 632076146 110426054 934222951 182807759 185743437 956150553 50430659 16938719 459976808 473225388 960971062 976957696 190770571 727626090 471455377 374950284 19265737 515397071 307214555 745173489 36759134 228015409 787433438 749026108 159427059 847070705 556266527 781684976 599995718 334851072 387565246 243638939 763677783 690370991 343916926 389288002 369310299 911352899 406333981 551799667 43905581 260004738 615968242 581492981 273295951 336330995 556119941 223716414 565135579 41713581 899945408 594314153 850051712 9167937 453068950 634074928 847606887 306768310 978252974 992191822 682839030 668552955 446318471 162122984 818489435 301429935 986216222 826883615 996296863 922597077 172156355 288759642 532558809 373302272 343009957 894318590 11509505 648464342 986899500 19616816 605029963 260477015 740226971 771131748 331317688 764113455 471507380 74994800 283736388 244187900 997802167 325967108 192736328 430760028 975372237 942280017 955500502 996969706 800752863 145903686 555216419 657892709 530582764 330400968 10466257 985122730 83699234 124655484 132373959 377279625 782872583 291359498 180014110 436919379 372588667 89428645 12470188 144167691 698087332 505534904 860502882 294719403 836672679 917165530 562073414 512015976 469921410 63438261 791023595 390654455 79817319 99522721 632027510 968990098 410469732 690975748 454112447 652897028 1980120 682640642 948374382 481183221 408714959 666166779 961040860 791845852 982033832 60257056 150467857 309698693 243376837 911895024 299243584 764019805 921953340 182810189 7627040 851050466 943012269 87851013 179010429 197456741 599442941 764186165 75997057 638190747 726735234 439209573 962046614 116230411 858192958 87661353 839243210 277096817 108321850 132600092 542293949 723043696 79269747 264508323 302356248 512078467 643473276 757703740 462699572 138559292 916401657 740074494 525069729 586950285 213822483 700226642 141537205 236512320 859773446 446487654 723751442 651862016 658167712 292232855 887918242 314581321 233703836 894908176 988356447 607327890 780797534 558458539 694796664 32055376 836237597 480728664 503262839 528500501 245706283 395692933 227566659 119258635 228429905 620049141 969497437 397707477 462462799 848144980 932544134 499050050 853629675 302036612 643980077 564608380 633581475 24179610 582768016 836184159 346451566 291576556 321419581 953019053 40236673 441004670 872151386 970062808 304599995 849151799 376276419 555739504 672745621 250404317 152292237 605766989 86213522 469335630 117088012 760921295 543692204 384701305 400907786 108653416 353199143 129641495 325154594 560025847 269675421 476245304 296505771 60802419 749942286 461642922 68419452 350279802 106911677 818089804 78775464 5576936 518797709 566805995 281225157 351399144 338396414 611489446 986763871 746127270 478327655 714772953 359131673 357446761 707444420 906712642 690335709 149540877 252994033 326614160 265545373 738186099 415864764 616778811 539305575 174537536 643687207 780226329 752291627 229865907 868011018 434577390 533156588 579913519 360793434 146288703 27049029 697076561 937863824 904129203 956149423 554808017 470898586 729397862 119558611 763650499 263490231 830049560 441743116 142776326 509847917 872702703 920711568 341949559 310728319 652807409 427586368 442545044 34859331 211629269 355512226 922992961 844713363 10656630 336284179 167836147 80951312 71386340 991736168 608541108 920437119 262706009 267074169 26274506 383531642 658806676 909688070 469987824 362608 326508010 703903526 70268600 28370524 636123421 996913827 416110033 576508353 957262822 75837351 251775467 551912441 379269082 467105254 435912505 878723670 654603596 406062594 96112185 106683310 203942777 850101604 453064013 657019431 998174137 517171794 353196432 6929784 719730505 763696542 164746069 545614111 770559190 572399074 194391091 804813382 340607104 835381614 639899218 890688805 20632316 858742004 394333801 579848678 437082699 270793599 132060346 552733956 909856703 893609677 86890375 985846631 124956392 440525792 840172157 973926324 994132822 467832623 421957263 443474753 642200189 765233141 574154065 871935975 363265256 331364628 291587111 880057800 68758106 137309096 216993591 555738243 59672970 6655369 500772245 199262855 673940428 755962845 25391039 858140221 26288265 733216481 145957533 874293926 139700014 900964045 799234410 601543022 766349919 956340511 981614343 7161899 133442485 179901567 704893035 957806686 667447983 448351304 708365210 500177257 542184106 520404152 666596008 2589645 455675277 578027982 409607019 431560750 423104995 904559106 92862019 603862399 29080284 390627470 1370331 362805174 671160189 28687100 590597714 819580015 648068857 915785344 200408058 282433254 481051019 92621779 703376857 939525575 658614318 569564265 309493230 148575347 435562030 219466813 703568740 10033449 864810367 301498800 168004989 892245025 426271662 723971399 520909547 453782954 984401203 621857469 143291937 518302478 117580824 13168865 953319637 697641246 754312364 916109535 698005662 769420594 664157655 90963797 406794467 748291214 748056277 367524768 824417765 192191208 477645872 430672386 149332269 73912683 324752691 163132812 946194686 768825527 723637290 616291838 44191657 355571815 102447710 438898074 457576506 961570000 983626312 685782809 697309124 559911087 993389051 977629800 364671150 299121660 527128712 313883384 733184684 250806979 761117259 552384894 108991410 903814470 868832379 832308236 495237866 945007528 462753425 503529621 438290313 782058417 529725343 635593674 149264572 591231395 89428406 206905706 568254848 286157141 478830499 71557234 221694719 56479231 606234076 384039101 486362970 382167387 451459143 584643332 95854284 381215767 25958281 43763732 566377111 149756205 15375770 104471830 760475486 255649230 278798844 945014510 554647923 192813496 277328731 721973767 535690490 996554578 57444550 942076423 814830409 60705809 565228006 697336079 275960364 68252042 65476312 770801522 41448369 140635200 575033194 117622163 708240718 810346860 584044103 953112099 280950937 129981014 708375599 823400695 394529030 274375006 206967613 899670160 459249021 437568737 489557370 187396028 664293816 714347106 885719316 844930060 228356202 303861350 199205092 580764525 794756137 969812596 620449197 353359236 774274101 149971194 337039275 210970999 462432848 752799587 637512708 625018086 262851890 190840932 960081123 336160026 311964809 944744054 599763865 10818957 790027660 7680884 656187283 815638169 900438941 367355663 708375574 795393768 954763864 252137184 468964868 596243415 824071674 362222930 235573351 70934122 803693976 294063346 937763425 997842557 274838337 37255614 269086278 328822112 611434201 166490484 857857939 798875620 323909039 501404220 599992678 751398660 952975060 668040547 725094308 3729012 90006074 309942056 313139110 665129257 63299928 208225550 270902088 528587051 571100411 405085325 338181890 382944103 390156420 382140093 789184394 148221150 240255800 336120841 799931644 334619221 808868065 772966073 535178731 377042274 163310632 871825810 901115984 711246048 561500134 602736816 29105090 895978293 198660446 586178402 418049869 308405949 334898393 938638613 214935871 941911317 158293603 198336521 671346275 476251128 300402304 277412339 384726231 805515981 369046664 678476642 262149737 58358782 3501129 604608975 231377179 921101505 651784808 564440513 625513289 881604181 563272378 980407080 634831497 268222168 629638383 205441014 40952910 892128792 296687228 733580578 873821951 625070767 878499167 704031273 581893454 807021264 800989872 246277675 268245014 959259627 416853982 424047783 381282913 952528734 268408739 203510474 770608996 53975123 295623547 355138421 231052860 321808747 705777591 887521336 894707305 605928116 727804190 130329905 715065460 502501922 23829837 549041704 88036448 703967144 418705488 662134406 152482976 607241795 688534914 379697601 618240773 847402363 944328006 148035208 926597669 704012385 569609316 556551602 579492975 502523361 379291668 886067154 648822932 66522679 211257150 824523294 319436702 318172209 433904662 807389205 377783927 47666825 876297752 306979183 66301968 802432615 554280285 43478199 124554693 60630810 367995173 780238567 546824838 360063826 989009039 90150138 822075929 365440224 61140628 689576410 957767577 716108928 312728050 711134674 319299292 494436226 707680456 851366848 236281732 657677665 211435729 700762439 745366361 712081884 685759199 659412382 419640009 674999377 809810975 179013443 70911512 829399641 69366138 545602389 945531305 66887900 901395279 178834718 617432594 502115068 277372413 896205969 925813010 898216902 269165480 849334894 173301053 374025415 745132621 535141653 823908039 958248576 545738766 90336711 421578416 836691978 790321180 992327995 687457223 666269340 902931082 696941158 286720553 622652824 51764139 580109650 180258167 407478808 497242148 657019909 188342047 339331307 182057872 519119150 611154277 133374402 897459642 435286406 400176950 490518889 894242767 298415082 931960988 57161277 820286113 394765831 350811565 570149631 902107769 815123704 730731040 225536926 568736320 113650440 951881505 143094829 1603196 123507727 795947359 803304591 793244906 856590218 585494202 378496632 41330874 418131448 842861531 259604247 370946775 725119629 403389415 525013717 62540851 993407462 32078959 402392930 90510885 881991294 68235896 639773905 706834001 292547641 310969739 724450107 604891747 637832755 47225035 434631050 955929473 739762500 34670864 877081744 275800416 202359241 450509942 878502800 477513226 716372218 580380694 336533572 151249930 437530092 721410233 280127380 889450723 22661054 561316643 474176090 932864614 958284591 321655230 391763153 212157119 589889716 517870944 704042284 865479591 126153042 466527999 449969024 925181950 174298612 122278415 147586411 204862717 416479747 422907521 241832538 993693037 608496766 902770784 472062132 947403429 540623893 338572009 896352940 477623053 833950303 28865468 279245926 967325280 904485735 102143780 167112617 21170507 689473705 963609471 210388359 19977764 528553152 323539639 117185281 469949851 630596163 479792987 774924908 618604648 980060936 931562926 940136813 906301534 446336950 666475117 234707743 102473965 99409549 638119429 525876169 915234073 222762213 811746061 308273844 111709692 221414925 401013498 41732037 994812145 828875016 8623018 409982438 998438921 553319025 338316400 808850740 79266583 746813902 862974752 793542845 912978981 924780021 90093626 815373344 351635437 572185436 733654294 300210127 182786416 799755408 857268610 44461706 557661662 395601198 100838919 362292599 11978548 515023895 910219270 380257937 230482530 480931099 411530559 185875954 868330704 406157687 511966207 249120694 4790895 432756707 836282360 38220225 963191575 933720755 490220636 949575627 937246442 518172332 646263292 581400720 872284647 831913210 45276049 635140909 353675668 410117557 266248379 448718630 798398821 324070593 132923552 961824705 746891102 149390572 27178479 411801428 358616950 147594192 727061796 237879050 615922362 254349950 391003834 891931711 74260697 370254391 929406224 243363843 713659476 930724604 614325672 631268082 103401190 967116558 233028771 425982114 54664365 735190533 191634971 892023238 335181824 111315388 763596036 220997190 779170989 316198730 843580263 538500236 667131600 711207410 355657330 326623771 901417114 740622492 42590573 638398630 411826657 262173342 34064127 905069448 845420404 350391477 275382988 769858746 929739234 107523204 821824348 595676942 105455943 528946319 532444034 2526243 223177031 978622947 202614435 657161 379092006 37215643 774584929 478818368 806967459 915951929 804428656 151132879 880177574 890311571 705656825 997543219 360145182 973682875 875925889 798498655 728650023 67059535 165510427 21450643 869337073 447415016 577671177 770504282 226073058 29653931 845572253 927917216 314735508 570106282 7271913 136529222 753669301 162570912 66760204 169045459 858136419 513767308 949577159 504245396 989147872 719661097 944801669 662354578 416636868 864987768 325230751 637928978 706677781 357072023 36552262 158601253 68418689 236493865 527356348 638144016 216993080 123278722 430581226 990963273 121528112 164121741 261596350 113153542 929284862 652063852 740853646 152346282 906499388 669354574 174306709 948175987 30127071 495690892 709569347 685880968 91507206 304282756 211380443 340613088 251920121 228551894 886436245 75175697 891815147 940932574 241538556 675626114 400171536 927070305 254607469 515461223 745145310 725392145 250375892 752597689 365046085 666630038 534760380 276439933 658845621 121932577 21464366 602560383 303000894 869400098 286593843 628743459 291938817 487146003 554545142 674701376 839914274 851270415 53891459 665018957 633314135 284746465 27631086 569364615 39938893 359669289 764741965 848529229 52266212 44778925 905237576 584985697 149771003 600426176 130242794 556494664 706947595 932567679 412038757 636075829 102691271 276569650 730295910 965206093 667630211 877798499 792864943 305696056 191691411 832737179 777368550 55194362 942430444 178359963 957660016 936145873 78785798 600369975 869256210 426678294 813017956 610858316 250283664 116260917 664563174 992835572 993145507 904149631 153669003 722071675 468872858 114114215 831001986 631119987 61508845 800583430 852392882 301791733 179010844 436363877 108720657 689897639 416537920 416044138 202101267 590853213 305567313 85614917 449792155 549421222 133419756 598696648 814331464 340371114 688745909 954148959 899673552 876712 725705886 954454611 715871928 419885219 898186170 268195450 779491046 503522497 55902269 621330331 493592908 300229478 933588929 945326214 630937341 51521559 46773436 229295642 677654177 938842349 62040346 135336371 79575771 706638560 80772700 625745818 997809089 322161037 496541783 21769214 699313336 862412884 916001587 119611974 343125175 488523397 19174270 22725245 325244216 664638532 42170901 620869409 546876749 739461580 3869262 890600869 654300164 117061051 581925254 287001712 72763644 98591011 867887429 356190686 187353611 607927100 502862417 597797624 841194512 577969345 380036374 469630080 563471787 894152218 947917201 19042318 77328575 181670058 206333684 880727743 305252748 245667041 932264807 589561485 557795237 779246249 141690932 468724289 268307997 319077595 885975477 493714443 859630576 399511576 515836198 729142236 494878937 416992384 357638114 599210700 699116875 243414119 761997288 739807811 504344013 510745872 714576905 589850000 774301688 738594140 122294371 849704203 147912281 121435671 4602712 91576726 675091218 22459198 708010438 48546836 836274183 698145598 59940725 749225303 800122631 143963073 681339906 133837970 416809552 958362760 42707027 255485962 196408593 633555162 783903045 976386847 415441467 823904267 151670790 39209918 288922563 670187326 550477807 166169359 673054922 761206497 960148363 172516018 356019821 308079313 632056670 132749472 218653920 854041664 545256318 323776109 639011037 15390710 950401865 768469035 719578579 960626171 425915748 36256039 34987704 473846313 305499265 786459671 721289576 266010027 679137423 219097128 715053598 944867772 1192477 425019014 876546289 824272269 516281700 291219177 98038522 196642090 866836951 541173130 516635428 523070474 285698785 822196379 67753073 681429522 772038501 352838646 935634840 521262400 261841007 818491557 157166130 63866444 297411718 101016832 485513 877849679 299459343 537105868 659472252 608788953 720504725 839063346 485468772 551049892 342111058 528975326 970162084 687460236 668147073 301860259 93775153 843334713 648909760 263780597 875080477 166705367 60719244 812109891 557806176 386754318 792643285 702188278 718538246 443436766 816294089 427791514 343839792 140676767 61254863 417923589 406752243 132993962 809570892 174081543 876843503 952447166 500081111 388079880 710206377 107625358 471620239 901979292 140767728 905700217 364575253 654242889 83673764 928437185 185920985 318844292 843931848 703177826 768255693 928877965 74614189 999585169 236186659 130454608 784265088 353694845 791131240 543545996 929501643 740999673 465763396 588265882 471895382 403008268 105444317 628063222 357541940 199717158 629917897 703848757 979936476 277785259 129079919 783672358 634300273 362143426 925171822 544448638 768013525 906367668 805873720 633531301 409183199 278171032 797349407 393830466 802980881 614604608 917264596 137888798 854273780 837740192 377461392 424491385 638936377 162295905 813602267 976862790 252816749 898748479 870316351 697734284 144494054 802033056 169126815 614599892 927780478 713391547 730998720 86544323 521012759 762018416 656318837 544195591 39912331 865735058 121956601 221507006 169121086 905167281 192459287 232652318 669116673 621543980 911934181 520374545 642930088 9832362 364118839 705751122 780670700 842103358 255653091 246233566 74762018 360017792 538754325 3765230 337386497 565941915 269066609 16808013 46861084 745576992 162352778 974623178 374626816 60318077 317095349 786003693 383600819 663178163 293181882 653870892 696458696 217123804 347774944 293610929 897663062 957930002 33907840 596714687 320545490 618366544 996815664 251173504 238921021 373031449 773417907 13568270 293439350 840078151 481286334 273680151 621293829 41123148 372850334 58396282 940660126 855410538 967645032 889600943 426685210 20198679 3688874 671158897 491965064 463377219 245444514 74068746 522100285 679021476 36916318 766082414 876233536 247169497 215519411 622264820 830351593 618292149 904805979 522947159 630189257 281632826 502898163 88267839 385966289 24995498 505852975 687132352 309312756 260826745 62031595 923638792 186769160 717170172 159424196 329353463 152278122 135628376 861500682 785747920 687880475 160958144 535094354 548538121 274938863 656444460 302754743 240069660 707002829 743692624 992140072 809873636 137115545 684751232 916980485 160383866 243359649 207849624 771900201 860731925 724373685 661245994 893512606 613264286 788629929 467592081 198058677 243018856 299760687 231713747 282423528 52138538 782366818 360198225 687081318 302725633 973646638 304557536 705183135 620317743 777146687 702223915 60408343 761117951 831473688 608758948 448717714 621453537 547892752 250188783 717587303 905827749 800144645 917034822 67192510 740466963 39785163 109312451 356615773 932976101 783504149 989870588 442435742 537109335 955852913 322338951 362961253 636493363 234149751 824248856 257994216 137823104 265802867 251650532 341764253 927441274 291720945 791325804 266654051 719138681 26038933 554943570 93482568 656890151 547778280 869138280 919084113 776389726 875065352 477538737 859395705 630471321 346629264 844821413 33823569 176812778 413626201 90105051 623569369 496100130 60188461 984749485 7511697 353622198 587781441 723136410 472270410 251563880 641926192 718843356 50924230 735569918 12034700 233156860 886705377 918627350 337028257 640237657 677161405 499278322 786594874 818116271 714526458 922580331 86835321 641611553 563482070 788725275 821467444 889261751 330469225 193925599 644572238 77730091 475506577 622215476 577150581 448879184 954812534 689353 604718959 701074022 694700917 468998190 221905070 502542810 351194388 315703880 937139756 91172176 21076059 957582378 480480487 649037903 349061933 581374749 107057586 832847595 706731541 100507547 298085822 583142659 995115888 620582745 443914803 477313599 875617520 549201591 794989064 311695353 105718785 979662188 467964402 874511668 43547072 540297393 787835968 730649992 523754823 171274138 931671999 130923444 711109733 24410748 878742223 414401620 660950630 537073504 681111185 515301802 149725679 192503481 30899947 82185383 199387144 332278487 795117424 60211639 653969563 937547711 677537875 240408334 529422559 190841811 389366520 490971012 993038770 766437203 205895109 655453149 267115425 200431981 557395107 134850936 128597992 520092411 470690638 468522756 253562199 391323568 84300457 258463501 517707055 390855068 635092369 769486084 930985514 526173621 250736027 499272049 414387670 989852816 402229516 83916349 887069822 432437626 946910733 664088421 201063618 419278267 266286832 419862958 536953672 204887458 860256112 704227714 523527390 494320701 181123688 217036524 169881498 375482540 163167616 788313249 353939082 904563118 345950534 480208598 108353181 631005235 480806293 609872011 646032663 700649109 329442290 961232211 121025403 207975612 439131431 76514089 889246102 264026788 467621600 655753868 909914769 68903936 807192889 77089882 26461022 606486421 735085454 377105295 264377801 806827725 129242062 165901953 556756190 908410879 83420427 619378427 461810706 841648635 655097707 356473177 339975519 399616616 139607151 795550362 358307476 962879265 253326017 381456789 19693964 274700176 383443858 398153877 329550582 181764916 961151840 94738289 388269559 318793642 122962729 756876759 955684635 221552563 749019668 18580700 868002430 926756135 199662206 947941349 838680150 382626874 459064923 487096936 505729209 730977362 295010811 509061078 897743801 233244606 138066101 676971908 313229786 124243752 932037936 954363458 289031908 852934999 704185071 401989829 668123656 776221211 70040969 488419585 446737082 764347054 561702221 50160047 726835378 684847753 64290278 814257357 778822927 692221225 519951973 766764022 883066581 885132520 170176303 17446348 16421960 5415191 704606026 242786824 349613070 902120320 212347418 490102879 935463537 238834973 528759846 206646849 85083062 225597829 235067625 794136293 259454629 804353569 436007116 585086310 947849493 117311017 512104973 315334283 773240287 647536834 677132562 706263372 495130475 899868185 788815609 921194126 432989959 334322235 746746316 1070395 374387658 244525314 827932423 923147594 953038193 624197885 948930996 154594211 58914489 222509838 196110740 206625731 631215170 660091352 182143580 300045679 356610110 429283383 541634962 189860873 931585201 230358115 16148709 257743290 345652390 474894110 886186372 776456705 476558661 895400899 907387507 98043877 125952812 63691115 58844819 31182125 608018056 696390132 169965441 836915208 654637380 645782253 727405083 763882999 712964217 336654596 887592063 788988907 802435770 344946645 963974906 762573243 554107328 592788327 792405004 898483715 781888023 580592729 892539678 313832008 333320161 197434412 566122070 624749975 267881188 954984466 25290488 147475466 965922916 488981807 389326560 128914707 472278892 658497188 567801396 195148579 746284082 91757788 534813633 216698756 496196297 356729840 963034932 200209865 853703426 720205113 851723994 385142674 81112436 523830075 694714603 602999320 158874837 511346531 771546785 644078656 811119740 164802794 461070487 674763714 778554006 792939458 124876320 77143423 902037297 68502427 330083295 935077358 945973360 434407276 949999072 103810719 366765470 741288409 207787593 362453654 622513379 753318921 806926804 309654464 21697989 819016397 780946026 770714491 287673210 615357712 92569126 423922625 847105570 760284725 184722228 820824487 698668065 775778974 534507329 157214300 927102656 173897396 4039567 587732701 462736832 589874033 123574959 635596496 729080800 81912269 964725665 46979572 135341780 236357042 658030625 642123319 728972415 7300859 712263866 337916723 342702190 607372023 151713534 635458486 111791007 894045879 392308577 174184013 464877622 528406546 376599591 95637051 630275172 98936558 366877602 68110297 721499774 680358085 940037460 767729645 80346676 130555275 255283123 584671114 102883159 786452706 456488359 927211588 923841062 974235283 964097080 368257758 111970227 194786458 737209345 219873597 927324185 653878663 900519877 828862099 31656534 16463289 341918103 287810209 674365771 705316293 490485047 297568656 852348212 317201536 247940676 561943627 447252253 495563788 210216214 437754034 775574860 923192594 215530423 247807024 653456987 331331970 339366375 388235868 77571096 606915186 599443298 376792836 569071849 779171533 146444695 283772507 920378493 66880944 185134781 672184942 304061898 809709765 666459781 161126870 333172421 233036030 220543550 547261889 265583722 332157431 535502979 178915740 21644932 959722525 180735655 457048569 905345734 527727323 614441408 769734377 803923591 29550222 609520644 58450814 356472831 239632055 812459882 483273059 941013155 852506915 88645246 26772833 744083876 382689505 325023256 594000648 298160326 241949736 553556706 930932420 898925907 824618891 145435833 188753678 267142965 346442739 58815721 151242834 972821658 432692166 6753351 6548614 166020369 961343323 399990358 799269054 23371620 834957018 41496163 686975545 155023732 191518125 756218881 278763206 840235820 541387713 501677371 558301570 150342598 298782895 706746817 109455428 510331347 774140187 126016750 424482860 359403044 932746546 662027408 220720569 508371665 33078223 101570274 508133334 450470294 936446186 556169402 508764533 211356951 102207273 9763063 842084839 564910464 850054775 321842536 805120227 929027685 189977353 629795646 493833150 155541823 709108558 687407741 976203626 894593524 375133277 133482676 40781320 589648824 118812263 968611402 684681541 213451248 88974547 609375996 604965756 193649993 425313621 576358462 272605356 398816917 106139934 671957650 827570113 608998222 663638374 744865734 351363200 934611620 429323807 320332246 721704346 50050054 611082395 619693990 808611911 745243288 131078123 967866748 8265376 358710406 448885422 475724081 386428821 374241875 529489224 819999497 649266120 931565770 64132942 915710092 456246517 933831537 932423837 700454710 772997142 611876313 260856244 43618175 899223693 333123184 357776530 39110844 195160422 664099838 1785909 843966849 765318498 643362509 59681680 32461599 459754082 995208904 499612133 420639262 626102000 61489023 745908411 318045517 100749906 201660753 508229257 194147822 676909456 724102869 607591516 916231412 642691940 591019198 490326342 320254212 451209320 710547811 371380808 642234113 634486589 619616528 693110620 426941942 803846553 776235439 540683162 338219388 490228659 46059209 860305316 281106904 990383679 598347340 74836590 19222988 288335251 380829898 380701354 433379242 67792007 74379300 823562359 456220879 841343660 340238915 342018676 889849830 825851553 316469002 873504716 466737948 989965502 280394565 961727371 373361878 621408501 804225281 522956526 153023236 356521247 939168379 754834599 765719092 64811494 902838304 961085221 923052240 980267521 603310250 115533366 380042820 636460864 341481819 608753265 382665956 79354556 423520592 124429913 112403300 707970942 980899137 547699523 324271730 262424770 911447522 628272259 296054516 958233084 842910437 739661721 848140139 91552594 250113792 411646756 986419787 222086720 596511798 138154711 72961881 13635421 186111282 18807974 146921356 801951246 306716954 640325268 161189508 24830918 961641329 24196859 600687945 809304967 236872279 361779386 845318735 819213061 527173121 749225165 402251892 141146161 660907932 837909000 998890362 748310585 273382230 206951034 232535601 139967161 632307198 144432490 51603462 389770977 120959174 20592400 489257227 597400516 336329186 909253591 829571845 408059650 560527314 815277621 282628025 743154079 981226210 29104591 933921419 253211342 969025173 663253052 233136935 636275044 229697321 602650104 775959042 491983750 77850589 236375721 666964779 667094715 542730287 572335605 489830015 207344054 458251185 276762001 458157383 887170508 73634617 708352064 246042629 756988476 194755957 611983703 249268148 922152102 442479730 869800655 973092998 883906210 41098119 18565441 679806108 272920434 379719064 378751046 772049085 217753660 780154197 585404682 261889957 178517440 957157562 908044753 78456577 400343641 650421586 546346346 334721372 368989645 610782787 935345813 921711157 218648352 35649746 902756988 235760702 992738007 72099118 362348241 2517630 376358549 276676032 195204480 923180310 129131999 647535635 15998459 256808691 435652797 672121701 137960363 799444442 591178356 511496828 767964064 547866341 425132316 321272683 833113042 177404248 353988681 490883150 954228054 968485437 162515684 571949015 491081094 958657012 944244513 327823545 163095083 422179838 721409969 785247397 460698480 7669425 501697024 368766467 275166886 312673140 980986100 582408766 209654818 369406296 621598046 796011246 792055463 136010340 364955312 111729956 360608645 774060924 399306148 311196000 478883467 32260018 826645275 892130810 565368097 312477917 829416412 578861681 137904981 958175811 361076068 636183287 461815775 644523545 851866927 136471340 858681481 398965185 389032412 288267955 943276812 580652318 627026256 631123276 308237358 223729476 530438677 774048263 263373642 511555203 479037226 734540822 408985967 720373354 863113952 257514254 419338624 805318337 183052266 271348978 447782510 749848866 319715588 151843918 713493152 635705234 520114188 534115833 972057696 250975416 914977814 308185996 567479930 69662207 502322321 957246555 527267027 890872749 425693935 599842713 936265143 808134779 844981885 945414643 291162597 496480509 357900477 999295827 746185643 261772205 380769010 603261200 708224825 704761908 519425127 65932187 673866607 162011283 765651179 155156941 855238701 792788989 140167719 250833116 981755286 703229531 5007082 517644640 2016968 949326682 420844472 82312663 405565493 101130533 104028440 348077453 141028680 664763218 293620697 463914709 802661536 129593344 200822890 455118851 468499100 952823975 79031337 379575612 287674663 887069235 470221761 438803069 464832635 181185148 242868544 250331083 720578064 901885424 352998623 601429797 313550672 544502305 491496322 490452573 842810542 409445266 216109353 958593825 756133856 340387180 219634630 381902469 18316002 649632472 471828166 169086248 806020341 910320208 218503274 320612907 279549808 619780178 139983067 550973613 198804676 880679737 854525485 310573231 486094469 615901925 144161004 31709474 439349785 274557634 438174066 808265596 687049849 796523929 546891121 527999586 238202676 635603674 211733877 478366444 624427859 331873328 665832708 565126374 169072671 118178753 67937613 330948491 197561689 448041516 381831800 407164007 944342998 564716455 308262153 485106483 255496312 366655579 556093296 994861425 574129549 416148910 579389810 322615821 944529343