72 1 73 0 74 2 75 0 76 5 77 0 78 10 79 0 80 20 81 0 82 36 83 0 84 65 85 0 86 110 87 0 88 185 89 0 90 290 91 1 92 461 93 4 94 702 95 11 96 1066 97 26 98 1572 99 57 100 2311 101 114 102 3319 103 218 104 4750 105 400 106 6673 107 707 108 9332 109 1214 110 12916 111 2025 112 17750 113 3291 114 24164 115 5242 116 32743 117 8191 118 44027 119 12565 120 58913 121 18992 122 78374 123 28291 124 103805 125 41573 126 136833 127 60372 128 179703 129 86683 130 235060 131 123118 132 306259 133 173254 134 397965 135 241604 136 515328 137 334077 138 665640 139 458363 140 857262 141 624388 142 1101829 143 844552 144 1412296 145 1135179 146 1807313 147 1516655 148 2307103 149 2014739 150 2940963 151 2662206 152 3740831 153 3500382 154 4752187 155 4580350 156 6025485 157 5967181 158 7630960 159 7740993 160 9647188 161 10002058 162 12182672 163 12874786 164 15359632 165 16513648 166 19344128 167 21108751 168 24324922 169 26896113 170 30555219 171 34164828 172 38324980 173 43271906 174 48017623 175 54654303 176 60075737 177 68848662 178 75077059 179 86509593 180 93692686 181 108439022 182 116786571 183 135613035 184 145371630 185 169222584 186 180734405 187 210713959 188 224390248 189 261845359 190 278245276 191 324748906 192 344553458 193 402008469 194 426124132 195 496748902 196 526289290 197 612751660 198 649165801 199 754574027 200 799652117 201 927717915 202 983755114 203 1138810780 204 1208630487 205 1395820211 206 1482998503 207 1708332388 208 1817261524 209 2087854043 210 2224025473 211 2548182975 212 2718324738 213 3105857420 214 3318296914 215 3780687457 216 4045576822 217 4596344937 218 4926149820 219 5581128681 220 5990997072 221 6768828768 222 7277190080 223 8199730049 224 8828902916 225 9921835502 226 10698822930 227 11992338064 228 12949653841 229 14479196882 230 15655974225 231 17463243499 232 18906464226 233 21040441783 234 22806300112 235 25324638875 236 27480380665 237 30450783808 238 33076513946 239 36578799984 240 39769967164 241 43897831205 242 47767749254 243 52631663270 244 57314950015 245 63044667691 246 68700475600 247 75449013776 248 82265897274 249 90212900561 250 98413170565 251 107770555981 252 117616741004 253 128633225797 254 140434036438 255 153402908602 256 167522059871 257 182787512308 258 199651556887 259 217619123913 260 237729462342 261 258874864227 262 282818323828 263 307701759356 264 336166528178 265 365444623097 266 399234664202 267 433679894862 268 473736240152 269 514253507267 270 561673477763 271 609326040230 272 665391768282 273 721424098004 274 787628504400 275 853501145516 276 931585504066 277 1009006154008 278 1100995234658 279 1191965527384 280 1300217521484 281 1407075403467 282 1534328928494 283 1659810714144 284 1809250811780 285 1956549228692 286 2131870713310 287 2304717148334 288 2510211582517 289 2712954565926 290 2953595108282 291 3191309483383 292 3472865785799 293 3751458691646 294 4080610316425 295 4406965267726 296 4791452711045 297 5173572466540 298 5622349310835 299 6069545602072 300 6592976629344 301 7116061829600 302 7726125691924 303 8337662844202 304 9048212849881 305 9762771286160 306 10589805063955 307 11424288680761 308 12386289688281 309 13360278461829 310 14478574791076 311 15614754252469 312 16913966070964 313 18238580978088 314 19747095641427 315 21290512750576 316 23041071033215 317 24838379058757 318 26868703768317 319 28960449062227 320 31314010606386 321 33746990137157 322 36473837089242 323 39302057201048 324 42459816542570 325 45745537851194 326 49400507593589 327 53215494950408 328 57443950233886 329 61870844097384 330 66760473727920 331 71894417010139 332 77546023763632 333 83496460027610 334 90025846057572 335 96918631971929 336 104458813099617 337 112438569987089 338 121142241370123 339 130375098104979 340 140417513706006 341 151094172917952 342 162676367562003 343 175015661098412 344 188368188491593 345 202621070633444 346 218008203355292 347 234462351991956 348 252186931222105 349 271171937216176 350 291580836007941 351 313474153180242 352 336964557556628 353 362198230900373 354 389224737035235 355 418293089015998 356 449375827110179 357 482844165481667 358 518577999348101 359 557092533040249 360 598157555692026 361 642456649553819 362 689630087652565 363 740557034022871 364 794726788472867 365 853244330962800 366 915424353193069 367 982631122683719 368 1053978864474044 369 1131128083096610 370 1212964319556497 371 1301484932094618 372 1395316216768661 373 1496836946655173 374 1604381135898162 375 1720757607238042 376 1843972709603224 377 1977318348911466 378 2118435332501393 379 2271156151494949 380 2432715973175885 381 2607550183906468 382 2792445884232331 383 2992508462870033 384 3204032622045537 385 3432866043251246 386 3674764731317648 387 3936395964168633 388 4212929471591785 389 4511934881461494 390 4827946742939401 391 5169524924020227 392 5530519565050994 393 5920574213212855 394 6332805122441979 395 6778038023679069 396 7248606872144911 397 7756623608850416 398 8293592771830921 399 8873021245683770 400 9485540153138898 401 10146165288887487 402 10844613784454656 403 11597528455996097 404 12393677724103659 405 13251454115198921 406 14158649066052452 407 15135530685335989 408 16168894609895967 409 17281014068867454 410 18457680452587568 411 19723303375655408 412 21062675819219135 413 22502477336796895 414 24026523765780716 415 25663898045472382 416 27397480512514357 417 29258891269591816 418 31230138859440049 419 33345511795163333 420 35586238531760290 421 37989405225148465 422 40535582268214393 423 43264777007854735 424 46157061532782845 425 49255482942570113 426 52539815272482864 427 56056254685737764 428 59784526997110581 429 63774078047744004 430 68004888567364419 431 72529741167238631 432 77329238594744171 433 82459574599051123 434 87902409784169738 435 93717404906306977 436 99887795905554106 437 106476749126906556 438 113469680637356284 439 120933277255446669 440 128855842656365643 441 137307576700818224 442 146280488023940314 443 155848252918778214 444 166007529962925649 445 176835408195481266 446 188334277628101541 447 200584541587185581 448 213595560546111829 449 227450922091059467 450 242168364033151628 451 257834488809867130 452 274477010824406879 453 292185342660551790 454 310998979667381136 455 331009897005148181 456 352271408344485537 457 374877766998038458 458 398898390558122395 459 424429481816620440 460 451559128543490142 461 480385118667295066 462 511017074677195748 463 543553963477237588 464 578130142288678353 465 614845320523669698 466 653862146639037782 467 695280601882618731 468 739295580921202344 469 786006847739370096 470 835645921497797240 471 888311840331618130 472 944277597331983661 473 1003640998295595653 474 1066721859541682341 475 1133616253750397029 476 1204696723713084827 477 1280057142437826929 478 1360129270260082425 479 1445004358355265343 480 1535180524204122449 481 1630746057244435291 482 1732273259638701267 483 1839847220203148567 484 1954123009801414513 485 2075182428493539442 486 2203772702207238572 487 2339972435245440807 488 2484631274130308175 489 2637824966160491271 490 2800516776881062555 491 2972780226813715252 492 3155704418089590990 493 3349361649176987629 494 3554980158283661818 495 3772632466637719063 496 4003700426786846241 497 4248258773929727855 498 4507858705854010449 499 4782579799738705120 500 5074159690865259142 501 5382686198612270121 502 5710101936474315523 503 6056507260225916127 504 6424069873973015486 505 6812908028714111621 506 7225436305749228959 507 7661797436768855990 508 8124676480546020901 509 8614248675312776473 510 9133495094489431800 511 9682633159411851624 512 10264967590621960180 513 10880769587835368081 514 11533697393480391271 515 12224089770089095803 516 12955990782235332873 517 13729823060428475202 518 14550051393741161972 519 15417201452305196363 520 16336196465739178496 521 17307687591239242918 522 18337097244342168468 523 19425228227514377681 524 20578046163321925406 525 21796535874027096541 526 23087253748405420862 527 24451401762655877833 528 25896178462005821288 529 27423043488558343060 530 29039893085720508499 531 30748491129145555408 532 32557491601672343074 533 34469015989071487536 534 36492540952437086422 535 38630606608794695671 536 40893582550953211224 537 43284497112543134692 538 45814688877192940809 539 48487753569748660748 540 51316081139108253547 541 54303924578581498592 542 57464814500509986074 543 60803763002982744806 544 64335538205248203305 545 68066026450854915740 546 72011338515817611376 547 76178364961679938849 548 80584673441073453682 549 85238305164259230484 550 90158408898359595580 551 95354341241466426159 552 100846967280691875878 553 106647144004970890480 554 112777600176132375722 555 119250900681607983709 556 126091798640548369054 557 133314799197099959041 558 140946855319699746503 559 149004672316080999388 560 157517594773296976479 561 166504818435023263360 562 175998289402278713855 563 186020017733301328918 564 196604780903691921987 565 207777764140371456744 566 219576828426892137664 567 232030735879156787499 568 245180707693047215552 569 259059529485209659701 570 273712086823162969357 571 289175684982468280731 572 305499208390992050879 573 322725032497461266271 574 340906409000764040680 575 360091393953279074183 576 380338012256774440079 577 401700676650861171761 578 424242633163161291095 579 448025399594680962659 580 473117937509551099041 581 499589697271566362223 582 527515902436658053711 583 556974850471769422545 584 588048631035854924457 585 620825398425683516818 586 655394777061419283222 587 691855892403667116820 588 730306643831637834156 589 770858356616563400049 590 813618025366051632668 591 858710529333001681332 592 906252867390391862054 593 956384964026912700062 594 1009234830723877549528 595 1064959078884087272616 596 1123697851042101945288 597 1185626251378773438675 598 1250897795023380255679 599 1319708064852586262430 600 1392225326593283132450 601 1468667824187928132441 602 1549220104417789552389 603 1634125469976470735948 604 1723586448129295604450 605 1817874032862476377279 606 1917210619953869069237 607 2021897784524626076951 608 2132179887867671247609 609 2248392256659096820774 610 2370803547737118968533 611 2499786317037525178659 612 2635636105050821792922 613 2778766509731643738006 614 2929502830832947463422 615 3088303887903491768500 616 3255527933827415660801 617 3431683589279547440831 618 3617165608292590485208 619 3812537429988858149476 620 4018234249400080267224 621 4234879818739250556684 622 4462954149453527250502 623 4703147323889179898530 624 4955989026913958760348 625 5222242257695644180583 626 5502491766312456584781 627 5797580678771641750000 628 6108154793087137057088 629 6435145251940696501197 630 6779265539461375539244 631 7141543448711752197748 632 7522767511944231195972 633 7924071617684022827325 634 8346327510342948461303 635 8790785506819496079169 636 9258409612758733065338 637 9750577874996553143767 638 10268356589148671643805 639 10813263893424658019127 640 11386479482505900148249 641 11989675104085847571203 642 12624156155575389826133 643 13291762777970644268224 644 13993939691578140736197 645 14732711596104584111786 646 15509677609196155835395 647 16327064666637884979738 648 17186642959401185139706 649 18090860987634152232372 650 19041678459124641069595 651 20041786573403015596241 652 21093354943808765877942 653 22199340577667089435520 654 23362145527325732770486 655 24585017876234659236191 656 25870617008126276721353 657 27222509710594924316874 658 28643640189704451108406 659 30137924148235629440895 660 31708620961662316248821 661 33360028281790887450928 662 35095754144284494569915 663 36920514273903278815125 664 38838302310502411395385 665 40854291553599228615609 666 42972901988908123590667 667 45199807690658343621811 668 47539899901256669610088 669 49999400712970177571186 670 52583722117280421779093 671 55299685894970573034950 672 58153279305617479968946 673 61151980330614650503284 674 64302411536541606086482 675 67612768918767623546609 676 71090376442647267652812 677 74744215729674384270885 678 78582384877713640565304 679 82614725096276290443416 680 86850188628992559090168 681 91299557181847319176008 682 95972725140349842202371 683 100881503222279704752748 684 106036824695565191881654 685 111451626128240230259547 686 117137985994666746509664 687 123110072665662102945301 688 129381226638802066659992 689 135966964013627651111685 690 142882015620279107766223 691 150143372134116459682931 692 157767295604538607996562 693 165772390081288874301971 694 174176603488033292133618 695 183000305134236182539243 696 192263298533849365695047 697 201987884463569760896823 698 212195908222471372510420 699 222911783943381138013167 700 234159602923988148977781 701 245966091704152122886257 702 258357811498704467510466 703 271364019094795232383702 704 285013991080998519721757 705 299339752894652054050805 706 314373565498008022202261 707 330150483891643573605124 708 346706048135017658447605 709 364078628338588529131519 710 382307366489363683313928 711 401434260317202477855968 712 421502407266136252163357 713 442557774699081945451962 714 464647802576352039045493 715 487822802196979124995289 716 512134979707277667490164 717 537639399974083071239316 718 564393498971034409054367 719 592457543421864427164866 720 621894706399237312113133 721 652770947063623292957262 722 685155730478329011116336 723 719121245087023494781736 724 754743854799128052631065 725 792102564795486718577001 726 831281301384142010814778 727 872366529291473764154248 728 915450462629010806207238 729 960627729014127668176849 730 1007999623233078062401822 731 1057669705340809433612292 732 1109749217251402119235455 733 1164351493389682173018671 734 1221598669489171638563362 735 1281614775416810320987064 736 1344533874908004647707032 737 1410491700859290572750473 738 1479635374571478112407635 739 1552113434123481510031295 740 1628087291923689937578945 741 1707719496740987697627894 742 1791187098962270265767854 743 1878667976497434978397766 744 1970356288100464425804391 745 2066446682685345322749951 746 2167152032356546388598711 747 2272685333721546872485828 748 2383279923884829891129112 749 2499168871123440182650173 750 2620607888977140316297789 751 2747852002234929894920489 752 2881181386390326807340554 753 3020875083274592175299724 754 3167240005471550959238919 755 3320581464218696110506377 756 3481235590874266430572899 757 3649536427898965853105319 758 3825852032047372122489271 759 4010547867458830413881725 760 4204026867884425560423563 761 4406688859167769702552647 762 4618974870400451177438887 763 4841322301509738301531365 764 5074213785732393007637394 765 5318127806664451926110385 766 5573592426706953243910512 767 5841131046955677656694998 768 6121321328270408906565571 769 6414735776811367250750955 770 6722006195932508950186808 771 7043758770230629268856133 772 7380684397521627945625467 773 7733467934985734866754798 774 8102864770832464526666710 775 8489623887768469934672515 776 8894571043542383693655706 777 9318525299567671895044861 778 9762389188094479535516963 779 10227058347706788135224056 780 10713519062339035810517034 781 11222750640576932085079123 782 11755830717803139338050972 783 12313830013143413445994046 784 12897925790618717172177125 785 13509288626243490657941089 786 14149204426811138994710060 787 14818952840507233831085738 788 15519938232781091709948357 789 16253559376948761839621179 790 17021349785068109127720744 791 17824838320883218872147449 792 18665699279638305799991225 793 19545603574425829789700587 794 20466378951940199846707189 795 21429851415428678027590035 796 22438015953395927319576928 797 23492867877999381345823978 798 24596584430096669680086754 799 25751345731746060087370181 800 26959527613625653030167037 801 28223511904392068925115316 802 29545890804731501562652324 803 30929266265458506470641266 804 32376466206166774476647160 805 33890332768214360318071824 806 35473950644376562298906824 807 37130424033135659330701519 808 38863117308763308783585228 809 40675420549720483706445899 810 42571002735378853782333292 811 44553565774808820896190887 812 46627110366743929874218247 813 48795678515719309739359983 814 51063632134945842486974493 815 53435384105741483950911554 816 55915689638574596777676494 817 58509366009127906069889824 818 61221596619843774047214599 819 64057639632991979820986156 820 67023144593451638112096788 821 70123850275944023102193626 822 73365913638369853051879897 823 76755597308248871042407968 824 80299610534548401652647527 825 84004786857478824132605030 826 87878436614126736484546366 827 91928015467553808039415298 828 96161487897560816931819784 829 100586987409642969821256609 830 105213190305469775127074122 831 110048968551278792048830821 832 115103772973040024767196270 833 120387279937424068503220150 834 125909782952637831290523871 835 131681834504922438308849784 836 137714644867607765037644703 837 144019720642275827404403501 838 150609269384062028296184633 839 157495836621042615985558517 840 164692714693177199247701727 841 172213580266189085589166393 842 180072905553063091012991002 843 188285598601722466560080179 844 196867414821675462614853703 845 205834602608150822717127623 846 215204312830503118065377186 847 224994252661307233517479410 848 235223090397570799972577638 849 245910120691558510255234449 850 257075661768786339106192291 851 268740735610332965050460550 852 280927454303205672675369113 853 293658719101453383986838718 854 306958592292782474408906899 855 320852019470332850697814777 856 335365182924695146981765553 857 350525251889495925796378555 858 366360713068165050866442323 859 382901154077005065111139969 860 400177566291648907730476923 861 418222167200694176888346501 862 437068670305663217301422757 863 456752152619154180192446625 864 477309285874947444548579844 865 498778255956419116063448294 866 521198949168109955071667774 867 544612930965521377564072661 868 569063580506882530966929745 869 594596136673662410979782008 870 621257773559357209645625870 871 649097722423780365505877363 872 678167280185642635877845561 873 708520016641951654330682959 874 740211707410960280195732649 875 773300636473479304755940314 876 807847444363973073129100576 877 843915536852001794823707059 878 881570838499966455969390380 879 920882319102855765169960380 880 961921642023341805702339621 881 1004763820844906761507278340 882 1049486751156982069666658149 883 1096172010752865548009855545 884 1144904262771819893392702560 885 1195772213686957717128874385 886 1248867874916260870208412903 887 1304287693799120356295020436 888 1362131659967105320303965610 889 1422504625498641394336574124 890 1485515241491997762281057581 891 1551277484617712542014066089 892 1619909408464353771641406355 893 1691534894774760665478242849 894 1766282203239056740151322506 895 1844285966805297593307907068 896 1925685522678412580493436208 897 2010627172234795306876563664 898 2099262275050316361965912385 899 2191749795123045273143100861 900 2288254138803497003907420258 901 2388948010235730930706271305 902 2494009973099264516958339541 903 2603627639416951364785188675 904 2717994934046854187666492098 905 2837315642270451160712005860 906 2961800354995707236443944643 907 3091670401831374742348480763 908 3227154453987021693397997741 909 3368492870852411321588642624 910 3515933936608918865527103467 911 3669738649666457481111611231 912 3830176568042255854714448856 913 3997531072354544633105442929 914 4172094794082860685186546319 915 4354175384175939033659519384 916 4544090497392820737535746875 917 4742174099943979179206213017 918 4948770982229633878235087321 919 5164243640295274957307356443 920 5388966288444637620984958441 921 5623332350643988336071110379 922 5867747943699037744280711461 923 6122640016082501720770118467 924 6388449271640450878831774713 925 6665638994634040159833805033 926 6954687383290131383211526902 927 7256097101134947963402748037 928 7570386989142081178397501953 929 7898102384680944608648496658 930 8239806180553201244785196462 931 8596089954074981324057460004 932 8967564340948425972285071502 933 9354871018129677193689166369 934 9758672360268959432133017062 935 10179664321077136787227499363 936 10618565340005926174827109452 937 11076130167798793898493660891 938 11553137991188607096859968838 939 12050407249192237707126918133 940 12568782943899544801433122871 941 13109152494827847129522082236 942 13672432204382540175707591698 943 14259584198213891604369244548 944 14871602014672145459040868128 945 15509528679585252996316468120 946 16174441390032672941986905507 947 16867470772272339608632009265 948 17589784631446803206361630769 949 18342608441509577634918630623 950 19127208134081277322575850007 951 19944911869139987664135994828 952 20797091838196730256393219458 953 21685187364198144887885911496 954 22610685696520351009158168022 955 23575146487962799958450092802 956 24580181561804234395815876407 957 25627480812918044932538394000 958 26718790930328977725901315565 959 27855942768327157108354947895 960 29040829011649916494337143011 961 30275433060986072475602519780 962 31561805632124253011206191850 963 32902095198391549178435482505 964 34298523519903134696674040907 965 35753417683240204523360457982 966 37269184562351088017774784729 967 38848344493109715018624719885 968 40493504673505461179484487847 969 42207394507602921775916695501 970 43992837959468429940570991946 971 45852790597438103624082085805 972 47790310923817173061707250680 973 49808599146222505123593746720 974 51910967513515021342923824245 975 54100880836274164496896931893 976 56381925868743061818567324201 977 58757853595180514438479944922 978 61232547707877914966230142882 979 63810068670174936826380286482 980 66494621351910860760732165040 981 69290600873246278744700142966 982 72202559471312119435320528522 983 75235254121603031699743844481 984 78393612723153821815932118673 985 81682783486123831424553233952 986 85108100537643134960087555654 987 88675135055238394451924528505 988 92389660411624704996320527495 989 96257705023795108246001052199 990 100285517172576253383191619830 991 104479619526460445393896508496 992 108846773790774156188019897302 993 113394036853636228578947058659 994 118128725440204830230643833708 995 123058473815439518558467262256 996 128191198641178592495698987481 997 133535158156631840188963196373 998 139098917460102313623101891433 999 144891409073278633539371364048 1000 150921898895342821591736525958