1000 940443132
427176817 778776609 78627537 692645306 480627982 851692165 811390040 52008616 875427616 260629092 215202206 720136525 78676354 850793114 774934350 541093504 784191256 929401352 404662712 610248218 54096079 517467275 957865455 299025351 764080834 754625231 838635724 447754060 816865349 25594499 892160845 674263619 175029495 132210674 504718359 652555654 141917290 14690098 168798887 177842820 794060901 484288642 187739334 115196446 788384872 165327285 227561070 660022224 901931082 189942091 566300659 589203020 434856427 312658401 226097398 800204301 829172700 689826715 702624552 680869332 975525149 309905719 585066056 526637771 351044153 952292201 482781100 722215137 208798843 951256999 733229018 532975964 181723964 304253468 440359943 280805405 466922509 649606787 352954421 478414924 714653529 80905765 579461698 304600493 320907314 408287369 88085985 639382036 23757293 188834003 2103301 698688786 238785716 102659589 140781881 823955468 836131040 160846180 604736906 704256172 790801441 835502192 887543531 392486716 560883674 362420634 613495279 472622326 410282954 103324188 978609831 397371197 9567715 97382368 318688446 177621357 58338198 417916960 750414193 642393124 20165094 667701300 493953008 2974927 643707602 144907513 750088876 20591865 243299300 87452432 732059932 486319145 522382161 128507254 406122782 939977629 455397463 349104382 634037668 805287441 762928088 40786713 69616150 634258246 537456601 694109676 764213530 170076875 464873968 422496658 827573755 172380447 996089268 850044416 640564729 731677619 598698665 20789529 451177913 707369391 441891386 523503542 808682256 566569284 179307214 502594171 293202793 703633391 831485312 115389316 273822350 142859997 723000597 553525149 960703942 59816546 337020410 246758578 638358196 757374759 387209675 183684963 452763308 277262453 986207725 987254627 376231144 856038894 669632614 51059886 499783519 281182171 948485328 564226924 148926899 580090971 964258558 283782972 694543063 354496684 338220489 965211419 86518765 312315848 300601133 911042766 779716490 830529592 172891596 951759733 198744120 996141767 91411251 116886311 526895334 135638270 696723814 582058123 951772984 624047316 662776420 963168792 280053149 368577577 271161846 519782867 181133839 385894531 232108132 248066427 247402846 895272885 326022424 985316976 481825101 656578475 127678327 896577890 631098206 1269314 831459963 153053638 541250372 135081081 814991272 361854619 808757823 821374590 661057134 193816761 311552566 707313146 650676207 725323088 78348053 472024585 855535677 862438098 565818191 233405340 471384246 64965448 710585174 200329536 817492338 992129997 315524248 358367684 28054533 294443912 376340596 638845276 168088353 370285897 139421617 825704809 264126918 488603613 785107337 455801467 21589744 197482533 679525943 747523508 26409328 768748560 814335330 929090888 179113256 202138803 607540608 4410140 416171903 910472370 325166810 578681264 129469900 194306205 61611888 620369956 772621261 703471360 832513021 462951312 608283697 759007859 692983306 126748968 325045174 944308228 137490065 767407937 172423382 334409656 734036731 67677195 859582299 92711578 250637837 41701566 370266624 552764523 669141207 945177681 917919991 118378938 445881888 723027047 516072857 728825067 687802310 438740264 924215479 22723629 908180934 705547682 542039468 85490111 999839592 347808325 218539460 219727750 213925115 7743266 537838585 913759917 883406972 240893344 584459379 514212628 594557359 583966703 783639800 95485750 141232746 624170299 88257618 184465560 359236077 87336589 303371557 251798625 758851251 812405580 786830316 88047927 947263972 825013918 664181785 757128134 51849906 228885759 30690956 710235763 245390367 654313244 966678717 682215763 935282771 506441591 188561399 620440133 746568962 399498490 922062646 683827153 625092509 438434073 594069155 274314185 467074526 902516615 189530449 493845425 281917167 922414996 408653260 534433823 281975030 208306934 286297003 854961363 21271100 839143726 673896928 700443285 836449309 811965735 68452908 380857622 442705966 379210376 676000912 440471793 896086165 141309950 443374510 120088163 715847636 276349978 835547348 388765343 903783726 61943570 617357615 843403643 257360237 739947635 126122103 985345599 879538949 374776185 161520609 207937721 56127071 463579617 595473215 998402396 115956028 226290645 890279681 577212976 140634661 799394664 627655432 114729965 239004451 797665272 343090871 704033916 422121627 698756524 561623395 493814201 296916939 496926264 543500945 795457811 927747226 164172191 651079695 706478359 16153335 370530576 270659750 272347313 886784895 906042605 945867725 132371360 282827579 97543527 284925036 729514381 215151107 795392608 2127784 641256945 327295278 405535528 804180034 659990181 238791088 422708212 384159808 880097335 175952516 922002178 38930934 762737792 72238642 200748485 807381513 168011951 514706828 439906586 356660647 591287104 851744474 432779545 639876682 280435590 412795388 689154521 464779751 545660622 709293188 925309231 316679767 902093515 804069457 933761791 446827961 322105859 861453624 668486767 604475484 826100705 885614064 625891686 395529278 762995853 263684550 643738989 110325394 76445472 284331300 947871926 189329783 289980965 626957461 250415147 437963847 250281365 220353711 334792309 800214164 586844087 410979464 586675963 204478977 905045180 406066980 272384873 352723451 715746805 376069307 102318826 312428847 248146803 501999656 190100019 915876619 334358440 827903391 498656505 870541531 292503372 994146563 626771848 845617263 832437343 985399730 624137977 43962417 346675666 919511830 286776783 341078165 188378219 843398515 177013474 648671394 830110820 809034188 206150799 288166630 337806879 982834458 482525814 271040826 637002825 992662206 745579154 968472866 881396877 184639734 939168244 305966940 296848861 354711588 853852266 274479499 603913407 298726669 227905870 429900216 136696894 306196146 308984331 606183298 760986333 142418827 275819877 265922609 237924351 344527803 674858575 157195702 23707197 179745314 632472997 348474923 83010904 572976910 612228342 124702888 996280589 343663609 567787474 887560987 720853837 710988556 337723713 832396616 510475842 204273878 441024804 865512439 460522598 35054473 676487015 260749396 263110620 21789616 102165286 221727020 601740876 560523839 828919403 351043572 945563543 686302021 71228891 657391334 388936192 99346917 433775958 871941054 873952902 601786919 61918385 841759558 365581383 154561063 819628252 315994320 937422876 214181443 974474855 489500942 260546265 689482903 455079745 325674225 248353199 76911986 138665081 908651830 958074033 915719306 109891903 573350844 16737218 928472898 176624641 217782883 451218311 242335554 984507253 295217970 729812320 267157078 349552291 935593981 282086309 721478414 726563767 650599805 115890947 913285111 114459616 827148398 86915884 199413228 443565952 734802941 84129941 753889972 130564800 272189357 462952190 496026485 118451287 391326987 344757849 97295654 2247897 46536844 103529224 883145682 690226626 288426472 226871718 239926562 676003658 680544578 31015471 731782995 69730223 54994505 237438044 630734444 819212314 606031803 57466069 332383934 149493579 214428535 31522713 15163108 359573069 733135838 146990632 54710720 49167153 463633575 308807688 191081180 155282689 699856370 38371418 837684097 618100170 616035707 756168423 443915120 481675937 53130281 572092427 979780820 130425302 255555496 500614449 345696530 323814642 686085797 474981501 632740574 36754524 84846155 885779643 4336011 683948258 365982694 214661838 797752405 173044349 982882880 930732557 982906724 654000087 48700154 813154098 289853691 954218825 28743955 324988324 798306084 339635795 479956563 893591763 23461866 842156701 951343059 484344532 559238910 140982698 745449672 817899508 624939893 413236939 42782247 1113115 216970809 964218571 53416156 999156217 668461917 955259054 609649100 268988583 198797086 3038649 730643163 273857854 718838252 654870164 548014483 908744114 795228222 348520324 681635780 500503777 341472840 104661175 178255980 81022334 54730423 221782317 484481150 160765638 6023653 138569189 326046563 732331316 207208325 116343747 480766456 114878206 251878495 975916552 254460327 391861959 647309603 696704475 184750802 610128873 492124169 74833604 936629488 733475977 163562571 31080770 299628081 79106722 72394885 103927673 765649026 798775970 803304885 320728027 706248090 392550055 755806850 948620358 169093703 463756173 105507071 39016997 20739150 371706427 110618936 974704923 485711491 101604521 196096926 863310599 937268953 325339773 883958968 964144331 437397291 18469683 136610450 607464594 706436708 875988026 49946745 986202822 775601966 929989333 714901457 71987174 358004201 110705594 787218197 49916417 905837522 579841301 883576231 387592776 234643068 444200251 198370857 794195211 626204479 229498238 989438649 27467217 158422853 406548241 66651574 410809491 113412219 897091175 225774873 984808042 695990323 599191755 922165200 854139712 253486546 2056489 12102915 920594079 725920689 392263728 27261282 782744117 644216683 865021265 95387119 786570730 672135660 752906406 663509895 747568504 578161328 973734807 328589845 994579796 72893178 168375570 625516488 348504735 139094949 440502070 539057066 695154310 494642629 954446088 397465085 61100915 604785798 68414340 83401211 305989763 718342023 479587075 399784295 584205562 843944181 822356348 847070919 97954841 507793501 596566914 338640919 32171024 963236291 122492406 690938509 194405790 180097529 780375426 780326926 659453050 881176643 550501019 581542635 939790930 521207269 362943581 203078473 799469713 561034195 476080649 703889845 29033282 240741421 167463418 927632692 567653531 132792291 819698024 851967657 313960028 56977826 286061948 230237534 523044526 595979667 504333862 390000674 260027989 124711942 809157078 731615172 495146024