846
790525887 565847420 845847784 962543160 293579661 909224921 537202217 641796263 331563667 539751089 461646573 929872738 375086811 390160281 347967585 461793202 541418037 158890472 107293658 317686842 367647212 127307644 359373750 666447858 605292761 157541199 722659531 988920882 876764848 28318732 420721901 702758300 187767075 541665478 818510291 955382531 863113848 694975978 743012334 828775608 136429997 828119031 764360647 234771223 979138254 712455804 835910240 429401470 377403968 911675198 594242218 450506214 37688506 957496554 148719528 936368484 467827885 890754159 993332417 550406705 967080775 845454818 117155653 397228744 196656943 887973745 999009276 15977159 996045267 675876457 74294670 273631218 633372420 211791962 363867935 674733985 599151411 281691768 399150458 907203279 882409678 643736531 95242267 373093354 423592347 83537672 944075967 946462092 57769157 753756612 842416012 565014434 437840518 256861310 657940293 852870636 299936566 415662891 271132042 277779180 569814229 988411319 119725181 975584045 826736878 224707650 636674417 630280534 654345914 754425919 749801426 318411692 727692714 558343037 267117421 246019697 780587525 2269924 265255728 150449681 275133588 668044302 246716775 228467342 835920447 880481728 167423000 528958889 128145165 571812247 694425001 304627128 276916407 182299134 2038416 711589837 136670186 975739091 956968240 215268379 364775288 36867797 13357678 709399680 586366072 978571730 758201561 839512395 642278195 12931714 552788607 642895439 320854547 761605866 244778523 886156695 128724409 185673219 307511943 593777686 814088310 697419524 266635382 577417074 813512029 822436019 651900185 830740770 927255930 637941462 235969383 980130415 500025604 951659700 174461819 253662589 350022172 950364146 127498454 212628757 332494520 958319096 715954104 465085452 368068258 785904988 12524377 539422421 55496277 660018987 245114623 187260301 607953807 916799520 805035877 86529401 883979673 31325636 4260389 676074389 627321399 572736956 597584243 824217883 273596075 164947457 442413848 535779251 50946693 442928289 249642963 811741584 995875591 462977846 412336444 645356020 804292017 307386377 87450835 548663944 102262612 383698907 982546654 437045945 369907673 277367997 329572 999273820 475027341 768996524 596653061 811357381 119433163 65796776 779889805 34673959 548766118 967946020 911122957 456345178 802766777 57699879 3598338 970374872 132682564 565914481 370715052 975691052 74250446 613051501 28032204 272966928 429530356 882927012 221162514 320710870 383720607 54916347 587531018 278902828 242972761 602331890 364301371 375881731 261071138 557800916 171976399 861148939 578268747 71689546 599927085 227256430 385800663 450518827 893301335 190258623 400016452 263599405 274607820 571791506 785601692 693931819 127047726 540748141 799571282 507290666 76883059 280999466 281418498 956460370 253004759 349325864 514822991 388599274 991218266 35691171 389857852 946754369 378163481 559303608 233740236 225408172 96425440 50004613 127633873 417381107 575023502 845804740 18190988 566200331 21363994 111880524 224038051 863702474 555486540 724090357 674209487 976899133 171652845 463713671 526683296 119154563 338341303 20021035 773855721 489198233 62586083 9282015 599732652 701549820 833970549 866720651 758346387 981434075 583412326 806818654 95678256 332101830 857234113 407819062 702304718 640342221 581625711 640750314 663041015 43053030 2958932 935339393 641202767 630345314 938129658 968044226 989653504 683651601 665488612 251218536 696303616 368891780 574729790 473071711 327404122 511415100 189207791 829301948 482679217 437090815 559979910 188511688 379941393 515224450 559089563 520536927 225876269 947623631 188178576 417246077 473947398 293815891 639066158 630306032 48224147 161714619 332243320 939683910 135394630 160506821 302702434 537091417 426745923 895130887 473690106 334464862 391642731 941269841 662369038 531297755 992661464 712818518 931118314 30352829 336063721 667521381 745791802 864369736 765455846 799490042 121153988 120181682 517837431 257141140 439596908 372937410 347573210 803358623 491520771 355647976 77903068 928057095 358602931 16078777 953269202 600827693 953282930 443945636 650808683 77045002 639259043 764542460 638622922 683371494 124309780 959044790 713966361 915775285 620439001 500869841 693058598 717013262 942293584 197339728 171067401 954572682 298168163 897497095 65667587 822697332 324928702 664197237 563133290 241516659 353577569 918219581 511364917 820817525 980213746 838108746 716917691 297460655 501474295 392731283 966582244 480568700 204638700 349036380 432872490 548070887 677938016 682259648 29712748 59784704 119037480 130468802 325703045 49156554 178935627 880647418 701006761 371856054 617539964 996202989 594720787 660876540 884632400 404960451 388388063 756308419 96144933 376422149 887775867 248833856 467061338 902207604 839323875 238577949 509329390 649648066 535342916 230198190 281888624 316084853 112626762 46387161 865952610 98424301 126276142 749676470 650380581 968896163 312261237 246540751 154474211 930840806 752612851 970638682 299391517 950848168 200219837 690142116 492737995 708623810 242175912 420038265 108624212 136921333 875887069 770786395 62243004 356743012 957755451 836707747 955186720 538916085 801028516 260832996 219050604 867043719 416952549 588482621 138722719 565900831 686774749 837700223 115377220 900349376 621417235 109099302 904726533 448067468 401660874 544867166 786810856 645176720 888920315 511311994 906948913 747915447 251784051 521919399 122529631 366832798 866623444 671036403 94457898 768714527 779496729 47204554 976769657 730418133 588874189 832756355 847265844 532541587 73940111 936564753 130882436 843920688 203623819 473968066 394064077 521025886 229949070 926121642 21652997 289728671 937125779 887745840 483653825 44451805 63907556 487457518 423782017 699734178 486257311 145936926 860784765 514244508 582965198 935547158 925546684 148331106 593901772 370652098 11003092 312607430 327585639 606146695 556206456 697267854 632945777 373741477 787484407 351117956 541208038 581847823 606068746 897573138 764744548 241686792 321156305 485311465 407709087 285418478 46139325 104756975 309874231 19892920 128387285 930365406 674612501 16317448 116145507 285661991 766010248 322570164 920301463 439452325 397123804 34275597 258908828 680820660 660634659 890709795 420527733 340489029 713559173 39057008 192977809 47327016 4474201 162644203 211014360 733632851 293203611 966496802 687740780 968037354 936919222 250559964 116327566 434779166 476921169 387842092 612808903 297886622 902593174 876881793 917935653 77856810 30360828 998151599 994420674 972857319 685735689 408734282 923096166 612956532 139050137 582104051 25357037 609331507 128529146 170488124 805336981 989545786 204678458 581033506 462829543 969356854 833829373 490091643 249087519 246634093 466613006 93345025 129716133 457208374 766191196 32558597 843058426 375205040 537007117 638021951 822583952 132255256 284722248 115113381 325426328 425476250 115948931 716598159 541899565 709635097 559475374 614833991 299744490 719935009 957347905 254048024 820387785 801457464 236113150 740778868 316660298 885209805 26534712 603513265 677396046 474202695 213785348 208712890 631700327 787441983 447662576 986415957 115018958 703590234 432116375 64987732 545287110 94850042 850538159 591340043 319356965 90425802 834621800 20563858 260327680 560666419 135411931 699591743 321777837 512092061 186098350 674982884 149219963 439939547 690165897 606876882 382516450 235945683 69213087 640307855 449782952 509403773 229004709 545057968 195311076 901449955 769111670 696446413 219275803 712266006 588080497 567082167 282775089 855386444 859716786 328208859 514778571 497237739 462899340 878326371 625536326 577143048 780880017 336326109 721546285 96608366 84024457 964615205 756040061 306911037 442154056 316385235 198371508 587011523 766106577 764366043 588592661 965786505 276210468 792876815 959029300 626794789 253749142 87323158 867176348 786371998 24721544 676136887 511790907 277041645 248265431 163846167 529010020 849735164 17727973 346765890 87629630 380355738 434884283 846159326 594100313 970075011 535240572 434537008 244718719 132105659 920675908 172690064 743668358 72559153 243669709 955218636 555445746 537846022 250862798 807961277 281403706 19800118 988948942 232890449 466677577 955987435 480431482 92162065 
379721752 690087632 472372851 75647483 190901468 275756974 718115294 206342932 628378786 661529588 933121797 106664348 56781707 235071508 307707914 962446828 439485469 621368989 842131404 621320474 545501834 727673684 794472206 215372528 549653187 204082605 193476766 928544107 370628735 391019621 346108426 709585720 335233139 352147173 631895472 578057760 653905866 67015056 242340867 87807015 284996453 68470107 703931880 118957379 17666688 181924916 448983622 229427129 8028499 557193730 31026144 761433859 930175844 527281316 526259830 695191239 222582113 275344858 829549626 771731277 8123423 742922114 196880920 102444119 775444186 84016587 672373365 61592579 317182395 354743709 68346964 11428193 188552778 568081982 758863875 650483089 344190619 650443315 593154016 544911228 465026060 448726642 574479010 848561666 477178743 891414521 858414875 151591485 392336176 136010083 915431113 756512151 642216252 513076971 300077988 94780955 756669623 746126973 677131363 253332788 774301849 386717690 644909767 39713787 439709667 649672805 995744953 167028508 762835972 52827380 577070069 573205267 498810583 235032771 418165502 16802362 727483028 199267400 231155127 374759571 742737877 757567873 235841579 394520847 135548745 561753207 885286561 69699879 544444411 98324145 108534154 350928217 163958907 154648554 162940987 866781826 891729103 476252718 482575717 657617866 69396139 30955820 525018972 651904232 851685421 405417485 738062593 220580908 38623932 840697227 692173498 491536298 224930095 664136215 258883115 476665391 15786625 676782553 985661898 831166987 119155581 340386816 232888881 711184045 75621715 288906556 437605300 432518924 347405624 192876427 496924765 695937488 92147100 473688859 666730735 808122577 376834142 822073780 505795968 346871465 240058656 18226000 537392117 777847586 748634887 263036670 496260749 599128285 997149102 517863594 80412909 383102397 68892023 859766163 595949095 491747594 913776297 889434824 880197475 831214580 515499217 57635790 253247712 114118593 861291499 104560947 720305636 828808590 5276213 535724852 799739441 63930746 435341123 25772681 94270942 471793116 465234059 715547293 561884789 903852576 836231825 462933979 759019464 476782050 4544598 240247648 44787098 454364204 739377701 224611739 155939852 559048403 438890565 513697702 390130827 460427257 367479900 65224366 287834877 244293269 690792674 122389470 78708554 305074130 555526332 311414204 930179641 665332984 101992444 54505341 398286615 387224145 792260600 670755555 180626631 919976482 377511967 76083074 717043886 729509047 120645833 700822432 12569059 836208595 674634959 308492250 917728111 312924647 604864528 99308897 854136212 245488795 579595077 342369320 595819667 323073580 348752949 269437272 243850230 609668812 9736455 288676858 930381282 485725420 873947505 453333884 225976782 619351077 107361 862377587 784469727 309846627 859684651 830505503 395460964 59837563 922868065 262219775 137513270 224065238 861876082 177046073 858610155 454898035 237535254 737563165 337772903 138989794 294265209 156829503 570731694 425697855 311756151 589026271 184582865 848004851 740873611 337802908 83602444 617882945 568836063 86431745 520577765 29950375 132276985 75829294 510208328 860230422 195943812 868373453 819140305 809812569 905991715 21554412 164119129 922247018 347054615 811603792 315690532 486350224 754567891 19610849 653198725 920723573 34831478 137217064 343716953 205540157 656465760 277371483 58023573 309428187 427237702 215909956 845123520 991954229 672093003 749174613 298784726 577614825 862388257 175192490 385175699 282936569 229244322 593076915 567054437 800903118 525530661 369355336 683671789 308680973 185330762 943675581 182206352 65419599 779587488 861418434 775101119 553651440 817133458 125716614 434986875 116190388 219097829 151283629 690880416 478672186 68368773 198521672 989659735 239334496 70324377 34496962 891941473 2258417 321892835 890175559 710497569 818080717 191564040 98142289 475208908 25404435 715748293 154247074 164869643 434374452 513618397 566552561 591647608 519304565 60507716 951288630 581062612 473852674 654461878 812015600 449387866 827244207 41487597 994755829 586142429 118297670 748829690 617722788 664929345 671781242 678582255 608870254 682325615 365824792 975075969 746214984 724444102 640030118 48868511 125376993 67136175 54217362 349575618 843379581 587623855 267252926 157883483 694251662 876243600 807202365 142814230 487727793 911345756 540295280 71507394 809649072 645058960 669803175 334412309 490512754 900146179 332343363 200776697 734056864 613476964 69012091 389923646 781182737 759996984 293998062 707903799 831533060 686382169 816766802 252344474 533502385 591810059 557969931 297993902 806802525 8651292 960915791 993562453 535392875 116860177 813579749 384614102 192322437 917874864 75967380 484323222 61342652 240868959 163774087 140044526 53438890 120843206 692388781 826467693 438223751 3227705 95318142 207839660 822977879 699705327 346323800 711085502 43510905 761644208 608000535 317083790 668586071 86146385 164714774 241437361 421444371 415506538 387767119 180032413 69931578 735886692 69121433 462127719 905683385 681032025 108087148 915327875 563104247 275583491 259994836 285775956 356485403 156943660 559513400 901293356 474847734 452371198 632927566 76384402 458101053 48592095 542807465 875151323 248045218 239576035 368822892 842214529 609749916 597880491 897387423 943920303 680500974 274759704 887539615 29838585 29972124 441949861 561288430 837531809 303710992 617653072 906203665 856496507 116349961 102376740 61697807 731273528 330716123 433462885 499443848 152983322 149997980 900889948 54432292 60297405 105379728 860379464 219345562 431769449 365990040 368043349 151847733 646052674 928268169 423620830 78740091 886392043 878844427 778761594 190072025 648425717 715795412 784604364 651622009 687877296 276993317 684493153 180862406 277372678 236451520 7462139 356535217 161411961 561157082 614298380 28316221 887422455 380001862 237859620 4730300 354158464 641203892 44736997 736393529 414672125 66017369 391300974 400422409 604427777 467129304 562454026 514036341 887798046 965773871 891356709 723919058 796792475 15064408 702690826 927613191 806733237 844531326 101988687 47004928 55623794 438774550 951446684 955930989 764469305 756900022 66310704 533135950 354542160 948438990 283562623 688077964 819863804 617927976 597597283 139691158 785947175 686684230 231160347 181246497 376831179 254823405 386492771 376926688 866255023 180736594 241657963 912021310 454084079 60598864 263565169 805299878 443068182 51156692 715977570 29383507 238315175 294552722 149226631 167649486 183381296 681482029 190916733 439453272 353378238 251693344 623535339 242288146 185379166 173069527 511517742 199689496 449111721 955984348 389798712 8879357 952698987 966484842 343121393 687519451 94175581 840027254 324764177 801908171 435250793 139654208 509153338 960040235 965291854 752620366 297752555 909683981 312783926 740641063 769035837 635792193 540490412 36092842 34556376 428522807 409809066 283955600 156406858 709738652 276193426 118558774 142657462 820110359 514826105 547804270 257492313 174039371 393966056 631570669 738011056 540413420 972687666 443147140 708349467 739678391 6848346 852907578 428887579 892061749 766216850 300644676 429572691 466491343 16070351 530669350 936501176 429486181 205772982 757350544 70147542 91405376 247896746 579971267 47274949 71081922 976304451 708527004 561208441 81432631 953862857 25857036 128630318 20011219 29515486 353590461 132251775 102459058 408840486 834880723 641073914 1771034 137610401 692311542 240593412 19984817 779624074 266314100 200377482 126746875 228073714 392546694 924298676 895495393 490296146 738414031 779544251 821939234 148993600 177008390 719428067 967522335 140658082 534202223 212754549 869605792 425770878 742036339 524478696 767172876 456939640 153182435 147944704 564372248 776338460 216517577 45876267 552416074 136996099 829689943 804972376 4978595 511578219 319383399 58402871 395942641 320392369 418569673 745172868 250627993 161764843 58230633 789084300 29928904 670128853 823028653 825529001 615159865 561592068 215192697 173854915 514751217 406579394 575963087 282211232 782448110 286910075 138266324 991104245 350023376 166915582 518151552 134864372 138450234 695109213 285519283 138142141 297263060 642713721 684003399