1000 682
428284072 840872726 480420560 451468266 763767568 124271977 856104612 522625232 387848399 39490009 392008690 430868425 140457103 201416864 457639731 844247916 270505180 128925906 165924769 474637421 500133459 385137686 396069560 845385096 695616169 561624704 634480562 474954645 287246336 596194043 889635664 232141110 591270381 521383545 277676737 350037542 98825565 108917935 773350828 791498599 446610699 360795419 929211103 278911208 991180688 569616 755508186 38004495 30675178 251844473 744365449 329530289 731514620 699127620 473783192 368456060 554161473 796524890 751282228 587166220 273965570 350567056 376575987 157397447 965157509 1369410 10395459 383114272 577102125 406720309 527265856 363891237 952949397 802404040 819490111 95555278 665045537 114902224 471510856 233463309 847446264 513732703 252690964 725901402 739429201 903663746 139567015 267094832 947820179 127799352 622747469 509214504 195139521 299592412 648494493 984492035 689132624 39842511 487882467 190895030 362597963 753558750 710453003 386377574 169991811 562238160 361978215 815451812 290043718 666863210 140938787 603551021 668834326 681823635 666214757 64244656 890614423 97799268 378939097 607548948 86605407 367844340 391409033 995714189 453835539 820659025 132260251 926478440 919702986 180463292 18156168 624730295 356242058 27877414 358240616 735142314 979265466 42221653 233900873 674079540 581872521 212368844 921033460 591190992 278240923 275974687 526450848 22402816 768854712 685537053 190220207 448659138 977180790 724230668 69568987 56284496 495789198 530203422 618321350 54266396 196504484 143847048 648016643 784413260 226131681 228672304 199511694 93323517 463078315 141808713 903995977 141432207 827047366 843823892 471608540 589942538 926784406 792349019 446966898 257219099 714441881 626340834 486355973 898907590 544327473 533955488 821699686 870734054 710032290 218045715 417544187 966926697 818283473 79692490 753771430 761108357 805151084 201718827 290479237 116887697 785983395 559025930 420354861 317022285 495843043 222519956 297463678 439123294 259516812 988421440 43443033 632677556 452609246 278602968 53477503 985902201 740538799 279166680 643264342 719651616 300514129 263332818 74190504 774306448 216447957 643984126 43125519 572706862 905194574 458894877 414521543 242843261 596639794 609427237 328921900 874347547 524890349 31305414 548007591 732669735 719929467 879922538 485211538 616887785 296540950 258430633 327455761 351475053 926967772 748804817 777355186 366822364 329047195 8073157 668714841 105518295 769315659 285340376 183889412 393169803 702286416 364324725 584923588 806427721 527928356 221582741 413095662 410313314 992446797 814226894 805112454 793437285 103820706 205225307 330783832 364073013 532309973 156313144 788170070 90099987 709348980 554193189 330845281 319492242 882502052 513689220 540239779 587909899 855859001 606192262 889682933 940765208 623897454 234649224 145148516 898085292 607539207 51308664 17960852 30382838 635853727 108768070 200298240 643689144 859943256 530293520 86395524 162123182 292761433 147904949 2841706 529429305 913187726 959005893 870737556 182730007 234349161 259129510 120165383 120583290 534152774 594601847 522203167 926769291 465084278 238015143 507924425 472421262 603088733 907614558 949828632 708283135 908642215 528286662 702906770 639306766 902021678 730839568 649346973 728478451 735720545 484977109 614406841 281475998 374786183 206174596 430002649 918613881 570089018 58246700 244586054 337073147 77001025 690050136 696543886 600069025 487875883 433218601 238599972 104232865 439334146 139528052 32260621 696522874 476104851 483696614 635369463 339550734 648996430 374793530 211009559 428685981 370165676 683056623 483585219 600947785 956642660 70482980 370866920 157477858 455673745 70555683 996196615 34590128 89971980 776004921 3409765 850958908 207887740 416177838 85354533 968840780 892332423 863597705 500180875 860385045 794093511 367184399 916042142 954347157 955111231 748929849 312367925 353692434 245639858 888832897 596957589 4112299 558174080 571591042 899566106 520172790 444168570 81789939 991226873 862356491 747106467 281711162 869176966 376350081 596807681 475153415 736157709 816934829 870070537 594938026 791140643 563957207 546688842 362377571 918880089 279684675 204310301 478120232 241441044 255733534 642694676 339511439 865791154 440376336 141530085 843500863 584949196 930510618 859599197 829741372 449412684 525699716 343200522 711557249 879078171 335208605 934298257 459196918 649827706 940489652 882422587 354947483 324243019 172985675 578026686 472094059 735255471 652591620 386049072 126514263 511098031 122101414 999814584 303694893 267094071 907649104 210925981 674603855 180326014 221934159 234935090 603487566 262936204 660239835 429332407 523054676 756998198 759382462 536369931 24738987 850849811 191117228 3552674 966371740 940136183 497740006 170518014 76514801 398757543 308179687 836803091 1772388 645333272 579414245 116729595 999478246 913779812 590099493 851219821 610072926 419780527 327726613 365498633 237032544 732865533 508156575 567493149 899786170 17533975 9751110 39766623 569650838 798987205 428511076 408748234 621179310 131130192 839958023 893004248 449043911 724975220 217682780 373851279 376606990 134826101 150551377 50259831 84899212 640364113 375876350 625826767 625698545 741746597 262835338 647787437 915684163 449544957 688951304 115229540 686313452 371171487 691710684 608469047 1684498 525041585 813006752 292138471 917608631 235757800 19397988 304838737 598293992 65560441 676575771 686360451 196242583 351876681 838211262 303775284 625831411 536908174 225055071 617159470 967190123 9884822 215865626 697047736 678587806 695075629 473889780 441001346 723284819 580770815 97759123 503884626 952545257 14866240 204489032 115959893 220383936 612047013 554028535 280934995 349733269 22374822 442129687 889460896 37098494 915967227 234884446 577368723 773533116 461854824 902215156 140468148 233477441 930436573 773348995 692798026 28946691 378232561 44724285 255688983 393009218 374897575 147911146 926381721 166138573 216527962 627397029 224870741 858164273 418755743 778967243 377205680 336493812 443800824 875215964 603204851 841345918 893605050 524211690 938719106 475876062 940485658 58462423 5544395 150525066 856327588 85413200 581891975 526772506 401195778 676638495 641630343 618782009 569448391 872885244 204852722 658702409 84716338 829707693 192236013 140425189 227461827 171648076 590026460 918412280 282623485 354704683 526226406 216998770 451415745 912069234 539512447 970104526 185989628 637769641 855376624 388338599 735870508 688385756 77166747 15557873 890398867 144712290 345532712 368714445 970214678 832224502 765622931 304315907 547453594 57871892 825596059 378735273 900332888 241254157 216675274 56059938 519677218 398924257 492079053 351421391 796797952 733839979 957224174 63204824 502380662 379054447 560471530 342433520 423218045 646821522 498183327 887920770 533437452 142989788 758131525 816253746 984361144 609723400 825703914 29242691 951155098 766888681 146614155 537688036 166602481 799928827 396854896 408868034 423566423 665502789 959884802 198804200 763692362 191844568 951801237 340262410 342428810 519440505 590475509 716526787 882689109 666804827 331944492 821344563 173608658 426396919 262612281 912529259 265253847 109167725 899663104 187203307 781809890 683717575 549085826 253772679 546415858 164590546 161702155 886493745 331099603 68400850 208112481 991471106 417665193 862589308 569180334 868257748 168024102 628713059 818815789 224855682 475341607 798091555 211475034 53800568 622811358 582115346 32836040 439159637 457558400 750406839 64001504 23768131 702164263 386785505 536222884 477094400 614539989 152359227 83437207 414720190 225810082 910477684 417848086 468634218 834498494 251776177 524233460 532335059 426412915 60842438 335836710 294268544 231611216 783636748 47000106 641914250 238875475 23984853 286519669 569875996 787940324 217340081 800456025 975749820 376930095 783686997 25121105 127908099 471141079 385545677 898563419 489969629 729554109 182371714 76658702 704283856 678999290 841378761 590736926 4464592 849626562 133223387 471924998 283462845 243726992 984110224 857387748 404527879 764952274 170251962 658212812 120927119 27796902 901356162 408698408 810244086 139310404 619300611 461675877 539695651 903316490 777153763 179259577 318150536 413095211 639854657 331723832 736845448 30787051 575648732 162520384 168731956 437822010 985904795 797255724 811195566 257142297 490626941 617271197 619970178 394321588 760075994 574403388 458585183 445255231 739116204 746540053 772927899 355021531 459007385 956906029 187768126 507062151 597767085 177137292 554288838 665055592 500493688 389013752 58582026 52016482 777563197 319467411 538708254 848357953 430651453 483363223 814892220 406701207 196884687 912466738 271681357 628397110 639727043 349813648 390058037 554795785 303069292 423773865 254615939 321921450 485730790 605544125 775536869 980462173 805325956 384541472 790569701 51643495 885645250 359458141 50741837 222983955 982216863 340416026 426461491 507356173 192982115 73133287 970022784 91839698 825182319 562196833 929723552 869045075 523153724 465405186 747741852 185898492 519464036 927770521 539450116 645115003 951500966 632521271 738356979 797375539 566777808 515893316 392735265 897561034 164327637 302431355 115730374 936101457 299666150 212442743 692804346 160912607 191552622 283183716 131462139 291230257 77757379 472574360 846249383 110398802 241189818 893415368 200850461 957362241 390853871 128553149 629486200 636546849 586259756 633886809 923657809 288902439 681972131 899131049 561971547 654737352 711598171 253894464 663723488 591690928 767478325 296035779 572426317 157917097 807290793 347580075 900057304 538225092 696476825 648666698 357619853 834063962 279978237 672064333 637185666 298910744 631429137 332196156 23910564 555364598 747109389