1804 30435290 195564358
430527798 99433665 551381056 935669959 938992464 271785209 315518400 411112492 846270812 500273132 369431520 546106956 581047637 1069619447 973159996 1048281247 1002110149 129607061 273992131 132471689 354392279 108166520 473397981 875498388 658840902 999168000 829137534 507435135 228615666 704522785 693560205 343111111 290139558 279155870 925178605 519740012 1018708605 777962304 522260296 564875416 887925436 111295653 1018215511 916366079 785157634 1049328956 525636670 1058736457 900160534 631227227 222254789 482684753 314637598 489028641 686130431 278470311 484160040 191643627 684310386 530916352 616198428 245178392 528852807 963677672 233933518 966288248 605692628 926037360 725854469 70004458 96298841 844003264 634948852 631723651 497287259 1052934003 534047849 661079272 462494208 239415175 1071459658 727608598 741144445 813118297 376826765 167476527 942319322 390143367 996483180 991422461 1059073276 339903651 566566591 199214185 899344316 540101279 641080345 498287972 732428694 312243969 593363341 571573607 818108984 275461661 687639643 887183939 236698953 820686921 768082642 370505899 28175890 597568880 867977860 572707595 540724595 295256897 602630520 746672053 819701010 898132030 75785649 994311281 1064940681 216662385 1018553225 573012922 1038886395 970750378 662242923 390716308 22581419 271055087 845181532 835961387 96709045 31530942 397378066 519274073 550775499 531148116 456464518 455300335 968432480 894118263 104689217 125226274 224731914 212128594 218771427 1022816296 968429643 539432208 473344337 911637953 922391610 560182129 420465951 338539521 217119810 72018593 999951659 581195324 844517126 448126615 312364956 505789077 671818951 578762649 498953197 495642633 498390760 271418717 711450548 336512008 484768195 779564491 83195429 281320554 1028807821 486018542 458001682 1055470559 767118504 280223455 921452263 704857054 188863936 278488959 393765379 109023709 905021830 1063529486 741055324 709840313 374363433 811499854 214576497 955723605 197341792 232630814 862386712 82205010 155779987 684242886 105933954 369047664 420717548 218122985 358258619 531027790 933923987 941318732 213875467 637605225 997137703 926185024 328618798 823819168 820768567 814116280 151223429 570261066 537914064 827264261 41006564 842035262 881344442 121258678 194946766 236117336 907956626 1010844029 894705564 460996036 1031327551 612953113 743624325 1002011409 961031117 232278689 665470574 725923088 94466942 966916801 753606356 468293754 868360721 122131321 970523162 959222421 38811748 297203892 1061624724 640342732 810983605 235015294 67538055 120344026 781535238 463274701 675660824 817886395 591028561 326678458 49023817 843903213 593978623 873876599 925904612 803675385 654169265 1027878305 519210237 688431654 1016694578 675510846 296470692 924709071 876607881 50448643 534472321 619106976 974214749 244683464 942707322 1014905340 652123564 603026800 824756070 502734807 380872583 680263151 3585416 733509577 869153113 158716750 296943788 562650779 482152178 130093888 283418196 106514870 78946629 18953274 600987591 762744554 42525957 567266546 480603369 254358384 293334300 1029352825 38842032 396975074 738104979 423189321 839048506 912089533 82099558 94763227 921997614 362203961 1043526906 1056217818 73704568 773887402 1031478753 361906871 1053499401 436931315 272173382 37377675 983593630 113415148 399062933 718197660 213401415 186930789 106550111 782794081 1018584296 981193069 906280218 145143940 735133594 309571652 983070486 923840194 1035354836 472627873 925996148 101601233 152152311 20691826 260799527 136986284 854742964 71958672 105353979 740482635 466224014 129040202 327926073 1030716135 460187398 1016198111 393034775 26830077 104867632 176873719 15320710 950296766 150725200 535802251 362918973 587133131 700028449 419927983 310714294 962281231 332985876 917717268 696959053 678736861 393136878 668858121 325254142 861685549 405881693 953593096 1062697407 582060852 208207878 280360361 378257178 95035192 560382170 112731523 585543687 202445478 994222863 278210718 343647113 152611967 550715335 281725591 153155139 145963079 868955311 738350376 642495977 390916741 104695548 562498002 456199649 1073237233 763062066 51293122 946299814 225083562 565709154 498308783 878672402 716549147 839510407 880098828 1073041374 291940869 303447095 595201949 84065375 731470297 619685495 235081676 396533770 404570316 384704086 637752862 152665427 340507860 111577979 886155215 846048326 354706647 95739794 760596471 832353932 899591729 183251441 533967055 478233059 375327889 858260245 672986 913617488 771177860 342566134 743218654 582893177 390008829 537945231 326121870 591859733 1063358061 454944495 910440125 1029472872 745327091 568417054 1052271710 672161802 960743980 118276116 233921264 791997348 492984436 657596971 352094072 177449012 890660969 728733309 1068323567 790499650 751702609 188530478 422382832 714145415 772890635 956337027 701807943 626103503 101217972 438817837 287375556 7853871 19067825 755879198 936258503 793614033 45726641 1050827769 825254992 833925617 436460514 334204775 17578797 996886910 891514490 901621832 506155622 173569275 513492594 685630473 134634562 410356716 861879315 210915824 253468735 450383345 96128542 337836580 219931602 1061767429 445191042 360923424 767100847 352774282 796862487 217022527 108378456 470463308 14123291 808590957 609553965 219060285 118974541 501718956 636932102 980784044 813658462 896565351 54875501 643772098 11482016 284241298 431894385 864204188 343736111 370902505 1059686975 235712836 791553462 565656856 60435219 113272010 745923663 514985089 904389192 1003162806 624805245 577304723 835470784 972971072 662931482 421578504 592380682 976496830 629704428 369890077 478875845 310957134 699810914 906935226 301996936 423878707 818754346 572413732 1051544210 298026386 614051215 849909957 394504679 697999652 167545180 265249784 413767572 393453934 155457551 638672878 589557417 815657732 320620496 129565152 738499362 557379009 531322096 877682615 193620622 330455484 274297505 986881888 587432311 1006547955 988383138 605709771 463650993 627350852 450360239 621711312 416326908 775266662 437982186 839417119 967356215 52112129 895517104 160696920 723844362 707730068 330650506 228238255 189706770 349450359 539572970 945796689 568811263 361389335 231770642 1016882438 260333820 717987895 775409693 704981295 325706154 471770020 580956512 729119494 33321470 266481724 819032759 525588194 264381939 248821615 513141176 207358893 1040084615 660996375 416393947 889866431 784215041 501086411 348056093 1039495931 164577391 686231628 153756113 717072136 426307160 619021719 636342785 168164692 75259057 626252012 455887171 946219551 656161068 328814619 974955191 416486787 439843286 1047964125 212882719 78885753 281408576 565000809 1022131676 701965535 819760086 835093923 49912695 375692983 172936437 866408450 15114580 918560640 62949255 1056705754 529266299 132544200 271913355 1072297569 686463486 707878529 249986023 889154297 927231642 282791146 903789211 183534573 600737000 1030229190 446911246 505564753 463146943 620785191 232227483 296110500 64018161 928965486 852243072 895256988 661700468 1032799892 94675458 642400272 65357287 782558999 769902598 788105097 472786819 84227746 1061468666 748907435 782626900 123268868 997439060 388376389 555597661 578362209 1063908240 602789726 479665339 493712268 1033266248 872198475 521599323 853574012 670752195 557906266 236768468 253538819 940329796 385012976 926539929 393198183 280368728 219166405 1056455200 634504870 354033607 689319231 624212511 642914813 608822758 936782522 977068212 869232864 475124134 542452836 985903416 1011697414 644837255 511030808 1018740100 1050420045 329704372 580399798 199225794 528392751 476128467 616537746 238757702 482847009 171024660 88658464 748379887 141158955 683452741 267241687 843761616 240723297 89096997 290432008 576076135 542541269 853932151 906985826 711790073 307992519 893460633 184903535 578596353 450100826 80308344 903058393 241941235 9743464 937776192 632454977 338382113 1032443598 517761523 758766180 32532413 945301847 453740504 657022195 22578518 578010641 95100042 529197410 535015314 304606151 283153275 748302701 892460035 993386562 989434612 465344074 462416809 925502432 68170897 499944945 1046112316 178530411 39528394 905083770 875433765 876733735 295901621 1064772754 676947510 469846180 766051887 59734511 940857794 364349685 937972283 361605587 1026482428 412811678 155451100 1007428886 114110540 203186223 974966072 910063374 926447747 729885100 702262615 826381540 356383486 1069527030 671197004 867397898 880908665 166918978 95661583 1006804949 54410623 600082337 381092853 359314304 724453949 36522264 947916883 824313745 74069685 87372638 307339424 254572279 150646127 663299081 697264380 256554203 29762304 185016550 1034332412 370178561 33908258 12856493 281324055 42087063 789733978 562196431 284156645 827425202 961407793 997810673 862179481 807799622 677812142 234389444 863944270 315154461 422863943 969433370 979654278 889543124 55754281 1055696592 705051445 631573640 1031874678 39022185 872759721 778659370 940351224 837793914 552379990 2259400 959446841 377068714 411809882 667212469 728263425 491130128 1069440817 497877158 935093747 305393035 505387955 707986517 607136731 435597031 407084065 91450667 838909041 99694119 641813793 631091744 507138545 444449628 43358106 681731712 149228979 551021395 460110161 71687057 406463557 33862435 644632572 991443003 573747810 250896621 871381521 626369719 235495480 675336571 1046059712 784102344 1018892528 1038061259 52522832 295660176 598324234 694942578 515345297 874695964 429653709 175762421 528229169 388584101 737052261 545675643 1016681740 484559058 355510502 488575155 612977824 51396001 722535637 751355580 709445720 246066969 290045440 370984366 295946508 238082170 847768703 670579496 955536491 585196196 40325929 71967610 843346612 107082043 984770790 96475037 865632572 839976998 100321826 183572043 95857639 374930442 854029436 1066065498 427315712 866422206 587146697 532501649 299225114 299270518 309150434 461739547 671748950 189855225 506644961 422294128 73094733 718828655 1043774839 439439367 297758812 381797945 765333343 317453173 908541807 335759286 1065753699 21242551 535111727 806547331 250056803 549946683 63043949 328349443 612775664 770420197 1013332097 206464398 594933583 202959884 142132663 7020838 272730940 444502576 174993478 531538609 1068258480 108566868 540146764 680686103 330174363 621317203 318866642 708482263 641973923 314290346 921878079 155026652 596346460 215821706 734312491 277109253 514602153 183539216 387259828 766559476 919801511 293593321 971400326 1006014984 93533184 833170810 583254981 1050267461 500781289 882010225 249265773 199192971 93899580 967495292 133437675 108026343 772752837 730793558 39512068 1052670767 781571643 753733120 321455978 103985385 1034727004 543992685 931007122 396323227 971792882 958185269 110577027 977775420 376521647 1062391945 998532224 946022377 161574030 405000831 205125242 961505082 793228593 218587128 663020603 474386876 36922458 701564967 818351713 1016610210 771361467 340239053 885800776 399186787 252805751 181229042 402244320 502088540 1066920655 415363820 621667090 638653673 960791631 258053817 686752595 344529934 205456856 719907356 805504134 558241598 194974107 783610453 391126696 847544787 31907763 282209922 564786582 640580358 597819408 763783232 514784204 776323399 563473588 824910344 237143874 856454136 647088418 459463121 1003971096 403632370 658705810 788379633 541496611 336938967 71890741 823671471 143227926 413560754 266533351 263102401 406732904 320548786 431195540 1020664276 220317052 242979151 335983095 629657787 137508949 793690598 220055223 160581069 159921930 692679138 800224909 11367465 800517229 817326279 587888070 854317418 194852714 357730602 822632920 336246752 465773915 216619543 312991321 779132850 260324780 410733404 70022074 731045429 74040806 264361632 435794918 565061747 265074494 919564703 483422533 632618051 502810223 528703079 696088631 872695798 537153697 832322552 946483543 887044052 435389569 694944045 89024673 92130118 386760623 355685684 791698440 549484615 816851837 1049080395 60358298 694931587 881226909 429333067 908182920 457736253 232604949 266396787 470258004 639162290 729806869 335592978 609161151 69431137 83225997 236006737 923993014 503473269 108353107 192909917 774893565 784384913 1053332214 971705020 366847326 1032793129 945070605 652595437 1037869334 233947161 451100384 622214983 563812115 835033551 211631922 806447191 814234330 676372430 545764908 991963548 228217359 416819912 831845362 278727616 268532237 920695680 836600042 908671792 971166870 774882301 414471318 339866833 166933644 770268775 1055078961 75180245 648404568 663407885 563695047 816965165 216773706 9192739 769894063 564460145 156338225 89945003 632504186 359955125 401507066 138635038 265587745 43485856 763790687 1041190736 633435500 303797970 682129752 410051922 833155232 854365961 708706290 894445926 693581455 311511055 232418878 346893932 665618532 55832854 73887934 433824514 705489207 443258580 805117291 124722839 962217202 994170006 561727003 795588126 779736544 228386551 777997538 257779043 451393358 973136870 236894369 679101569 720241784 684685241 326744477 665884770 319716596 830114854 980257417 878304529 1054380833 267601163 937988996 214371793 1034392100 313492713 241698011 171014075 372891097 497840574 75837055 167258914 111696303 706825693 430442702 233321590 469555845 773648133 800207250 724542826 849527788 118500353 791789257 421961840 488877148 808220614 520437034 895693647 660657658 766199128 75571254 909306426 488355009 767290524 171135208 925976138 622092430 104134065 763545994 224950156 1060005851 729561485 449755459 704767696 509926994 642505536 676674739 112580081 935778640 879171268 790072788 888849359 795937419 739805988 414399732 961057338 1028818812 258046782 109696570 1013893654 627626199 266474454 624778048 464087371 853647268 1010860226 103956809 310616374 618085201 422574333 782670998 456997848 707427465 613961550 352044452 657673641 310897595 651392116 369386232 1072811607 878533784 913808781 1049291783 454806937 146288359 485035713 1005240379 751785902 139286177 87916942 265572343 587229726 137424348 23414452 912355058 961121506 510151007 425784155 328404256 254623033 394671301 426147462 337896765 688670074 457699747 1033566588 330397302 202487507 302073456 372304353 437148386 37493022 285950024 924364561 120925300 136800937 61755140 614267106 48304341 1041611534 80315903 516071622 400514654 256789012 952878047 622649619 1004478495 706686558 951619965 539716869 26849874 509029174 1015876011 788253610 287165905 582710352 969260800 97747465 227907002 119031385 75276135 326829765 3605213 165323412 549001107 340605801 669290136 839975693 145349189 856719931 123878967 593536128 404376314 112455828 92054569 674643510 176760700 991918977 468804071 732709863 45137721 680823686 636208992 371391311 397848802 782278421 218178422 34176968 606011179 31581216 691020272 144059961 555070542 257818315 991556971 215932516 163322680 621605969 266217014 292576951 243796014 1039123602 311341878 584412017 121874188 885121238 984623593 496094879 879299505 35660876 106535304 638844890 370890274 727443280 235793309 148875401 985255931 789409952 689543282 553025104 161183516 269145079 125352945 853057198 382519193 308198817 48087048 502329164 767843514 884152847 428865665 924733358 1013785473 249610598 476252197 246228452 479081475 162362724 982127831 603491464 729492609 919038369 673420570 1015158950 406527590 382356274 811802608 92967940 333289642 422993114 1025200722 768048321 997496976 493147359 966815321 908547538 121770551 873970864 435011054 602456637 678204647 30537907 953084254 772612046 396278295 482517926 705698340 854797385 456225849 1073178964 618207693 127342238 172619622 593603636 45182485 790691679 588560899 601661595 803337888 294635371 893695382 155163110 81002186 454952222 684858587 364746160 493475199 392868064 846490348 450997574 718493021 962863558 96026135 206391503 632910669 700509141 129266537 248895488 364927513 404317488 362470055 373641242 26952622 971301803 504727286 229006487 682332721 41071058 833937022 910677972 382034122 352593903 513325984 22611213 460529580 358313247 321104668 776197158 477580568 306556584 981676366 503949179 231334525 972666237 603795445 524009137 111751216 458833620 1028169926 922374091 81962909 167296502 3482668 599290700 731508490 532887472 742231033 121719121 384273342 773532732 44789699 687215307 871867671 591563448 730037827 583264308 263727063 265501587 378400615 1001068480 834225435 923816251 592287673 498624839 436984394 772812958 388170627 210001564 850701427 432361892 750004842 510306648 688522771 890271512 957010090 491755768 769807190 616801624 823254205 760071083 16311999 710241548 1036615092 167420979 1026994617 496564903 332617754 614818790 112151742 259779980 269780236 460099372 888080594 914813882 853555339 345222647 535422871 7856772 165258914 363493171 1030185689 233800125 1065818322 349614441 173302456 751899949 215001271 535468005 306120973 530752678 552319555 1042316152 988225091 885628203 315638086 58178511 1016735286 591173824 1016097733 7824077 933508688 79270193 809685885 919657593 58863082 820627408 34867326 49016218 892612619 1045426446 403053789 277563305 365083166 592748317 629669051 980326117 655063277 482793896 561014569 636968868 38975349 896166965 492488630 926492889 322114264 512522129 437740314 1070531970 552858646 693019457 162308197 1007974069 1016150943 438234098 256683552 149767723 563251089 85990248 640587289 365743380 844211771 615907844 743450734 635381389 790716390 738017058 274862280 752397362 159734366 981521440 336410438 1012920342 664115391 195188636 125124300 892313869 976528842 992902910 415951032 597899137 798505117 374312170 39098906 141071553 236287007 740374351 55385845 773483527 891486017 583275115 240310628 74855792 643830164 632824792 689137430 489333792 227900679 172559608 65762392 127001916 544812252 377665382 782018905 1060797239 843258362
