0 0 1 0 2 1 3 1 4 0 5 1 6 5 7 5 8 1 9 5 10 18 11 18 12 6 13 18 14 55 15 55 16 23 17 56 18 150 19 150 20 73 21 155 22 376 23 377 24 205 25 394 26 885 27 890 28 526 29 940 30 1979 31 1996 32 1261 33 2128 34 4240 35 4290 36 2863 37 4611 38 8764 39 8895 40 6213 41 9630 42 17561 43 17877 44 12980 45 19479 46 34243 47 34961 48 26246 49 38310 50 65187 51 66739 52 51576 53 73501 54 121455 55 124673 56 98831 57 137922 58 221949 59 228395 60 185176 61 253675 62 398527 63 411058 64 340015 65 458181 66 704188 67 727916 68 613003 69 813940 70 1226065 71 1269970 72 1086877 73 1424074 74 2105855 75 2185433 76 1897812 77 2456818 78 3571622 79 3713195 80 3267420 81 4183715 82 5986943 83 6234600 84 5552555 85 7038755 86 9926266 87 10352881 88 9322207 89 11709185 90 16289552 91 17014129 92 15475303 93 19273836 94 26475545 95 27690276 96 25419768 97 31412439 98 42641936 99 44653985 100 41342821 101 50720208 102 68093464 103 71389007 104 66616315 105 81177500 106 107857549 107 113199178 108 106400643 109 128846910 110 169533239 111 178106951 112 168539129 113 202901927 114 264536345 115 278171897 116 264875112 117 317136321 118 409916388 119 431415505 120 413180742 121 492167513 122 630994837 123 664616915 124 639966950 125 758636756 126 965177515 127 1017354264 128 984556814 129 1161834430 130 1467438887 131 1547819976 132 1504961906 133 1768354501 134 2218176880 135 2341151538 136 2286320929 137 2675625729 138 3334415221 139 3521315285 140 3452964632 141 4025504606 142 4985715409 143 5267989489 144 5185591950 145 6023581673 146 7416689924 147 7840455100 148 7745623235 149 8966493900 150 10978734601 151 11611274417 152 11509594108 153 13280415024 154 16174592745 155 17113593843 156 17017545207 157 19575099097 158 23720719167 159 25107346030 160 25040854560 161 28719491424 162 34634255542 163 36671584737 164 36676988865 165 41947148659 166 50353929638 167 53332840763 168 53481403680 169 61002730805 170 72907572201 171 77242976599 172 77650550956 173 88344909186 174 105143505670 175 111424859790 176 112274984103 177 127426536262 178 151049196501 179 160110689110 180 161688323466 181 183080323373 182 216188797747 183 229206547149 184 231946941405 185 262048194947 186 308302232613 187 326928453741 188 331487409077 189 373705763360 190 438123196198 191 464670820130 192 472025024441 193 531051092008 194 620493073345 195 658189020108 196 669778442863 197 752050512213 198 875873855965 199 929205469410 200 947134294022 201 1061465613979 202 1232397752238 203 1307585313206 204 1334903968760 205 1493327103860 206 1728636991226 207 1834276405740 208 1875375479143 209 2094276216650 210 2417337842515 211 2565272441348 212 2626430312022 213 2928066968182 214 3370442655700 215 3576942686690 216 3667083564722 217 4081618192351 218 4685828693501 219 4973183039805 220 5104921947144 221 5673130072521 222 6496330370630 223 6894989246085 224 7086066972125 225 7862944921423 226 8981792176183 227 9533244563001 228 9808490868779 229 10868048147990 230 12385135901419 231 13145764595143 232 13539774716613 233 14981387974919 234 17033734421725 235 18079968998421 236 18640740413000 237 20597561297061 238 23367786593774 239 24802975904700 240 25596834073683 241 28246893546199 242 31977911331836 243 33941469354681 244 35059718855875 245 38640565235441 246 43654858976396 247 46334410153403 248 47902289171162 249 52730248985345 250 59455120018609 251 63102594318466 252 65291296088738 253 71786772106613 254 80787353141715 255 85740272064172 256 88783039808541 257 97503680068825 258 109526030645735 259 116235602572080 260 120449221702348 261 132133333439385 262 148160604474278 263 157228735846864 264 163042160672795 265 178665437459703 266 199990951147828 267 212218910511877 268 220211300486583 269 241060822422925 270 269383012904319 271 285835298166230 272 296786436888235 273 324557046579072 274 362102611082510 275 384190617725827 276 399147592626397 277 436067212916576 278 485750614888282 279 515342049631145 280 535707240519261 281 584699570591765 282 650329319560259 283 689891033008261 284 717537968645115 285 782433383400408 286 868978422141003 287 921762550593790 288 959188140086364 289 1044996662947695 290 1158929885937978 291 1229216029993758 292 1279740182036030 293 1393004279028769 294 1542744894955865 295 1636154689696225 296 1704181552430049 297 1853431426830738 298 2049913823077114 299 2173818884617305 300 2265178068635423 301 2461518399190779 302 2718922695370561 303 2882972830605801 304 3005364266356235 305 3263229277999389 306 3599918279616287 307 3816724359468290 308 3980297202870463 309 4318421026548695 310 4758140323374512 311 5044155771974344 312 5262260406190345 313 5704922425220460 314 6278335565904335 315 6654992546318000 316 6945155735260056 317 7523776720156815 318 8270426539820780 319 8765598296233325 320 9150785558794899 321 9905970725252730 322 10876782011585931 323 11526662305244241 324 12036909394139770 325 13021060160670420 326 14281529170036160 327 15133044383290300 328 15807562369004068 329 17088210891375235 330 18722465332314484 331 19836365940884159 332 20726253074980619 333 22390314278253816 334 24506275211030815 335 25961092601084875 336 27132822438215468 337 29292009353136498 338 32027946430272985 339 33925050540277180 340 35464951706266863 341 38262664058710156 342 41795510659787987 343 44265566248346798 344 46285567218901765 345 49905643670547177 346 54461532498106912 347 57672730207877786 348 60317715590380770 349 64995540826800470 350 70863138059040032 351 75031674885349739 352 78488891821458814 353 84525475847132170 354 92072838725323115 355 97476246010195013 356 101987315235067404 357 109767119986720440 358 119462985855125225 359 126457057731555095 360 132333289509282145 361 142346774951703558 362 154787418053016249 363 163827687081598473 364 171469585117158460 365 184341692887701053 366 200284769509044434 367 211953718656769231 368 221875784398142118 369 238401883629419490 370 258809039905165705 371 273850542882325051 372 286712779839560508 373 307903981613216130 374 333994437969370015 375 353357297958379331 376 370005175003053526 377 397145396997492557 378 430463269268647907 379 455356197422636110 380 476871279115776479 381 511589032648530186 382 554087827441159213 383 586048789659392140 384 613812802306788680 385 658171407554996329 386 712319969396595007 387 753303560527789810 388 789079361862642431 389 845690207341518005 390 914605435576614468 391 967092848566531357 392 1013126640050971700 393 1085291230998070107 394 1172904172003065870 395 1240041457747959191 396 1299191662624215210 397 1391079600878710460 398 1502343113347141011 399 1588114827055167640 400 1664014405224115378 401 1780886173290430634 402 1922034331484833414 403 2031481397059107827 404 2128742042164745485 405 2277227603488693789 406 2456099431764176750 407 2595592205628139635 408 2720060947382954207 409 2908507817999924245 410 3134950945290948637 411 3312531121632765449 412 3471612432146910313 413 3710520141682367027 414 3996893656407445655 415 4222701945404830642 416 4425761638484406631 417 4728323522947133054 418 5090123855199797110 419 5376934429570811425 420 5635805589563453334 421 6018583818198366841 422 6475223070604410536 423 6839110791698810486 424 7168726848858696295 425 7652492694973570403 426 8228265722473462772 427 8689438342873276584 428 9108624440377472272 429 9719403321152297090 430 10444688311575294180 431 11028523473274664910 432 11560984710283977461 433 12331354760148831598 434 13244102443469112715 435 13982438674900638419 436 14657992982722283836 437 15628697275806035071 438 16776276619033322538 439 17709019078424513870 440 18565133787056355525 441 19787080258182490540 442 21228564106963133337 443 22405680009465495373 444 23489385071237037285 445 25026125276759989981 446 26835118519287314470 447 28319114613482149473 448 29689382557279531677 449 31620181366592109405 450 33888317593075865969 451 35757313440948576911 452 37488017152196437229 453 39911651119601304896 454 42752912370522502175 455 45104449413336476083 456 47288034646378399201 457 50327488216717212842 458 53883537396162575380 459 56839295927330561085 460 59591337123950748199 461 63399604232201136878 462 67846362493420027969 463 71557998010428125310 464 75022844818551126130 465 79790090381476961912 466 85345843950105919184 467 90002202503193334266 468 94359971941794150831 469 100322365062833907200 470 107257749585172476173 471 113093780602731488445 472 118569008021596414821 473 126019608687051998755 474 134669896743142859255 475 141977653725379047759 476 148849986892647142243 477 158152153252955499744 478 168932365143606988340 479 178074572406254875100 480 186691980052422705463 481 198295867357282878170 482 211719340274214622653 483 223146111022534501583 484 233941183409643398345 485 248404032294754511626 486 265105222883407357609 487 279374644457475125746 488 292884693188045948285 489 310895759126219748805 490 331658224532061902392 491 349461685716218457047 492 366353508089679539714 493 388764671261325648568 494 414555380390311163475 495 436748709305999307480 496 457849075174414689813 497 485712397838626543727 498 517723775458694386476 499 545365492115468972245 500 571698645769731629953 501 606312420947528937475 502 646013831696615885368 503 680412105646850068710 504 713245860707439953500 505 756211031903809956901 506 805411780445832565943 507 848182031903974585766 508 889084384284875610621 509 942373623473680212345 510 1003299994446111952432 511 1056435499640552088720 512 1107344105427722578558 513 1173386330544856660901 514 1248775733813018194600 515 1314734107851754347110 516 1378041485108881023874 517 1459825196841266128879 518 1553041139463979659180 519 1634850191433057824355 520 1713508126476027077953 521 1814707668861735019451 522 1929880068594297712988 523 2031267276638051800503 524 2128914669056207115265 525 2254044395388960916476 526 2396240709769573233163 527 2521791475811482451838 528 2642910769982721034957 529 2797513156082848646815 530 2972946960130219818839 531 3128297907512467058819 532 3278406364694870214835 533 3469281393431683799718 534 3685566438507619994730 535 3877641350630900038260 536 4063524754779706520536 537 4299009444043237172050 538 4565468919451326008521 539 4802766530921605595315 540 5032764541108760997390 541 5323073356533157355395 542 5651116112645989306257 543 5944060913455873761257 544 6228415233759265955840 545 6586054382543683877993 546 6989632330066202322195 547 7351001896344764611741 548 7702280799501880949282 549 8142552120775520934235 550 8638715979505546148749 551 9084161183408160356067 552 9517776780427269507744 553 10059390224383938813973 554 10668964357535250144530 555 11217642232290056701968 556 11752480326190138080540 557 12418297960813956889186 558 13166699318534275061830 559 13842042480405668280360 560 14501228997741466604977 561 15319168232610176297884 562 16237399585412298711001 563 17068051083585865375763 564 17879884085516001155280 565 18884013517540124530824 566 20009867359944784246947 567 21030815807112885832377 568 22029898113880454448397 569 23261766272027798877280 570 24641283225525392405511 571 25895240258494711077848 572 27123854982467685439294 573 28634100507168866880309 574 30323334996600624244810 575 31862405769391534944425 576 33372185787692928802089 577 35222487500072473879270 578 37289644213568320599140 579 39177352024276902980030 580 41031304925995438039675 581 43296742149925203039419 582 45824759671493503861363 583 48138498313929949197791 584 50413460979665385068440 585 53185368766887304483336 586 56275042212349597330819 587 59109044636418190761944 588 61898656768407087917134 589 65288077810045894046070 590 69061830801643705983938 591 72530760654575493536747 592 75949064773993306395174 593 80090920316811376266944 594 84697358795776618239605 595 88940652986492658771294 596 93126450247506943329644 597 98184576933018084282911 598 103803983842925682535178 599 108991100123597657157315 600 114113217473077742033789 601 120286446471618154834773 602 127137408093970871638362 603 133474162619894951281733 604 139737818205757712101720 605 147267308265776679308585 606 155614700959164459779166 607 163350917863244221996891 608 171005409174035628390708 609 180183487367816930388945 610 190348098849872533964198 611 199786838233262974245007 612 209134822440449859005388 613 220315636791766685194721 614 232685750331738977256195 615 244194434133888561403875 616 255603123939196000594492 617 269215472347979255443094 618 284260806997715107935653 619 298284625639726445224885 620 312199288307206471270704 621 328762060121118401488979 622 347050537411690873466596 623 364128595894847934305703 624 381088820098059615158455 625 401229572553983490927321 626 423447472308229570515180 627 444232224957106069577383 628 464891512004848169423979 629 489368806226048021162220 630 516344984113118102732355 631 541625615185542792599828 632 566774960966909735550023 633 596505204400462350286167 634 629240174943127400787710 635 659970711217992123053122 636 690566976227452778098065 637 726656664073958330962956 638 766357508991944425584232 639 803690604142256387296565 640 840890625241424200837083 641 884675046990546043592770 642 932797294739357465613470 643 978124808489002747614788 644 1023326392418825321321260 645 1076416076305020897085022 646 1134713920036058516108994 647 1189715633340738885204873 648 1244606794090122780993064 649 1308943208336730878247305 650 1379529692876121373041994 651 1446231760245788328906187 652 1512849826935580207502528 653 1590772149420228248532013 654 1676191271070450890999635 655 1757036320460521924409001 656 1837838857383136293327067 657 1932163973542490592285059 658 2035477008816245706648946 659 2133408167490401708469395 660 2231358022790872990345963 661 2345476325492365646705666 662 2470365147247600803075968 663 2588926709581752594586220 664 2707593954944544313628645 665 2845584011873153025409403 666 2996474676682572083074385 667 3139932649961641963239580 668 3283616703794055107151326 669 3450382442039445679470450 670 3632592956300513489480829 671 3806079338438238447176859 672 3979955195044572445141629 673 4181389946050798842618297 674 4401306858399018673093995 675 4610992235246833723284010 676 4821285470843418596323395 677 5064468041806745783377610 678 5329757387177690362634371 679 5583057308018877800778880 680 5837253422980913553924177 681 6130682336890980639616563 682 6450541498273112029661851 683 6756363121419808919667036 684 7063457832664015800970225 685 7417331036497278176369937 686 7802789323743168751362188 687 8171826049609575219297800 688 8542624397948385747022551 689 8969173110093920032506480 690 9433450316154333218963393 691 9878533577864529831132717 692 10326007198450210726462580 693 10839894191254888945308983 694 11398828116176325004768715 695 11935347219072578236557691 696 12475060881072405551111465 697 13093855418382336287874848 698 13766411399039231313459921 699 14412814339188352320790355 700 15063434943580686744316721 701 15808178870469308493623696 702 16617056776620961055742805 703 17395447382085780982356889 704 18179351072861886903241455 705 19075233249142374385666579 706 20047590271518724261957273 707 20984439866522749794130935 708 21928435830044172084879045 709 23005595285748215390193585 710 24173906228932297505455305 711 25300901399883720585145538 712 26437094381446921112672267 713 27731576339582885716097458 714 29134657134952261686634375 715 30489709172526238782146847 716 31856526824591726103042436 717 33411420188139430260342869 718 35095645069996691763046243 719 36724091383611893640421365 720 38367507389957601575555166 721 40234297548485001575978488 722 42255045919002817023475255 723 44211079299052904914269820 724 46186068926590696869560590 725 48426245946832289745178366 726 50849621544463133366330442 727 53197989736405986082382799 728 55570261208287060493488268 729 58257230801427058150093435 730 61162103561433175937912533 731 63980129393924690298345964 732 66828182438093000051609515 733 70049535742787205844992093 734 73529965907097363774340160 735 76909947394819450131520501 736 80327519717843644118042523 737 84187728135219668567054421 738 88355842977929135129916437 739 92407903646453703812487945 740 96506877167572424434140704 741 101130490506112527923720771 742 106119896779308380662725433 743 110975369225238866452364203 744 115889220978678944592135355 745 121424661334002480125305351 746 127394491544882054976461671 747 133209932291106106759369399 748 139097830316342882083072744 749 145721890799993271305429965 750 152861599101588129502307911 751 159823550535371234974653059 752 166875213236298209800950896 753 174798390320219065502727752 754 183333434599984862996235290 755 191664070660640988361333602 756 200105529507894349524003500 757 209578340884889432538279328 758 219776912113515004781719956 759 229740728977260503119817480 760 239841159618667831865223192 761 251161626700216397344785214 762 263342615396304681234451331 763 275254357334053771453084024 764 287334173829088124489455715 765 300856680020785644085447943 766 315399103543918511594932412 767 329633148159297761214391257 768 344073589940995068171732088 769 360219363484399884107090555 770 377573517665554120978777977 771 394574984740715852069140353 772 411829466942161069485999980 773 431098981363599145770707493 774 451799626743083073047081255 775 472097521965490908292422450 776 492705067992412477692893043 777 515692705193633953873582857 778 540374653061905370569222228 779 564597413189109596243861475 780 589198545121455924731953946 781 616609927216648465788600866 782 646026455144977542122206762 783 674920326105456600272305040 784 704275855126971390100523380 785 736948322833905601403296107 786 771992925079339259871797986 787 806443680765140438357327833 788 841456918056018836154222558 789 880383717607715310186928775 790 922115784596148116779639436 791 963174383617196250065405225 792 1004917383994440717800348660 793 1051276223280460089900404049 794 1100951348551161188161391530 795 1149864231258745535005774439 796 1199608789641833869572771853 797 1254795540101856506862465644 798 1313901275250640748414687656 799 1372146126547192002276916465 800 1431400373785396691227021726 801 1497068830366184049192470080 802 1567366851704487238394931987 803 1636694799631347217781065692 804 1707246392533054913237114335 805 1785355163173326265487566908 806 1868930981588708947247586115 807 1951416371034209099042086175 808 2035383445300276083493114250 809 2128251227882893549802642830 810 2227572769898827391591024266 811 2325671849210037368085373904 812 2425563107725682966727994103 813 2535933830848545273264326723 814 2653920448984991656123140590 815 2770540539714973108501442656 816 2889326087353884609774249928 817 3020445647003291956659569173 818 3160549386886437615339255597 819 3299130379099597191580684000 820 3440325194737199804362815275 821 3596031818276456804137576288 822 3762333085123990969509472249 823 3926943419301769402824358361 824 4094705682998700935912755750 825 4279536302125584719581580229 826 4476856437919771033705216634 827 4672306107351230128589869605 828 4871552983668978996334497984 829 5090868407671840876810872095 830 5324902121468890392193860582 831 5556875665157213114512989455 832 5793419591646758620705994894 833 6053551751328532608629671327 834 6331022849153310339814190700 835 6606235815298304978952954005 836 6886944869241259391378775484 837 7195369961844147761738938434 838 7524214411607639740529098583 839 7850597367954498937817135095 840 8183583897107313364304511998 841 8549125916915872617559890516 842 8938706971878776274765073867 843 9325621835994740013613927909 844 9720464255143505558162136095 845 10153534158830981299465250408 846 10614895066736372481518344503 847 11073389343278060257181509930 848 11541392835025036063036265394 849 12054269483456212917388772255 850 12600430246661289846140755095 851 13143535709341692918161652409 852 13698038544692717497863501243 853 14305198604995308959139189257 854 14951504351948302115699050375 855 15594587817784745886470667349 856 16251321153025753518358153280 857 16969826360927139155894959392 858 17734356166968101653936378225 859 18495531305745640881454854775 860 19273041643805377054382488110 861 20122993245136671187728984640 862 21027039730840189617067415852 863 21927650364075867394594584804 864 22847795422477564513934325925 865 23852867267644761266659081103 866 24921499040609096014626569447 867 25986686147111814913071462468 868 27075216687215958715452716644 869 28263280381977989204972008930 870 29526001413562056193815442297 871 30785368114143114102617929083 872 32072610400075507006574950378 873 33476468165034705337675613859 874 34967990554031554222138518920 875 36456381743869348343505431204 876 37978037763554351238644408477 877 39636281275462909402818445773 878 41397430600606162287365184315 879 43155846689742293400839858430 880 44953932141990332142698984177 881 46911948682782311928923597328 882 48990724348586165822156816056 883 51067391823486843018189747991 884 53191335220474228512244724710 885 55502486015014488535356384937 886 57955302724151251858698582456 887 60406928030996809817494836911 888 62914858161720757518153320278 889 65641857924010106066444706585 890 68534998749358467292481124626 891 71428236409476876720251369549 892 74388489946185440394070891035 893 77605021470556232285229570815 894 81016338049903485711583256100 895 84429509050140043792088988392 896 87922395359903024441157801784 897 91714998597994841626368354241 898 95735899848540848407090118936 899 99761002320979023875175190280 900 103880868688563434815960032517 901 108351150271389400176678236696 902 113088927852231714520706771635 903 117833989003710928605396166679 904 122691636618929191036981955740 905 127958853363049477057278569072 906 133539400055279099455922020149 907 139131226384196580766307289740 908 144856735758167931360659591872 909 151060814506055717888314986285 910 157631800909788786184120742102 911 164219193137118503257036352015 912 170965227274221358222340531512 913 178270293658400679467877728437 914 186004879329898132472429841930 915 193762389383261773745107417295 916 201708054265274194386224725918 917 210306554881861477717524851895 918 219407722490150865513859693668 919 228540042557303331452920274535 920 237895397543762832184864928399 921 248012913837683407922593746817 922 258718529384548639910732445757 923 269465617777224920266196895516 924 280476943681235783548960309615 925 292377811888103540999840159695 926 304966530826952121504360074452 927 317609596493288454238556184095 928 330565546690239625325903256495 929 344559416802049238070772532595 930 359357575378937700518958421970 931 374226062749282883799967666222 932 389464843105159639564539673673 933 405914331437183329211508659461 934 423303985187749983293874798645 935 440783724070188229173765703079 936 458701471185004612470089440210 937 478031086192034706843849143726 938 498459383754331649699848552282 939 519002095716200774883581870340 940 540062650485231605646057673094 941 562769200552592417575850998075 942 586759311367629538467815104624 943 610893695029737820640510005410 944 635640000430194557124977173725 945 662304726079689205794342354106 946 690468575807197927277155872668 947 718813229410807821644451719461 948 747880618417117303389068706712 949 779183330449113997160935860995 950 812236438785941768913704296232 951 845514920045738827175542831492 952 879646602462899795576103834740 953 916382152844819141614192363237 954 955160915775437378000263758395 955 994219287301786889070782427378 956 1034284394007607517434954041569 957 1077381858787984733646883812387 958 1122863672134354921238041667892 959 1168690936630986400249690097260 960 1215705537301439512940685530055 961 1266250551599279776874254677461 962 1319577236240490076332488212112 963 1373329130454954663593291058385 964 1428480707544167974070844994950 965 1487741463030006896503427181002 966 1550246525680299726666639824074 967 1613273217083821548614187723236 968 1677949156062776307376140033691 969 1747406652804177123985982738115 970 1820647001328071164476494980357 971 1894525318320490472312032593428 972 1970346063586236585630607920406 973 2051729302398977894895845953376 974 2137522133099535866061178901570 975 2224093060009789811585235764753 976 2312950689351372308310080909549 977 2408277599864624543910917049527 978 2508743288075512065095938767789 979 2610155572475439150716670152540 980 2714258662704850532165591962226 981 2825883688504074327229538075121 982 2943495645533868125812428911678 983 3062256499843435872318303139521 984 3184182294684154797591268892945 985 3314851702778426432072788739686 986 3452494314546182346288974649104 987 3591528349394084598439144578755 988 3734283400864046797076656883252 989 3887199551375969948194237729985 990 4048235490108031075958449460072 991 4210953196663672615175558757301 992 4378043836332940087229899965466 993 4556939843232289000661074917700 994 4745288247010238382509394791165 995 4935665553254486692441191705349 996 5131179763746921642973153496043 997 5340406202678063895330025788868 998 5560633452637967431786069077395 999 5783304118589895409464172696780 1000 6012006622962685078226083441835