0 1 1 0 2 1 3 1 4 1 5 2 6 3 7 2 8 5 9 5 10 6 11 9 12 11 13 11 14 18 15 19 16 23 17 31 18 36 19 40 20 56 21 60 22 73 23 92 24 105 25 121 26 155 27 170 28 204 29 247 30 280 31 325 32 397 33 440 34 521 35 615 36 695 37 805 38 954 39 1063 40 1244 41 1442 42 1626 43 1873 44 2176 45 2431 46 2813 47 3221 48 3623 49 4146 50 4751 51 5309 52 6086 53 6905 54 7746 55 8807 56 9992 57 11154 58 12685 59 14290 60 15986 61 18065 62 20342 63 22669 64 25604 65 28681 66 31991 67 35955 68 40248 69 44755 70 50253 71 56029 72 62316 73 69695 74 77641 75 86131 76 96220 77 106855 78 118509 79 131965 80 146418 81 162030 82 180208 83 199438 84 220585 85 244678 86 270531 87 298646 88 330858 89 365049 90 402702 91 445132 92 490665 93 540362 94 596581 95 656433 96 722341 97 795952 98 874981 99 961382 100 1058135 101 1161398 102 1274998 103 1400957 104 1536261 105 1684237 106 1848599 107 2024377 108 2217449 109 2430252 110 2658961 111 2908954 112 3184819 113 3480300 114 3804237 115 4159531 116 4541526 117 4958617 118 5416426 119 5907343 120 6444425 121 7031100 122 7662006 123 8349897 124 9101648 125 9908380 126 10789094 127 11747862 128 12778972 129 13901398 130 15123597 131 16435770 132 17865243 133 19416935 134 21085536 135 22898824 136 24867322 137 26981133 138 29279148 139 31767538 140 34442760 141 37344945 142 40487483 143 43861911 144 47523123 145 51479275 146 55730908 147 60335406 148 65310311 149 70651241 150 76435161 151 82673518 152 89374697 153 96620056 154 104433390 155 112818735 156 121883403 157 131644408 158 142123844 159 153436313 160 165615245 161 178679915 162 192779331 163 207939862 164 224206298 165 241739234 166 260587136 167 280795001 168 302569068 169 325951255 170 351022540 171 378007088 172 406976901 173 438018455 174 471416556 175 507238584 176 545621631 177 586877713 178 631115551 179 678486453 180 729383142 181 783913956 182 842301263 183 904978468 184 972111231 185 1043949833 186 1121035351 187 1203540994 188 1291816566 189 1386463287 190 1487734366 191 1596028482 192 1712090876 193 1836195920 194 1968881361 195 2110980558 196 2262880077 197 2425197939 198 2598960643 199 2784598156 200 2982922370 201 3195087909 202 3421682644 203 3663644952 204 3922389222 205 4198581703 206 4493430462 207 4808535025 208 5144784270 209 5503579931 210 5886871819 211 6295680893 212 6731783234 213 7197394668 214 7693850257 215 8223216375 216 8788182382 217 9390296208 218 10032142730 219 10716791682 220 11446234007 221 12223482591 222 13052248790 223 13934855995 224 14875033841 225 15877035098 226 16943807288 227 18079702930 228 19289845822 229 20577690703 230 21948578873 231 23408401612 232 24961491418 233 26614086412 234 28373262211 235 30244111138 236 32234232731 237 34351786300 238 36603095924 239 38997040907 240 41543392850 241 44249597311 242 47126404565 243 50185110708 244 53434885509 245 56888291629 246 60558821848 247 64457281100 248 68598798416 249 72999003606 250 77671108508 251 82632792122 252 87902678527 253 93496338998 254 99434966311 255 105740169969 256 112430871525 257 119531830958 258 127068739614 259 135063893255 260 143546854007 261 152547470002 262 162092686655 263 172217031031 264 182955914494 265 194341070262 266 206413576400 267 219214613482 268 232782348324 269 247164738028 270 262410541442 271 278564672202 272 295684008070 273 313825289840 274 333042306586 275 353401427920 276 374969709819 277 397810390123 278 422001964087 279 447622497399 280 474747435610 281 503468321814 282 533877248119 283 566062819306 284 600133031011 285 636195116081 286 674354421245 287 714736816131 288 757468583494 289 802673304230 290 850499131352 291 901093108949 292 954601712411 293 1011197501037 294 1071053356168 295 1134340902514 296 1201262826052 297 1272020395774 298 1346816456568 299 1425886919913 300 1509468044947 301 1597797215674 302 1691151001264 303 1789804368779 304 1894037159214 305 2004171044775 306 2120528301431 307 2243436017620 308 2373270637139 309 2510407073446 310 2655229999218 311 2808176920000 312 2969686604974 313 3140208120589 314 3320252625487 315 3510330279852 316 3710968048816 317 3922759546089 318 4146300968865 319 4382206742983 320 4631169348773 321 4893881560223 322 5171062916983 323 5463516969760 324 5772052204217 325 6097506566390 326 6440816081811 327 6802919556004 328 7184796424200 329 7587531975415 330 8012220346459 331 8460000784951 332 8932135772059 333 9429894866117 334 9954607313555 335 10507735729168 336 11090757794147 337 11705217829847 338 12352815035071 339 13035262659079 340 13754359572039 341 14512072723306 342 15310393687910 343 16151409989074 344 17037403902168 345 17970682601620 346 18953673871515 347 19989017435820 348 21079391967780 349 22227611641483 350 23436735719362 351 24709864733442 352 26050266695275 353 27461477074192 354 28947091319637 355 30510893371935 356 32156975919541 357 33889497055382 358 35712844753836 359 37631744844795 360 39651013507187 361 41775725963296 362 44011346844637 363 46363441116842 364 48837886270758 365 51440987075244 366 54179181895364 367 57059261574308 368 60088508755426 369 63274356211009 370 66624658188817 371 70147809997546 372 73852401402803 373 77747497813894 374 81842786645813 375 86148175537788 376 90674136658246 377 95431828251433 378 100432687793566 379 105688790104435 380 111212997861629 381 117018491583261 382 123119203485202 383 129529936955892 384 136265891650283 385 143343116100722 386 150778658279146 387 158590018683880 388 166795693630004 389 175415287183278 390 184468959974461 391 193977997364831 392 203964954446498 393 214453023166614 394 225466708797422 395 237031927100214 396 249175368418283 397 261925206544367 398 275311230707200 399 289364117455583 400 304116268589191 401 319601884189843 402 335856233576418 403 352916534820000 404 370822064036083 405 389613322820817 406 409333071234960 407 430026364777546 408 451739724157093 409 474522221021601 410 498425552203118 411 523503093960771 412 549811169820321 413 577409036515727 414 606357945377129 415 636722476414238 416 668570561987346 417 701972420105975 418 737002104178247 419 773737419349375 420 812258869785070 421 852651290921519 422 895003803306965 423 939408618905258 424 985962928269063 425 1034768724500707 426 1085931633020239 427 1139562900749903 428 1195779256523398 429 1254701586974776 430 1316457226508594 431 1381179661241321 432 1449007241234990 433 1520085595823243 434 1594567371974558 435 1672610780179379 436 1754382364075724 437 1840056551148976 438 1929814252194161 439 2023845784157140 440 2122350452118582 441 2225534970970049 442 2333616804930545 443 2446823525450143 444 2565391309220230 445 2689568464080494 446 2819614813838813 447 2955800008872891 448 3098407541350269 449 3247733863683758 450 3404086805210763 451 3567789813239930 452 3739181092738732 453 3918611828829920 454 4106451001679278 455 4303084210995421 456 4508912043130474 457 4724355158608563 458 4949853130832722 459 5185862616408776 460 5432863114825078 461 5691355435935289 462 5961860064408187 463 6244923247566254 464 6541115468774367 465 6851029618403735 466 7175287868122629 467 7514539709161152 468 7869460380631240 469 8240758137779674 470 8629172286778033 471 9035471430900202 472 9460461658100782 473 9904984068327657 474 10369913357322915 475 10856166476138559 476 11364700144901303 477 11896509276600411 478 12452636710406047 479 13034170136673922 480 13642240959727921 481 14278034595528968 482 14942787373013407 483 15637785273212940 484 16364375480374746 485 17123962604034357 486 17918007984574475 487 18748041918276194 488 19615659846561026 489 20522521592753993 490 21470365049620781 491 22461001589598686 492 23496316027573369 493 24578281112392408 494 25708952897534373 495 26890470713818570 496 28125073366824062 497 29415093619938095 498 30762959092165020 499 32171209414035713 500 33642490668899279 501 35179556409895277 502 36785286805519574 503 38462682076750906 504 40214864686697451 505 42045099628508198 506 43956787826016136 507 45953468590496037 508 48038842229415266 509 50216762320114062 510 52491239646219691 511 54866466167891554 512 57346807275762936 513 59936806191274125 514 62641210644887367 515 65464963876701560 516 68413210896094988 517 71491326783167774 518 74704907703223533 519 78059777888499188 520 81562021100887402 521 85217970267188021 522 89034216788575091 523 93017643939820365 524 97175416576045216 525 101514991499172185 526 106044154550270948 527 110771008817409092 528 115703987906585263 529 120851895346415344 530 126223892958584367 531 131829515616263235 532 137678714967237236 533 143781846200056851 534 150149686415708692 535 156793481115085851 536 163724931264631125 537 170956213704732263 538 178500032692569192 539 186369605283291281 540 194578686221213681 541 203141622791975518 542 212073340701865213 543 221389371702062709 544 231105914366791720 545 241239818247944962 546 251808617047310664 547 262830593362758431 548 274324763622007760 549 286310914865973441 550 298809676452156396 551 311842503282862721 552 325431719439607560 553 339600594652760699 554 354373328698602857 555 369775099747050295 556 385832149013190145 557 402571763552799405 558 420022333053309361 559 438213440221230422 560 457175845278491678 561 476941548844820060 562 497543891965460293 563 519017539227918400 564 541398552030946217 565 564724495528769486 566 589034424165567034 567 614368962753030708 568 640770424796345422 569 668282797031551500 570 696951833259492915 571 726825181029001262 572 757952369547737050 573 790384913458007477 574 824176452986754739 575 859382741456846983 576 896061764706663371 577 934273891358962916 578 974081864968121027 579 1015550936024977962 580 1058749028195523069 581 1103746730950692889 582 1150617450730473704 583 1199437589459670992 584 1250286543468098323 585 1303246870507943553 586 1358404487251748970 587 1415848669949826883 588 1475672244884416155 589 1537971800793178036 590 1602847697970158634 591 1670404278605318886 592 1740750101824454014 593 1813997956265650920 594 1890265099057550125 595 1969673509039592230 596 2052349910567157486 597 2138426037341301637 598 2228038912639792170 599 2321330878959205447 600 2418449896806538356 601 2519549847115693283 602 2624790575701370193 603 2734338223009052108 604 2848365558867025576 605 2967052035936755215 606 3090584162107667856 607 3219155862368287815 608 3352968551655779600 609 3492231545708508110 610 3637162461737298097 611 3787987304447461404 612 3944940928868070529 613 4108267474225114262 614 4278220475210152794 615 4455063372465514173 616 4639069993119728887 617 4830524680693182695 618 5029722868891568841 619 5236971602847872901 620 5452589701698833197 621 5676908391303719505 622 5910271881725345836 623 6153037555534528133 624 6405576677593392003 625 6668275022506476757 626 6941533104988106217 627 7225766962364688821 628 7521408849946023972 629 7828907506257109636 630 8148729029301359759 631 8481357633340505481 632 8827295968031848259 633 9187066084279152853 634 9561210273197528159 635 9950291431815214111 636 10354894142946743241 637 10775625589693090503 638 11213115989936057496 639 11668019786412239991 640 12141016660835217714 641 12632812029858008563 642 13144138373753152569 643 13675756343517471343 644 14228455344289527321 645 14803054999401557533 646 15400406378438444510 647 16021392661018661739 648 16666930769277001138 649 17337972710452739442 650 18035506351460418593 651 18760557217461634542 652 19514189981521675146 653 20297509343401107290 654 21111662032737081702 655 21957838439832947518 656 22837273634347150100 657 23751249572027229644 658 24701096904551976965 659 25688196132451951200 660 26713980060335047367 661 27779935780699648570 662 28887606002980135708 663 30038591757992550673 664 31234554599987123679 665 32477218107551347927 666 33768370889767843065 667 35109869002755274381 668 36503637671692863258 669 37951674601838524269 670 39456052661331075411 671 41018921822103863537 672 42642512837155814324 673 44329140187811350454 674 46081204301535244790 675 47901195601823542807 676 49791697780579213610 677 51755390293443752485 678 53795052854202499175 679 55913569033211324658 680 58113929098651832263 681 60399234966039692925 682 62772704193896419526 683 65237673175421693233 684 67797602627406313599 685 70456081987831529832 686 73216833038728958301 687 76083715950561290144 688 79060734165455125501 689 82152038460918163872 690 85361933648665164130 691 88694883953190533790 692 92155517611832526224 693 95748634251141800060 694 99479210859378277688 695 103352406939395851097 696 107373572678911147139 697 111548255533262499058 698 115882206044143930898 699 120381386835841160328 700 125051979924552448465 701 129900393228281152572 702 134933270526002380904 703 140157499518530825084 704 145580219163516376029 705 151208830640973137529 706 157051006303111301279 707 163114697871107917878 708 169408148568418013531 709 175939902995719626591 710 182718816348365013012 711 189754067775226275189 712 197055171341369993102 713 204631986317355810352 714 212494731954092029527 715 220653999583684123757 716 229120764169293928416 717 237906400571718331034 718 247022696981127526989 719 256481867797016927628 720 266296571611537122898 721 276479926040744418824 722 287045522158976332067 723 298007444297079549308 724 309380286501871874796 725 321179168617608258773 726 333419758165260863273 727 346118288521794913141 728 359291576915638497570 729 372957048513080723536 730 387132756589110782759 731 401837402558557052304 732 417090362584746920620 733 432911709862413669851 734 449322237002351067009 735 466343485323035952090 736 483997769568891845311 737 502308202806315981529 738 521298728771808451175 739 540994149182285978785 740 561420151521273678588 741 582603344647085403771 742 604571289080215610312 743 627352527882549718175 744 650976625968805521223 745 675474203572831682465 746 700876970671582469533 747 727217770256225950669 748 754530615436370592712 749 782850727667414998763 750 812214584507688955738 751 842659960618533591235 752 874225970334124410310 753 906953120226119895979 754 940883354547334087686 755 976060102471525881101 756 1012528336091234261699 757 1050334620632472352619 758 1089527167008200476134 759 1130155895650749234928 760 1172272492151681074401 761 1215930465541308850965 762 1261185218700052260716 763 1308094109836768411268 764 1356716517263356828141 765 1407113916884436605544 766 1459349950295950513956 767 1513490496571529468224 768 1569603757716687026162 769 1627760333906824661942 770 1688033303204544032039 771 1750498315597658475065 772 1815233676311588825311 773 1882320434102221466144 774 1951842484933560419482 775 2023886664013754987166 776 2098542843762599239607 777 2175904047894627378105 778 2256066553297603657147 779 2339129998475829720944 780 2425197509297410076374 781 2514375811524080724592 782 2606775351044999401276 783 2702510432232700628021 784 2801699342463744057539 785 2904464485135425691615 786 3010932532131917271358 787 3121234561340082302977 788 3235506204022114204385 789 3353887812554082902932 790 3476524612541237514372 791 3603566865772279233936 792 3735170055022331770402 793 3871495052010998683354 794 4012708297820833698970 795 4158982006191799552005 796 4310494349244267202397 797 4467429656871433767327 798 4629978640665006689409 799 4798338598937948959216 800 4972713637344330763254 801 5153314915185087408239 802 5340360872034190666533 803 5534077471441045801663 804 5734698472172281639297 805 5942465678331335806455 806 6157629208841304406218 807 6380447795762121087371 808 6611189060665041296397 809 6850129812170403671549 810 7097556374394401510668 811 7353764891900548461773 812 7619061658522684475555 813 7893763478554079873734 814 8178198003586672355151 815 8472704095402312708557 816 8777632223554845836820 817 9093344836944141537136 818 9420216764643684188924 819 9758635653061611790799 820 10109002376219307587563 821 10471731477914287628854 822 10847251652824814173352 823 11236006198976984624099 824 11638453505874860775688 825 12055067583428104050958 826 12486338561367713441395 827 12932773227487586299553 828 13394895609614402686788 829 13873247526227782861831 830 14368389180359884663196 831 14880899799325089074116 832 15411378242252505018444 833 15960443654688484055047 834 16528736172328190926689 835 17116917590650486185428 836 17725672086865003391586 837 18355706993375141295066 838 19007753536359469658102 839 19682567631195731341775 840 20380930733121410582362 841 21103650651081327084427 842 21851562424580907126577 843 22625529258494733298140 844 23426443420386218593223 845 24255227206234268917552 846 25112833968320610491667 847 26000249103705660153192 848 26918491118349375008377 849 27868612756499392654961 850 28851702090160542862471 851 29868883690634865173273 852 30921319870093535058242 853 32010211881370584892005 854 33136801208319293759272 855 34302370929762394525179 856 35508247041401649822524 857 36755799875919106992484 858 38046445602084290719626 859 39381647680095063829152 860 40762918425065170245959 861 42191820653616026585922 862 43669969286780389923536 863 45199033070094804024419 864 46780736382960774071882 865 48416861002817340254423 866 50109247998163206964917 867 51859799715580140465687 868 53670481722106671041820 869 55543324887161587717466 870 57480427565510377211733 871 59483957734423105386111 872 61556155284031520447382 873 63699334414213986621784 874 65915885986820850180349 875 68208280043743904581062 876 70579068439581464568251 877 73030887428973537200022 878 75566460435748637528075 879 78188600943046186849834 880 80900215340052940652287 881 83704305965475546684751 882 86603974281260471081293 883 89602424002930127452959 884 92702964445324619433353 885 95909014006038511978645 886 99224103608440348055918 887 102651880377693539098027 888 106196111465160907641551 889 109860687833295537738737 890 113649628295351695548209 891 117567083712203523348152 892 121617341153918408690097 893 125804828336875476058229 894 130134118230352199321322 895 134609933629953757800265 896 139237152032076806728662 897 144020810688094506614988 898 148966111631295654295663 899 154078427029248260944828 900 159363304730221962671181 901 164826473785985587788782 902 170473850329797029048402 903 176311543660539599683387 904 182345862311203376640452 905 188583320501240503468360 906 195030644811748169068741 907 201694780850577700180305 908 208582900336073225132834 909 215702408417929620478586 910 223060950998509357154520 911 230666422506495379592473 912 238526973927127674901752 913 246651020840961369753575 914 255047251955531781369078 915 263724637910545324348525 916 272692440105298593646753 917 281960220058593699550276 918 291537849064954631351892 919 301435517884250393558920 920 311663747011166665044402 921 322233397261110821050648 922 333155680407142224743755 923 344442170443227539881138 924 356104815190648496202977 925 368155947970499166687548 926 380608299957770011355767 927 393475012902558474011234 928 406769651939788964712030 929 420506219135059246609967 930 434699167429036229977132 931 449363414690242212194325 932 464514358568456645561669 933 480167891775269477216325 934 496340417501316210248057 935 513048865698108434936653 936 530310709824054287799891 937 548143983752982303112262 938 566567299622517425246198 939 585599866180825327250404 940 605261507331307562221949 941 625572681692182348522587 942 646554502698181206714624 943 668228758933311959848189 944 690617935566332263506595 945 713745236369235997342556 946 737634606010949599743523 947 762310753541716156700084 948 787799176512260565299815 949 814126185410200289195663 950 841318929389642866934514 951 869405422684555496551309 952 898414571394062917404331 953 928376201664068338817229 954 959321088614007281370362 955 991280985688436220113840 956 1024288655524581156840828 957 1058377901623758492669912 958 1093583600515054955560474 959 1129941735555859767673343 960 1167489431609105810073583 961 1206264990278883196848510 962 1246307926922563324687708 963 1287659008610108001050204 964 1330360292724545206004404 965 1374455167480648674650259 966 1419988393477370048822264 967 1467006145973550844003721 968 1515556059244893579361516 969 1565687272059285759278452 970 1617450473976700775240663 971 1670897953896423526390528 972 1726083649825625586726192 973 1783063199573964861421385 974 1841893993885915720587048 975 1902635230896037468357483 976 1965347971633797174010090 977 2030095198160749858060917 978 2096941873153310025712522 979 2165955000659835387585320 980 2237203689712455140210918 981 2310759219506500147464829 982 2386695105904443756742972 983 2465087171022690282888459 984 2546013614532131640344422 985 2629555086436017365513785 986 2715794763190467366509654 987 2804818425685296703038694 988 2896714538884290764191647 989 2991574335075469976105838 990 3089491899155952600950064 991 3190564255762747458526692 992 3294891460317099082925861 993 3402576692279427705619332 994 3513726350470529825499021 995 3628450152619690685123114 996 3746861237331295665740668 997 3869076268344550419890648 998 3995215543374899560320748 999 4125403105585274954592960 1000 4259766857616394819281669