999
38946099 11959718 310004218 903899620 667255883 140957929 525416473 75516907 631652591 439846495 750521486 133067199 515588824 514732171 444685548 938350222 751856019 839348322 3907803 60927030 791437569 522084303 400781972 236090829 655391704 489118256 239381865 714564122 51107872 229924566 931283002 225552922 460872119 927547785 140498945 10642812 89904334 298996994 53701703 60953894 49515626 146874736 804520877 803014062 136860900 294265075 575676004 20735457 407589993 378176036 674892469 77478719 344602490 469019787 469273466 670137980 968233325 548319527 145611427 146026497 541395178 517421290 886114738 88119914 511446639 212309306 756122687 284377862 15549133 654065777 384194677 177186394 948660649 600532573 123630995 484198045 563255291 776232129 827612780 890374205 74753170 665809875 399856103 90081881 240144015 838350524 139016575 836277061 58009061 572961819 351156676 551898890 736376287 14576770 821390041 473382883 929719706 893867255 815547637 356778176 538660999 925515125 530791650 895066567 188847851 654447976 339783296 76584654 567501918 243440181 40429890 434058211 586627151 119104431 374251696 824838084 814182526 33888419 960721124 742173799 321390977 248519501 615024909 926640499 945889600 540913120 113954799 952463557 85819257 778569986 50942049 785660652 942435900 348937806 138827214 759237550 556177520 825777873 453798580 111381121 291154508 52355981 127819560 612239122 145251807 229000185 572224848 523926977 34276745 975588990 821666280 616670242 81423999 481577724 32104637 485952382 553204043 842423619 214282037 727790929 718500426 41589659 973428933 907633098 26049581 86004540 927230329 682969677 763057272 115699414 392444528 341265908 507074054 338237195 372133981 311774218 731490690 559769840 41581064 208319119 236612591 67034767 125078219 615145143 292230945 957643624 918755605 814195562 15608898 886245100 794119402 370421189 198054991 489110784 167594592 280577944 662730904 77504640 541237284 63389670 743005508 746500537 9058291 887380841 61814218 752616174 687032610 345598731 252252537 454771924 198982423 825128558 536232432 785795862 53137869 818891364 719340455 140916945 812677715 832005496 863987813 418207001 156587342 230234211 263369159 148920179 439594867 536037528 209368511 485141593 847293454 666185913 208364307 14129081 83054973 59920671 170621402 430848886 912547765 600471638 130851842 478442981 944849085 248006046 121871309 830553169 861686062 530673003 316973647 11708280 30034105 123841510 407982578 405511692 973499041 730868075 284538098 122267955 79114300 84377865 538994658 249508103 490700663 183517956 92684837 993553174 467607887 127445334 532565621 876820195 109691480 36844586 979328351 974010468 253326650 866614879 108571589 678844034 732838191 684397580 555593563 34315676 961041030 610273526 31091499 446504964 547843875 222202651 852964369 994326144 39759613 557141291 156112703 680020682 190387871 86205193 108440250 128171537 89681320 400182350 68057051 78402422 118496074 689091271 73480143 358525584 614704334 259343602 684937240 29185512 69885967 582763653 684290314 41566077 774377979 875826407 190538319 655840065 403918613 127908789 633907043 13992346 758600693 364726590 81173016 717173731 886591430 213726983 894050579 345337577 949965000 851855432 771034701 834513262 295071948 75114093 615281555 122699433 855742394 816019350 113592582 506664131 54977550 307195160 26207132 940142940 7744854 136168441 417141150 631993860 139745462 650317176 71153960 61242050 746858853 138774403 523711660 522801809 150822189 184517439 456989039 88581086 532939503 235044739 561843210 133025035 331902236 524188509 290530538 978484975 24279101 409965196 435821776 662542676 796437356 12939780 830434130 120487799 124886745 385562221 20672856 194455692 279686726 508065956 682382240 90071095 884185995 142101561 504310075 37530388 775701779 543055855 583355918 285288240 134261853 375859263 434519890 330404493 290097276 554315222 448750612 974142371 536878231 988622866 61437877 974096345 623929962 928872329 420049003 341866000 220888771 282290818 532049854 384251673 126699014 903584122 59092748 128102457 534155945 301283232 674725894 423194028 332872121 907678041 132813104 526406943 238445395 27043005 161892965 856909365 157041963 347318808 70739793 821657347 294091017 720282730 884372469 992686228 793263431 62691303 44174631 437104486 907110741 820715128 260848399 21002219 205144629 112927800 866282411 981553417 428904191 879136248 465704267 915254426 909922141 117928892 596657430 739290604 993565200 867254076 738098051 69039170 993944938 568618083 63505121 11773778 564899282 404771795 166954960 490685893 486553155 643402591 173241286 17853882 426088653 363987087 738148747 703020355 113013011 928493344 400452029 678210790 79586507 359817602 824068428 233193501 930977345 497242456 129583615 72436182 31683796 796556284 83315949 249666292 640707447 252455672 702811909 813993677 249723186 357995149 98116999 871841706 959738271 678573616 56601224 917137738 94149485 201533192 273559922 397573983 374633696 331369586 474180482 171808271 365854799 301144189 327916104 907571317 188561060 32483438 370241067 43229982 353458144 346320701 191715042 755126412 158570900 359348758 895699964 719028149 617708393 379681497 87671641 908560005 542286745 544759450 869553582 599024728 301345652 696538146 398096645 997943425 292963292 966501996 531386683 489968839 651315657 334723881 629168768 657607650 549348038 194602301 31004634 652587010 885852530 563963711 983443363 868455752 534854656 628638205 770483718 291313739 716725944 490801398 882001286 4619925 342588531 102109406 8934263 43989283 511586082 843395613 568818819 176330985 392429640 110012240 89813286 439171915 520620924 18406342 305858611 719026341 658476264 675693061 192909133 122991812 334523852 128274499 305218414 945924458 830734588 20742893 234071908 21725390 668503389 933665572 38435406 784944154 690242668 874596666 797657123 863714796 114792120 152741177 21708332 973566165 271087715 111780189 888248198 194360285 779893669 541217429 304972705 106079997 234973001 93960454 420780227 602843043 773952814 791833224 77286533 270437681 33726662 274938151 414910036 179666815 520846234 434146211 450971122 800729941 693639109 574821360 337459699 596191985 132454517 766517687 361472577 61916807 453004909 542862035 149401240 562013372 13818502 756105173 57125130 54295850 71459881 994080385 500718204 314461407 762345430 233461838 293685031 198396638 909842848 646675690 514874136 403332764 542867375 86972083 381905073 824416388 829926077 726822207 246255910 148006004 397109401 47811542 971478784 187179582 241465511 605752307 612191389 422270504 585969246 147161030 361524398 430672236 887062472 141774004 440032440 701475001 374149638 353125846 874791316 160190128 741631945 727812726 367278575 109741671 782503386 60630165 167554251 112266217 59878804 190814056 625848828 204565684 929985380 138631126 161499819 464007738 160635216 871441659 941648342 23832674 375997805 977169065 796464846 470638084 474369639 229200866 877437880 691106159 462571517 829647198 667126285 512317671 295204226 478768139 26745114 642219295 361383517 302398344 775313536 584202180 860645514 195573418 799119541 525038066 268716823 549612023 462452097 638361788 956150952 689941037 434338434 952002984 42510835 25253564 161253289 188577073 405023301 874532936 525145531 579499331 954509819 562991400 590969041 389971395 705526537 786333674 768940760 565136645 327378807 833181645 541630993 643905107 193034207 43929924 15289234 647381100 729630705 275082362 331428291 382312963 709629167 337339337 755389666 455515196 875258417 701780545 33987455 672532787 619063202 622478887 464354049 588811381 408170560 84562292 787840544 149781892 886192800 610928210 501003625 369270359 802118504 600192418 433803197 916330456 681676756 669791097 744853713 330860132 555295794 678325150 151926703 589239887 166805093 310934541 496073524 267024989 827683430 638292343 66588817 84438090 835614910 238792640 259758026 867703107 45518093 441809024 883183674 369392235 824653446 839474563 203535117 324089687 980957297 771917641 935696324 952773778 139930280 375822726 89550516 260785689 357071898 48635811 381171079 226312160 851844427 34463035 174132666 635397196 189667026 97736863 132089630 364721847 552365529 268019026 845039703 785946095 572274849 313488014 18453856 110465719 434600700 284842429 78673412 67920452 985622737 148151553 867188838 378092225 192393883 95965101 519809915 343841228 229978602 749231817 402528651 39424759 67834848 710222738 380969651 145771080 914652085 6590967 734960486 822833337 783309620 328559390 932541159 344553656 767888700 304695773 113930192 803096232 998353984 981274433 959732879 17650014 716469448 897282826 712212452 743548582 799941101 280465965 137303908 117951932 785342945 922056017 673190393 700779986 486622308 56851794 634196063 46945937 439839568 480286145 453331881 251881616 173585166 259893090 308297146 913395678 633016607 389221549 868748236 803947134 134703764 741836878 48720621 664022246 590061206 114007461 438063741 526581887 292105439 863200070 560044721 194866728 265700927 930129274 576654611 251207348 558647064 129328316 525247231 219028327 276319714 150364733 233928743 961053820 442252200 532839520 832264464 493518242 94622856 319514430 498219924 395726970 126002231 305805092 473787230 424055579 506883708 524361489 233641585 573323918 72342448 999382328 742286241 407445331 987510596 915492740 569981208 510360026 660755003 498610190 424283858 615915786 303842731 722225577 507528993 891073726 234645312 839492695 290412330 602111043 710946233 774527441 701316966 82484443 738425194 928598019 142103587 641010237 588467896 518106510 508791808 213861139 27767456 770534980 154425972 514854778 340660529 93814703 36701256 224165765 243484685 662192010 70192152 117780411 885916907 532378183 73406678 56193941 564496920