1000 719
66373318 411446043 220719671 468226916 218541224 209394325 78255707 278086342 846918799 682260152 842857744 325438725 558735007 724296303 510546637 624410458 656037 356463619 257488840 167618291 886660246 319753084 670445019 365229761 328625569 645782185 85976688 61822127 944564051 866115006 536762287 625300202 804437657 53177574 947678502 251455864 500542416 150606288 982114348 581840563 881584645 569016478 671355970 364206975 206391141 759776960 187658007 61772163 250638252 827369777 679249650 888528128 122404016 185876065 159663050 940444346 58130602 732365168 941883484 893445788 775534360 791481855 308458998 67912042 585760471 246893474 149126708 850886597 452656964 48086327 260123900 709208881 209608074 681345444 910206326 444011572 50838385 574825448 215258006 260534053 862177822 590659107 925576959 688082108 749473075 385620128 665587544 148029347 530734627 944954370 426147716 989503806 438070557 69919164 736765765 55652510 388415332 362677495 160026683 939469236 882995062 379967647 366605351 228812850 425133138 976218956 735659077 233555579 52508610 684680854 266229095 111709537 307066477 632140971 660119232 144952377 603201429 278705954 858421301 436499296 296693200 765016872 61873531 555158429 637378272 180075667 883802681 754897848 81442726 637724114 515347261 19226257 444577113 65598923 366621410 92116995 645186681 249506309 354938793 276719830 742777104 677488205 65719584 650328649 415877545 872003177 456056072 815314513 864808081 788550894 200022846 588906531 572183630 106632673 467099111 687748541 515266551 302321497 250948009 783394754 526514531 366686786 11057277 134406033 639115179 605308414 608471119 882805422 381197520 175858111 979094997 294425915 580427414 264433981 385867789 782277165 668472184 152179313 857915976 440389642 139203743 376602835 422029785 769330893 816303752 439412507 419410917 248905412 554813406 80616442 179401241 485819407 142470032 249016904 642401416 685506808 14294063 240083132 939444320 536991213 229613064 636569652 72440138 900677741 82594629 905384912 463994612 668498474 694504953 213425962 934348035 60224960 457245658 752217453 57621528 359979765 888525204 120677437 198762507 835231906 707891106 537065032 524448793 949012304 326258214 578874377 87619806 951280275 596361790 548530777 221033836 171988005 599018470 963969941 619942488 89800434 597263236 182654179 161161157 995902883 472042579 778596825 637767278 840826821 4619559 471485881 719687249 378679649 342235822 271517209 358036347 53834021 36785200 47317372 648482917 327988086 749874272 223877093 425548005 666789010 152598715 169620905 125189320 909050613 190148449 967726543 994062024 474892223 446093164 51116248 657514254 170634429 704717099 267175068 133699609 875977993 344680643 888268958 855340108 966297094 407944718 262645651 625764870 175821597 645239989 524827816 462438770 344358548 759614431 398131366 672319673 452390961 62950201 60900849 904315877 324599668 254859028 743212945 309059879 478658118 879305479 765490809 392689267 672339431 649609660 941158830 564372923 690350321 827513511 559549308 238004285 157171476 472981030 921105705 523906315 996720147 457497340 842477715 247947918 93479073 391720600 111422406 276400554 364915447 923691225 696023310 874203989 826904475 505525039 180815240 186847462 625240373 955898057 159566477 759110465 112104045 436070505 470972284 571426277 861043888 536818928 627705664 23455528 681543652 291631904 393166152 434484952 266880365 382018938 932096481 792957099 411408470 370223687 513404500 912419132 72222012 527443527 69151394 463428170 758063978 853448469 932006006 23056094 636695403 923481743 900045570 517140963 773952741 440408204 128865357 132538323 66657372 234524208 942089303 306289821 161604100 328242700 629156166 51188181 235765662 232453605 515548130 734485513 487523902 79280951 718729301 207350723 820537292 169633382 998854838 855823897 208527681 703545205 436663478 227586927 376008397 789330333 33794316 492028856 236827025 45685713 546448769 544790135 876943397 452841066 313797713 640787806 701422785 452003254 940097760 948717006 179366894 654300106 108570588 168273433 986537776 702319229 50025892 441527447 281007066 798893848 869339783 302849705 275420253 785935826 175530841 248658437 781831183 19987515 725704107 124584883 107772829 187256495 501792086 71498773 893476750 865219415 424066233 541169394 222175315 362240494 694386497 611547754 227941762 785749395 907954120 820533909 418820699 560069228 487785381 691419414 694505595 262477299 359515715 211571439 942040810 292907611 272907943 687402475 965742348 269611642 388204988 116776481 780304628 496495176 809989395 709040341 621031727 121703147 811871261 491382942 590744824 879403893 602347409 386057120 140677274 843121965 890464061 238401581 154003895 225930469 505365786 440287564 318341428 672944339 288523058 654596971 169632594 936209380 547791887 454704844 844539690 532080188 496920911 747915189 359898382 115012038 927110842 173421158 133849507 914812940 480319165 475356797 761411130 25280658 897923297 419952567 927780394 117329385 112004666 780370869 540544889 547096666 211525548 190806416 177168640 385756915 865597754 796596553 369073601 689896942 106063615 47517090 218254139 31934440 380909553 449313084 649651135 548573524 624226795 569567035 924500797 134293739 315293845 791517236 397110274 678017041 283075661 788940058 116597236 251817884 960969138 982894525 96045283 561467872 472773810 271859428 570010122 474867713 700207266 102588690 272070839 10625850 516069781 89629948 387649596 244560370 96958074 684116396 120507502 388682195 403681610 28054547 3524076 444488517 24970330 783676511 53264541 746478391 765402059 871349785 889397729 471548600 904267101 321264389 8123047 925118621 654185792 266729755 286425165 68571131 69879483 19730817 103756457 781471597 66733075 219514361 550267583 732040824 306875669 412864103 166277159 619883005 145476146 248573435 839410935 324271227 22550744 985871587 495257354 364775770 72741379 719205992 145952793 508857700 465293962 654814137 206897919 230967382 636694653 549049548 378983038 755305260 784479743 187797849 657894628 824098803 977914909 553886688 357036399 146219487 446153644 124506614 668198369 8479093 422081696 365493064 239056893 570136196 6677229 151630672 275605893 741814302 864196623 36456846 589539108 826963962 4650185 955023695 787927318 412433791 15611650 844894177 953169643 983518544 513809769 941779072 908091948 15822143 885925743 50600045 885266707 269498881 375802215 966448783 185878286 146395461 351191004 894106386 134276605 582198302 834392328 440683039 568590344 837186303 248582392 566531877 819982567 502216052 460885533 609087843 10879468 907494854 153296748 912236688 421756262 52462675 77611360 286909421 643349497 235257606 197326356 863011299 594110942 481463668 9417365 703257511 144800666 728553423 325931261 218075197 87681962 702540753 983532195 737851595 232017272 41255075 898685132 819482805 686368244 225010114 958566111 523259112 910495621 331102817 878661125 221388325 577773239 129663627 964642414 144014575 180820078 679404057 454192248 496395789 781126501 701781731 483511844 646959809 994422393 69009949 733148253 379558688 206355441 908333655 811395641 867439931 887461852 1077717 539417170 46445874 990540190 699742783 535903469 9317320 773131031 44116348 324028639 378023444 238829953 422072000 783760479 358756612 192970556 847896042 283929872 63804086 368215330 580244192 624507143 347852996 342236287 794828317 320925266 804371496 443064338 81946403 449781980 427853330 20966776 283612922 316476390 592377807 469662504 979609457 235488752 486311793 477004151 98354725 569288653 839633729 839518371 500346884 774746329 546263231 256628474 549919527 128723329 770948241 1297055 146641382 398619026 329656975 855365017 576010757 161392891 801971571 286719627 751945102 543202727 757345919 593818248 965838254 547226233 629723259 2536224 645272385 770716779 63082001 900302453 19324801 252778861 850799957 133216248 638005293 768465810 908017071 730032698 12295610 793048741 836379082 918943979 18949176 44240794 930682539 537033228 897566756 789073867 962441161 501234028 78822931 552142286 634582178 566623125 226138855 10389553 220773120 904288532 576488910 210787670 986706121 25458099 40967134 633438936 121123440 560173989 711123439 127759272 75079585 998294699 10588938 391494949 860910610 265994116 837506744 101196902 487100741 534537285 352444348 164275668 825280215 145675426 510927533 727508148 913367267 66860671 873598883 713151801 57960731 69645255 871541244 394313568 623525850 124938512 612138117 984658709 506352064 236245690 112265584 364462222 587851903 211331185 642252153 543884058 295501170 922268419 626973747 482658539 865286875 742133177 90110552 354888597 796883035 282389249 766703789 98599265 342424620 969898830 880276462 378512200 811130496 873613014 17038856 619696446 493298688 678212516 394799946 457266670 331110245 327245656 577403391 473690035 884465569 766380213 746933907 912094424 716419390 495291199 573832777 530862697 130245915 732458153 665311452 959346394 589926786 657822467 462707180 850048282 659211257 404118109 758835313 179486758 583554545 704714710 598488970 245064218 561647355 885834284 349891124 78723606 628758126 475933357 897697769 436388284 881174718 862354176 431144124 968786322 494100435 953626237 991790437 54929801 266807129 990766191 866098302 667966700 19177160 252286227 417564374 377043940 583107183 888697648 681915716 916052659 556558226 121889489 533952685 143315462 272468973 44195511 201669254 393846455 333078102 345135589 667120050 672714814 568708934 161645048 196592586 796977879 264336991 580147955 582313777 111008374 591958751 896852573 734748750 849426739 124503844 754099137 945888364 479741380 462095924 610379337 367914110 197774979 552919586 759798892 709604511 693944871 973423400 798911704 835956491 937896166 280282197 888867957 781951080 895404214 612713255 429991582