969
515406050 591998764 947023021 487081168 3791190 166987188 374447883 352822477 603551751 415198571 858633459 633406688 635347751 191359607 454978575 205369761 64672848 673864469 149485538 87801621 980025515 584693332 158616612 742639589 4724076 773264319 510933524 943244634 851662067 341922495 122596429 591793905 51777583 859983317 629372147 282254611 834187136 832883248 951896915 254038156 119065109 738298442 994909457 5312621 813353363 219584342 371374590 761998033 246372374 882987268 509574937 667345626 533495984 241368783 271734782 684130238 453781726 407203815 967079364 33132270 85524982 379491405 672754350 152726099 615033111 826425254 39955031 607287521 669940811 26253538 661203804 801039832 2573882 961942189 151661503 193084970 49598939 587552158 388657530 308475214 48802711 8343085 763168170 14104398 308259468 893561233 530963993 108090630 529941164 564957050 120265599 644915107 918918105 933327439 99177522 367940243 790503488 964995206 190727303 199846567 264476908 573436160 253898601 919984750 784851553 800842463 44160949 645339788 605476551 312106422 397706074 226770252 948576303 13884295 286492760 748532680 355949112 820947065 886687638 712703052 714230435 307764576 72587749 343958921 34293118 639668324 404506923 171833845 986730354 819001757 258536150 340540808 198476594 181914736 669444217 304786953 706160373 610347465 163947845 543997530 694616249 331493384 675363886 639747836 722758149 29868111 722650851 119980606 426192112 73875200 861938268 95167209 630199018 720120825 939109808 575666374 846568925 728941930 520205324 272889242 717240461 263152941 737243581 167514881 708454637 888203054 266253247 251530877 174877386 959979863 249423960 294705535 480478182 622758650 611045085 688611524 994884335 107277846 378561033 985496802 803649757 232375539 469057207 534394303 94941926 61711156 203586107 556947133 357875979 545009597 694363155 352604809 948277910 231719154 626216287 235597147 558858649 501702341 226412777 663868422 929336750 700764189 837836715 311219917 505789023 884712641 995988105 907849272 191340710 251894836 829349183 821016334 344426671 222832067 577545765 74751860 222230740 262966309 740556117 450123210 584934092 176483864 494151394 318953927 680080675 102356819 637547387 519508536 923399174 849900694 82370099 426452952 209046371 395963463 598408797 984882875 438812633 31862938 75963425 566948762 994860455 184238774 611943525 266525759 305095731 898531912 12617981 429196006 968686689 673214593 92198070 811514856 424446986 906983002 759652152 852363413 465060912 923355412 280056398 128313161 130104574 201967794 59348664 356135916 759612580 4174327 334283808 454485175 33978450 856697148 672995455 419195970 392316326 964656205 94834055 469217513 627259508 673749368 745582155 88442531 589609756 529105055 578382630 239494793 823666195 210326769 917489159 627700703 459833768 9837919 950083037 333900445 282098666 935662273 239798018 604258108 928960963 933484343 64164374 744120350 454372012 414505390 314812203 321809542 532843620 828551397 285858359 924840039 369358119 349635368 375456465 350597229 520996985 948999320 334675367 982131771 503045367 419804415 801388499 180011798 538295136 367424930 310097620 668660415 856626590 501354497 283958910 386804920 536746867 500372822 462174861 382068134 362591671 33636117 705932790 549463639 402991383 364538627 223797877 753314456 718342359 847095472 745120409 631861293 378713739 867402021 118215564 692424096 32741928 454130632 975710061 242418437 907867990 140187991 571567091 476187300 886427028 25603955 920018470 43464313 565853037 894617571 814230146 614280655 54180211 320132872 234841425 268943527 122579559 786236574 874837620 267922268 923091444 213547774 993470579 557018658 311475436 748654268 155779077 742548774 487576170 868674989 233911007 441107021 64257953 454991201 321252281 583026002 183468631 51129859 329243656 448515505 944711118 419876892 362780552 259345963 720761084 287020784 166248398 503351886 617765792 595341414 759274734 575963393 570806922 536117870 42141245 200572333 889892378 13230878 542527758 903381767 989153584 768138980 672253580 26558023 689915640 157474941 132998188 184678211 196967226 265047157 459068842 417460359 931660220 478584952 925738406 250018944 7928053 297218105 252324561 89907414 56311012 549850020 316758606 379751206 107369706 202030199 289745099 56110244 295669286 203956605 164119051 538291239 547014148 556473719 49524593 485555718 24858882 697858120 823108333 7481881 680718714 125119306 716651780 371129445 916736131 546507121 395077083 843181972 660045135 449308547 973604485 763794177 495039759 655636912 824034631 14311314 403541693 462524731 89369820 256544303 711501016 132091866 873964900 444717609 32755393 159881073 628931605 778077447 390825234 198724883 303230615 910361130 383900558 687512316 85798167 374000850 315859464 514734625 829332400 319843484 714594299 338829845 711214554 651378819 330855104 816500810 458393663 749388551 360623222 13834566 921700382 792235122 47431357 519970206 314609382 634598686 810861334 918370905 56970112 463844128 444387655 278213715 620456395 844814292 258251716 330095788 706785258 175940011 907992931 81378622 545966655 904099643 828638928 281920558 181355538 150825665 282776466 484400984 102668035 446566523 932757328 701832904 656152322 285533074 649569635 664017803 670642561 59820424 663367877 167492782 735050797 795531239 234506363 613059641 907762832 18328201 252765917 950487033 809269905 228172942 749126016 789313249 69480340 27178303 78992193 587928878 873306665 238945846 99447407 526149182 746491514 150029878 594349 503833600 855754318 34321901 223474632 866115374 131287587 934084819 853576035 9071679 456750279 635445181 928733811 733289540 111669201 449235343 386602598 10603936 992387976 161435027 948964067 898511978 605231254 770323744 707265733 314057028 413957928 343884805 358296884 963364412 795436846 962434951 943959423 323027410 956823399 824384624 624333626 780251922 123486570 904547239 409171240 713850386 430390559 649602132 730250566 709574081 828693560 762270101 293371435 459317844 856992593 766961041 534115171 9069617 482366745 986927745 100352851 138450602 804588636 83015865 20037070 361162505 26393506 265439841 851470145 154960690 719692288 593004988 442824628 563145918 364733953 804018137 885913898 674999496 162095124 800598789 105870728 202235372 405236785 794224260 162700334 351813081 764932833 141658382 315125362 916071589 258206113 541611843 428580147 12487978 166632049 713363633 883311826 432611661 557457130 899408904 687652931 655345464 148380909 431161654 887274341 486752071 840493077 762074573 994524261 880447581 791904412 535445283 655700175 417183465 834843523 275136569 512058850 580763668 657108922 481545753 821760528 890203273 708546888 160308298 321208747 109627272 276747387 800779429 104254187 499758579 290821352 650109324 879195637 300987962 814028162 963236263 599892770 417776547 406976613 144821277 79833045 258621763 836931785 200570966 470880212 657273059 235458601 984019229 528039698 73132880 114089178 709179810 843150125 464071681 299319881 513437033 94254702 8887105 274581765 335715645 599512699 755602656 734853588 46037061 405094448 52395304 612599550 81989399 25348702 103102279 340858662 319317905 357792447 517197117 578546649 214280375 947726215 420888419 121272966 796733772 419826375 216141404 2961663 2958097 674522885 679653687 728651706 887102435 386435095 426146510 178270110 986578748 577141037 447647 502159205 198640498 649097005 686201890 913353751 175892127 336358461 352826927 673685985 682699567 306373019 871627443 776870146 537503254 214779608 201527148 869054566 1713387 279365160 222462561 3770157 329022866 278418493 64103849 409593334 294953884 779285634 976265603 607013151 56928282 244963727 98445105 537054996 236320444 729823389 397988407 530539968 117493890 273635533 66628801 681814057 133108344 252320977 614349628 579941890 1198626 762141280 789039295 390857289 839819413 364637899 274336773 51580845 701247252 318510842 323826976 535445466 355839782 744001405 291932438 122147129 595208171 908105915 268885672 997963548 785089145 538697556 351319776 627514876 774432380 747414886 924757502 244732022 211326964 682620827 577678571 479322628 406622695 837019033 567344830 381979111 474246469 619271678 96231287 857967145 658737783 422263098 140019637 967050985 296391540 526813293 555428020 932202231 467896485 345689624 8338683 436569109 526413823 111425334 659762528 847203994 21652872 405968006 991934442 620509817 901671574 280537227 277009436 39494927 613400689 860465665 362442351 350897490 490278350 587259042 528319660 237879858 712425297 662825052 313342981 495723877 954760989 655767674 668877077 695536030 869111400 451310734 556053850 934611488 841894154 300645419 480777992 586205425 846186927 991403180 180214356 671506644 450053683 287974796 94929058 281709457 270680752 281108133 825831935 384402337 750200135 800378635 48225182 281831386 112662143 868093801 555940742 854301307 933518080 236853908 285315970 978653813 88961871 97183024 573575236 402785324 127940979 729943674 932457059 996527917 549499478 906226055 533395283 38236508 954857779 79242207 525937 204900723 736243753 20267804 370964093 691273771 761132916 53519764 934167635 502310334 900409276 677933876 870351236 902939120 261358128 75457974 333500173 689067369 728516507 793167789 183848246 730175512 738433723 298825046 869432967 283068007 915788196 881515150 88892719 387410227 799275298 955687340 140616243 487751329 504027061 825348450 473242339 873199747 766139730 949785518 90550166 230449551 141577055 780648379