0 0 1 1 2 15 3 90 4 336 5 951 6 2247 7 4676 8 8856 9 15597 10 25927 11 41118 12 62712 13 92547 14 132783 15 185928 16 254864 17 342873 18 453663 19 591394 20 760704 21 966735 22 1215159 23 1512204 24 1864680 25 2280005 26 2766231 27 3332070 28 3986920 29 4740891 30 5604831 31 6590352 32 7709856 33 8976561 34 10404527 35 12008682 36 13804848 37 15809767 38 18041127 39 20517588 40 23258808 41 26285469 42 29619303 43 33283118 44 37300824 45 41697459 46 46499215 47 51733464 48 57428784 49 63614985 50 70323135 51 77585586 52 85436000 53 93909375 54 103042071 55 112871836 56 123437832 57 134780661 58 146942391 59 159966582 60 173898312 61 188784203 62 204672447 63 221612832 64 239656768 65 258857313 66 279269199 67 300948858 68 323954448 69 348345879 70 374184839 71 401534820 72 430461144 73 461030989 74 493313415 75 527379390 76 563301816 77 601155555 78 641017455 79 682966376 80 727083216 81 773450937 82 822154591 83 873281346 84 926920512 85 983163567 86 1042104183 87 1103838252 88 1168463912 89 1236081573 90 1306793943 91 1380706054 92 1457925288 93 1538561403 94 1622726559 95 1710535344 96 1802104800 97 1897554449 98 1997006319 99 2100584970 100 2208417520 101 2320633671 102 2437365735 103 2558748660 104 2684920056 105 2816020221 106 2952192167 107 3093581646 108 3240337176 109 3392610067 110 3550554447 111 3714327288 112 3884088432 113 4060000617 114 4242229503 115 4430943698 116 4626314784 117 4828517343 118 5037728983 119 5254130364 120 5477905224 121 5709240405 122 5948325879 123 6195354774 124 6450523400 125 6714031275 126 6986081151 127 7266879040 128 7556634240 129 7855559361 130 8163870351 131 8481786522 132 8809530576 133 9147328631 134 9495410247 135 9854008452 136 10223359768 137 10603704237 138 10995285447 139 11398350558 140 11813150328 141 12239939139 142 12678975023 143 13130519688 144 13594838544 145 14072200729 146 14562879135 147 15067150434 148 15585295104 149 16117597455 150 16664345655 151 17225831756 152 17802351720 153 18394205445 154 19001696791 155 19625133606 156 20264827752 157 20921095131 158 21594255711 159 22284633552 160 22992556832 161 23718357873 162 24462373167 163 25224943402 164 26006413488 165 26807132583 166 27627454119 167 28467735828 168 29328339768 169 30209632349 170 31111984359 171 32035770990 172 32981371864 173 33949171059 174 34939557135 175 35952923160 176 36989666736 177 38050190025 178 39134899775 179 40244207346 180 41378528736 181 42538284607 182 43723900311 183 44935805916 184 46174436232 185 47440230837 186 48733634103 187 50055095222 188 51405068232 189 52784012043 190 54192390463 191 55630672224 192 57099331008 193 58598845473 194 60129699279 195 61692381114 196 63287384720 197 64915208919 198 66576357639 199 68271339940 200 70000670040 201 71764867341 202 73564456455 203 75399967230 204 77271934776 205 79180899491 206 81127407087 207 83112008616 208 85135260496 209 87197724537 210 89299967967 211 91442563458 212 93626089152 213 95851128687 214 98118271223 215 100428111468 216 102781249704 217 105178291813 218 107619849303 219 110106539334 220 112638984744 221 115217814075 222 117843661599 223 120517167344 224 123238977120 225 126009742545 226 128830121071 227 131700776010 228 134622376560 229 137595597831 230 140621120871 231 143699632692 232 146831826296 233 150018400701 234 153260060967 235 156557518222 236 159911489688 237 163322698707 238 166791874767 239 170319753528 240 173907076848 241 177554592809 242 181263055743 243 185033226258 244 188865871264 245 192761763999 246 196721684055 247 200746417404 248 204836756424 249 208993499925 250 213217453175 251 217509427926 252 221870242440 253 226300721515 254 230801696511 255 235374005376 256 240018492672 257 244736009601 258 249527414031 259 254393570522 260 259335350352 261 264353631543 262 269449298887 263 274623243972 264 279876365208 265 285209567853 266 290623764039 267 296119872798 268 301698820088 269 307361538819 270 313108968879 271 318942057160 272 324861757584 273 330869031129 274 336964845855 275 343150176930 276 349426006656 277 355793324495 278 362253127095 279 368806418316 280 375454209256 281 382197518277 282 389037371031 283 395974800486 284 403010846952 285 410146558107 286 417382989023 287 424721202192 288 432162267552 289 439707262513 290 447357271983 291 455113388394 292 462976711728 293 470948349543 294 479029416999 295 487221036884 296 495524339640 297 503940463389 298 512470553959 299 521115764910 300 529877257560 301 538756201011 302 547753772175 303 556871155800 304 566109544496 305 575470138761 306 584954147007 307 594562785586 308 604297278816 309 614158859007 310 624148766487 311 634268249628 312 644518564872 313 654900976757 314 665416757943 315 676067189238 316 686853559624 317 697777166283 318 708839314623 319 720041318304 320 731384499264 321 742870187745 322 754499722319 323 766274449914 324 778195725840 325 790264913815 326 802483385991 327 814852522980 328 827373713880 329 840048356301 330 852877856391 331 865863628862 332 879007097016 333 892309692771 334 905772856687 335 919398037992 336 933186694608 337 947140293177 338 961260309087 339 975548226498 340 990005538368 341 1004633746479 342 1019434361463 343 1034408902828 344 1049558898984 345 1064885887269 346 1080391413975 347 1096077034374 348 1111944312744 349 1127994822395 350 1144230145695 351 1160651874096 352 1177261608160 353 1194060957585 354 1211051541231 355 1228234987146 356 1245612932592 357 1263187024071 358 1280958917351 359 1298930277492 360 1317102778872 361 1335478105213 362 1354057949607 363 1372844014542 364 1391838011928 365 1411041663123 366 1430456698959 367 1450084859768 368 1469927895408 369 1489987565289 370 1510265638399 371 1530763893330 372 1551484118304 373 1572428111199 374 1593597679575 375 1614994640700 376 1636620821576 377 1658478058965 378 1680568199415 379 1702893099286 380 1725454624776 381 1748254651947 382 1771295066751 383 1794577765056 384 1818104652672 385 1841877645377 386 1865898668943 387 1890169659162 388 1914692561872 389 1939469332983 390 1964501938503 391 1989792354564 392 2015342567448 393 2041154573613 394 2067230379719 395 2093572002654 396 2120181469560 397 2147060817859 398 2174212095279 399 2201637359880 400 2229338680080 401 2257318134681 402 2285577812895 403 2314119814370 404 2342946249216 405 2372059238031 406 2401460911927 407 2431153412556 408 2461138892136 409 2491419513477 410 2521997450007 411 2552874885798 412 2584054015592 413 2615537044827 414 2647326189663 415 2679423677008 416 2711831744544 417 2744552640753 418 2777588624943 419 2810941967274 420 2844614948784 421 2878609861415 422 2912929008039 423 2947574702484 424 2982549269560 425 3017855045085 426 3053494375911 427 3089469619950 428 3125783146200 429 3162437334771 430 3199434576911 431 3236777275032 432 3274467842736 433 3312508704841 434 3350902297407 435 3389651067762 436 3428757474528 437 3468223987647 438 3508053088407 439 3548247269468 440 3588809034888 441 3629740900149 442 3671045392183 443 3712725049398 444 3754782421704 445 3797220070539 446 3840040568895 447 3883246501344 448 3926840464064 449 3970825064865 450 4015202923215 451 4059976670266 452 4105148948880 453 4150722413655 454 4196699730951 455 4243083578916 456 4289876647512 457 4337081638541 458 4384701265671 459 4432738254462 460 4481195342392 461 4530075278883 462 4579380825327 463 4629114755112 464 4679279853648 465 4729878918393 466 4780914758879 467 4832390196738 468 4884308065728 469 4936671211759 470 4989482492919 471 5042744779500 472 5096460954024 473 5150633911269 474 5205266558295 475 5260361814470 476 5315922611496 477 5371951893435 478 5428452616735 479 5485427750256 480 5542880275296 481 5600813185617 482 5659229487471 483 5718132199626 484 5777524353392 485 5837408992647 486 5897789173863 487 5958667966132 488 6020048451192 489 6081933723453 490 6144326890023 491 6207231070734 492 6270649398168 493 6334585017683 494 6399041087439 495 6464020778424 496 6529527274480 497 6595563772329 498 6662133481599 499 6729239624850 500 6796885437600 501 6865074168351 502 6933809078615 503 7003093442940 504 7072930548936 505 7143323697301 506 7214276201847 507 7285791389526 508 7357872600456 509 7430523187947 510 7503746518527 511 7577545971968 512 7651924941312 513 7726886832897 514 7802435066383 515 7878573074778 516 7955304304464 517 8032632215223 518 8110560280263 519 8189091986244 520 8268230833304 521 8347980335085 522 8428344018759 523 8509325425054 524 8590928108280 525 8673155636355 526 8756011590831 527 8839499566920 528 8923623173520 529 9008386033241 530 9093791782431 531 9179844071202 532 9266546563456 533 9353902936911 534 9441916883127 535 9530592107532 536 9619932329448 537 9709941282117 538 9800622712727 539 9891980382438 540 9984018066408 541 10076739553819 542 10170148647903 543 10264249165968 544 10359044939424 545 10454539813809 546 10550737648815 547 10647642318314 548 10745257710384 549 10843587727335 550 10942636285735 551 11042407316436 552 11142904764600 553 11244132589725 554 11346094765671 555 11448795280686 556 11552238137432 557 11656427353011 558 11761366958991 559 11867061001432 560 11973513540912 561 12080728652553 562 12188710426047 563 12297462965682 564 12406990390368 565 12517296833663 566 12628386443799 567 12740263383708 568 12852931831048 569 12966395978229 570 13080660032439 571 13195728215670 572 13311604764744 573 13428293931339 574 13545799982015 575 13664127198240 576 13783279876416 577 13903262327905 578 14024078879055 579 14145733871226 580 14268231660816 581 14391576619287 582 14515773133191 583 14640825604196 584 14766738449112 585 14893516099917 586 15021163003783 587 15149683623102 588 15279082435512 589 15409363933923 590 15540532626543 591 15672593036904 592 15805549703888 593 15939407181753 594 16074170040159 595 16209842864194 596 16346430254400 597 16483936826799 598 16622367212919 599 16761726059820 600 16902018030120 601 17043247802021 602 17185420069335 603 17328539541510 604 17472610943656 605 17617639016571 606 17763628516767 607 17910584216496 608 18058510903776 609 18207413382417 610 18357296472047 611 18508165008138 612 18660023842032 613 18812877840967 614 18966731888103 615 19121590882548 616 19277459739384 617 19434343389693 618 19592246780583 619 19751174875214 620 19911132652824 621 20072125108755 622 20234157254479 623 20397234117624 624 20561360742000 625 20726542187625 626 20892783530751 627 21060089863890 628 21228466295840 629 21397917951711 630 21568449972951 631 21740067517372 632 21912775759176 633 22086579888981 634 22261485113847 635 22437496657302 636 22614619759368 637 22792859676587 638 22972221682047 639 23152711065408 640 23334333132928 641 23517093207489 642 23700996628623 643 23886048752538 644 24072254952144 645 24259620617079 646 24448151153735 647 24637851985284 648 24828728551704 649 25020786309805 650 25214030733255 651 25408467312606 652 25604101555320 653 25800938985795 654 25998985145391 655 26198245592456 656 26398725902352 657 26600431667481 658 26803368497311 659 27007542018402 660 27212957874432 661 27419621726223 662 27627539251767 663 27836716146252 664 28047158122088 665 28258870908933 666 28471860253719 667 28686131920678 668 28901691691368 669 29118545364699 670 29336698756959 671 29556157701840 672 29776928050464 673 29999015671409 674 30222426450735 675 30447166292010 676 30673241116336 677 30900656862375 678 31129419486375 679 31359534962196 680 31591009281336 681 31823848452957 682 32058058503911 683 32293645478766 684 32530615439832 685 32768974467187 686 33008728658703 687 33249884130072 688 33492447014832 689 33736423464393 690 33981819648063 691 34228641753074 692 34476895984608 693 34726588565823 694 34977725737879 695 35230313759964 696 35484358909320 697 35739867481269 698 35996845789239 699 36255300164790 700 36515236957640 701 36776662535691 702 37039583285055 703 37304005610080 704 37569935933376 705 37837380695841 706 38106346356687 707 38376839393466 708 38648866302096 709 38922433596887 710 39197547810567 711 39474215494308 712 39752443217752 713 40032237569037 714 40313605154823 715 40596552600318 716 40881086549304 717 41167213664163 718 41454940625903 719 41744274134184 720 42035220907344 721 42327787682425 722 42621981215199 723 42917808280194 724 43215275670720 725 43514390198895 726 43815158695671 727 44117588010860 728 44421685013160 729 44727456590181 730 45034909648471 731 45344051113542 732 45654887929896 733 45967427061051 734 46281675489567 735 46597640217072 736 46915328264288 737 47234746671057 738 47555902496367 739 47878802818378 740 48203454734448 741 48529865361159 742 48858041834343 743 49187991309108 744 49519720959864 745 49853237980349 746 50188549583655 747 50525663002254 748 50864585488024 749 51205324312275 750 51547886765775 751 51892280158776 752 52238511821040 753 52586589101865 754 52936519370111 755 53288310014226 756 53641968442272 757 53997502081951 758 54354918380631 759 54714224805372 760 55075428842952 761 55438537999893 762 55803559802487 763 56170501796822 764 56539371548808 765 56910176644203 766 57282924688639 767 57657623307648 768 58034280146688 769 58412902871169 770 58793499166479 771 59176076738010 772 59560643311184 773 59947206631479 774 60335774464455 775 60726354595780 776 61118954831256 777 61513582996845 778 61910246938695 779 62308954523166 780 62709713636856 781 63112532186627 782 63517418099631 783 63924379323336 784 64333423825552 785 64744559594457 786 65157794638623 787 65573136987042 788 65990594689152 789 66410175814863 790 66831888454583 791 67255740719244 792 67681740740328 793 68109896669893 794 68540216680599 795 68972708965734 796 69407381739240 797 69844243235739 798 70283301710559 799 70724565439760 800 71168042720160 801 71613741869361 802 72061671225775 803 72511839148650 804 72964254018096 805 73418924235111 806 73875858221607 807 74335064420436 808 74796551295416 809 75260327331357 810 75726401034087 811 76194780930478 812 76665475568472 813 77138493517107 814 77613843366543 815 78091533728088 816 78571573234224 817 79053970538633 818 79538734316223 819 80025873263154 820 80515396096864 821 81007311556095 822 81501628400919 823 81998355412764 824 82497501394440 825 82999075170165 826 83503085585591 827 84009541507830 828 84518451825480 829 85029825448651 830 85543671308991 831 86059998359712 832 86578815575616 833 87100131953121 834 87623956510287 835 88150298286842 836 88679166344208 837 89210569765527 838 89744517655687 839 90281019141348 840 90820083370968 841 91361719514829 842 91905936765063 843 92452744335678 844 93002151462584 845 93554167403619 846 94108801438575 847 94666062869224 848 95225961019344 849 95788505234745 850 96353704883295 851 96921569354946 852 97492108061760 853 98065330437935 854 98641245939831 855 99219864045996 856 99801194257192 857 100385246096421 858 100972029108951 859 101561552862342 860 102153826946472 861 102748860973563 862 103346664578207 863 103947247417392 864 104550619170528 865 105156789539473 866 105765768248559 867 106377565044618 868 106992189697008 869 107609651997639 870 108229961760999 871 108853128824180 872 109479163046904 873 110108074311549 874 110739872523175 875 111374567609550 876 112012169521176 877 112652688231315 878 113296133736015 879 113942516054136 880 114591845227376 881 115244131320297 882 115899384420351 883 116557614637906 884 117218832106272 885 117883046981727 886 118550269443543 887 119220509694012 888 119893777958472 889 120570084485333 890 121249439546103 891 121931853435414 892 122617336471048 893 123305898993963 894 123997551368319 895 124692303981504 896 125390167244160 897 126091151590209 898 126795267476879 899 127502525384730 900 128212935817680 901 128926509303031 902 129643256391495 903 130363187657220 904 131086313697816 905 131812645134381 906 132542192611527 907 133274966797406 908 134010978383736 909 134750238085827 910 135492756642607 911 136238544816648 912 136987613394192 913 137739973185177 914 138495635023263 915 139254609765858 916 140016908294144 917 140782541513103 918 141551520351543 919 142323855762124 920 143099558721384 921 143878640229765 922 144661111311639 923 145446983015334 924 146236266413160 925 147028972601435 926 147825112700511 927 148624697854800 928 149427739232800 929 150234248027121 930 151044235454511 931 151857712755882 932 152674691196336 933 153495182065191 934 154319196676007 935 155146746366612 936 155977842499128 937 156812496459997 938 157650719660007 939 158492523534318 940 159337919542488 941 160186919168499 942 161039533920783 943 161895775332248 944 162755654960304 945 163619184386889 946 164486375218495 947 165357239086194 948 166231787645664 949 167110032577215 950 167991985585815 951 168877658401116 952 169767062777480 953 170660210494005 954 171557113354551 955 172457783187766 956 173362231847112 957 174270471210891 958 175182513182271 959 176098369689312 960 177018052684992 961 177941574147233 962 178868946078927 963 179800180507962 964 180735289487248 965 181674285094743 966 182617179433479 967 183563984631588 968 184514712842328 969 185469376244109 970 186427987040519 971 187390557460350 972 188357099757624 973 189327626211619 974 190302149126895 975 191280680833320 976 192263233686096 977 193249820065785 978 194240452378335 979 195235143055106 980 196233904552896 981 197236749353967 982 198243689966071 983 199254738922476 984 200269908781992 985 201289212128997 986 202312661573463 987 203340269750982 988 204372049322792 989 205408012975803 990 206448173422623 991 207492543401584 992 208541135676768 993 209593963038033 994 210651038301039 995 211712374307274 996 212777983924080 997 213847880044679 998 214922075588199 999 216000583499700 1000 217083416750200