1000 605
443476372 185292171 372084118 597471607 562441614 440488969 361235809 870464404 753636787 9183007 758285194 875178151 755040573 703778416 790345768 446848384 543472552 729741421 820067688 144287875 268483575 522245647 914394157 763769516 402036339 912545333 530215768 714748045 166245161 305972257 35043996 718913961 91754842 775785492 2178233 430024753 770625809 593534614 759632224 6446047 416756627 268353052 608633856 858090122 150044284 716480331 844549484 854640457 621066104 898266721 352366238 533992564 856289116 835994800 710628481 92721009 418277038 377369255 363121485 759698241 201515133 73149499 174788769 763892109 451484076 962014105 369975738 351872881 61387900 871327445 310149030 483447699 133739417 122474569 802084287 86993026 478216141 399297419 184149416 622676290 161431466 861780012 818632565 451304471 556788749 474814347 502916688 896714735 447999018 119673073 744502284 963320124 550318033 778865300 119326143 255369598 69457527 549581358 267873339 114212015 973263989 889039562 81673003 954007867 537990370 450949313 920859192 662481515 76856485 14763464 190258438 646692506 620988222 531933208 13831372 386928579 926251799 671945143 107360936 416568468 60426297 383969064 192229755 584019538 610344860 880779336 941063750 104728416 479074917 739522862 535269910 122140119 443080329 352446796 536347329 833104356 269352748 673708844 694926820 332615148 709928582 769719502 520841034 5062002 859508388 883309892 660796791 443019463 493495506 988432147 842113263 608268282 584320552 222186954 76002434 894133195 802608106 564310040 845590339 94918609 48076096 396955459 770415867 947940244 980858875 165777422 790733113 172953798 397879454 637089735 717729361 547074571 292174222 38955753 657746584 158059426 517520945 921044183 662227413 44442792 413835794 495640836 154167555 840799574 421043044 743274153 477409122 207771701 677861753 196433621 284513693 804098802 645650775 290242094 233837495 278293873 764908679 845582713 722111601 241225123 117748306 273992881 592654906 684596316 88050024 564830188 969124321 185440543 339239629 150467276 20261154 472406628 503615047 627421176 121862670 510606469 650942816 301578070 731006087 8955825 859265972 685757797 888643500 830978284 309449535 692741714 357759739 808343523 974472899 10201774 433921824 121219623 404705862 880840005 925360630 596149449 187302330 157831223 474075779 353348343 485425974 349736617 742528259 857643228 435413509 41621576 863222111 639370254 670246988 31927465 930967536 63686807 262021185 600653629 812402506 866531489 116773208 797755296 801930094 825559899 848729245 219162915 406596488 169828979 700013835 695795317 968702456 574343883 184933905 225870283 618140964 2859719 47430537 76153321 338603669 954470833 141186782 389054763 536782988 566158041 603215857 761274492 989405771 255098329 966802482 963985883 882661337 741148885 567481285 709118210 886062848 773042426 354917825 45580804 200931252 104852047 526045383 672139902 531209298 115091403 910071635 710141926 5736249 109659456 855551455 176797754 608235496 478666288 939644499 488642255 745215935 274906874 366259450 383175386 634799158 557629859 369719665 316416590 921565484 344249406 19684757 524036414 554790135 807353723 507331392 663679934 190139563 165491597 428146667 209589487 296892031 107409816 670409837 776971692 753128727 798276971 771395687 636009703 394351924 395483971 191389355 814118803 294050109 638660952 534734108 321150303 615302610 360204011 794872979 120504755 719736393 227637933 174369908 694278886 743990988 165565884 115110704 233015531 917754472 202052170 689770062 221351585 111913367 783110982 836577853 411185837 678418916 350295101 711897127 922750726 487428879 278943674 604705218 41535319 428113620 712669265 567509555 424322143 789791165 434684983 199764409 423827501 875896044 454357757 306009034 834844609 147566507 518898367 634549066 312402441 524409750 92054978 291533491 570480219 628170726 65826893 714351872 526741641 272588010 82799092 116640842 598875006 510305118 410332632 282979324 12774908 325225143 512216982 493968923 426523529 731200471 211080882 14959980 550245679 478217372 120226744 123490146 246855625 853227824 924675186 259776755 13571499 404003438 77549091 47423450 545078273 149142785 858564314 1789790 590644833 360035313 212710942 810687804 561727635 575778442 750934953 839906145 572183884 175458298 484514628 677341556 323791019 745857563 637385577 344000885 347641208 114297681 76706991 742202759 709879401 521470526 216426633 469731328 37958817 837110040 614367027 492906126 523079336 294975455 974299487 748431730 100931267 269847188 429012747 276285490 499099992 208734792 196100170 103387321 710874038 801575597 324548233 700684933 912905203 383213189 83822686 724984473 243620163 961245781 212191489 466248595 108158980 488285363 170334972 529060757 444691850 266560179 796022135 248004060 447877596 488384723 810282695 500730457 819439170 289281973 233877768 582312932 917273841 770791354 410433454 689578631 824506372 147108466 808471778 642391768 848472531 3418291 49035482 392696768 842788257 461027848 458046333 795556786 435649427 880093892 742711868 718197726 720122773 775252249 612431944 931613794 590238655 484547147 306815412 279720212 753269236 370140886 695289309 428623846 252899204 316153247 684740981 303714137 669372572 982689844 155345298 992326891 753115632 642928091 716241633 809793833 790307872 721144855 775161586 682111728 200535900 146508194 569906582 136721807 337670329 885839858 737171851 14267126 401721031 679763878 422307700 804785335 667696357 717913038 889995132 144409268 126379683 640503996 88056244 123486770 993635709 462247276 481306007 654832526 471859574 371870042 844776064 517245837 980594549 946954549 271931403 310389646 338030427 175009904 688102868 907565110 857013735 483253705 268154024 496356604 13507199 953562591 769955830 267807664 500805412 796477681 141545147 560155940 170806862 690017764 510087307 470643623 107029513 383858835 785101915 144060195 438493343 987500203 401028757 727201098 90872578 455069497 325028909 492917732 540976623 253847 192077203 29607510 275188515 807576645 272881096 46169697 626079304 771712613 165366870 713364061 297037433 679323929 835266167 544505769 176895182 347328190 280373164 972598117 860174648 910737560 242384636 474314930 474619343 175419969 278284479 234577589 349691451 14016168 889209527 872275254 535577335 363413872 679674561 485819893 962524138 526453253 809509856 793133292 160206478 615129713 84600671 69280967 680762166 377095971 693447045 456268529 891403004 718236005 856980678 784042582 414401557 5162753 43842253 598664494 961378566 29745057 121048577 835455183 848389007 240039361 540494827 333131229 149535320 232941414 778452142 867772923 658464234 300684497 888606507 742121322 719454542 612968674 990188619 862721481 513935717 197761138 996405704 517221584 205054709 833670203 991508335 610598031 692574248 12254798 795567102 253564093 424174176 684347654 53475722 611589107 272722884 896482627 148306527 925518055 590553124 800315568 130199641 183639005 15495890 371996085 857732526 964685611 903358171 483825906 385230780 333998718 725362820 961997441 954244543 699519219 753564381 696442530 523014609 412364578 44796906 93512597 323242806 983495513 169648559 84800881 398514582 665968816 685540106 51109279 298470263 14322947 460302754 9938389 485586086 942434496 676471778 462162015 227568870 602029721 545304462 141320738 267533724 487732866 641278942 518803386 461309879 152643447 109302389 458026692 941120214 886518097 850148591 575197884 412614089 185953343 822672358 955321401 234341000 892847342 928703777 927006788 489593201 780917143 236163519 561359666 340937371 775767899 449655728 619413635 447566590 5694454 885553109 116282121 686934952 109545646 634613118 553863181 839188672 695735025 771483832 939352551 431315908 901227626 88708052 597834428 736640636 571213611 45929445 68314693 146823684 771211558 280853137 265958988 264520748 917916362 130087813 221205570 118176276 696322411 645418376 112293541 300087822 493882465 447028072 148980895 479570014 842685426 908114812 614007107 354495464 977240333 460256412 141024524 682326225 856101102 681870132 734310150 944732514 387212856 524925072 17902222 52082576 735968476 54210156 98147936 734797147 808943370 732386338 798494038 49335614 215727204 125944097 965908647 147235532 792901924 74484425 604589967 843086149 734951333 989094407 468313725 102755750 92847040 103669738 636930257 565505344 416228529 824983093 978857906 157463681 63345028 352908751 160511986 191544679 900349694 231147973 486992572 108743259 193135451 418270804 312666866 135791817 76299950 441661045 633911125 389282269 920080548 319298954 570198023 384064822 641981862 671894300 292804369 118972800 708419000 583807343 915169528 142780602 46371893 342478680 217280836 665119201 936628875 550771588 804973194 200065744 70257251 355025117 232932038 148271144 365193977 709445830 319290825 910027067 51267823 170796116 170716645 614417765 282369900 483167076 153133651 374100448 827451701 530255709 520412432 120978851 221447321 539098877 847724710 658895518 760666659 929428623 386277368 874259665 841209208 173695613 637448577 9830725 623459415 623937803 103918126 705432558 408204767 855890940 71414370 442906183 400912737 56716231 59448024 297919744 192876897 788774925 456381014 601837124 618082117 655023936 180967625 661500293 82393533 509565990 873720667 714623713 83454339 126180401 568720395 826326724 791252409 371234771 167540651 287086346 646316745 723977637 730622004 438807297 707191333 76975475 51709720 769712574 641588662 990998478 157116132 301224933 301966252 851445396 928813714 103982819 52231550 204281162 861728654 7263911 551227557 190973192 31323193 660343821 753996535 291647722 857502076 41502623 457551573 12492240 791839194 304127655 910470835 240342861 568229709 388196388 916691111 359839164 416974968 126192491 811865145 337406371 780665998 770179774