0 1 1 7 2 52 3 192 4 507 5 1101 6 2102 7 3662 8 5957 9 9187 10 13576 11 19372 12 26847 13 36297 14 48042 15 62426 16 79817 17 100607 18 125212 19 154072 20 187651 21 226437 22 270942 23 321702 24 379277 25 444251 26 517232 27 598852 28 689767 29 790657 30 902226 31 1025202 32 1160337 33 1308407 34 1470212 35 1646576 36 1838347 37 2046397 38 2271622 39 2514942 40 2777301 41 3059667 42 3363032 43 3688412 44 4036847 45 4409401 46 4807162 47 5231242 48 5682777 49 6162927 50 6672876 51 7213832 52 7787027 53 8393717 54 9035182 55 9712726 56 10427677 57 11181387 58 11975232 59 12810612 60 13688951 61 14611697 62 15580322 63 16596322 64 17661217 65 18776551 66 19943892 67 21164832 68 22440987 69 23773997 70 25165526 71 26617262 72 28130917 73 29708227 74 31350952 75 33060876 76 34839807 77 36689577 78 38612042 79 40609082 80 42682601 81 44834527 82 47066812 83 49381432 84 51780387 85 54265701 86 56839422 87 59503622 88 62260397 89 65111867 90 68060176 91 71107492 92 74256007 93 77507937 94 80865522 95 84331026 96 87906737 97 91594967 98 95398052 99 99318352 100 103358251 101 107520157 102 111806502 103 116219742 104 120762357 105 125436851 106 130245752 107 135191612 108 140277007 109 145504537 110 150876826 111 156396522 112 162066297 113 167888847 114 173866892 115 180003176 116 186300467 117 192761557 118 199389262 119 206186422 120 213155901 121 220300587 122 227623392 123 235127252 124 242815127 125 250690001 126 258754882 127 267012802 128 275466817 129 284120007 130 292975476 131 302036352 132 311305787 133 320786957 134 330483062 135 340397326 136 350532997 137 360893347 138 371481672 139 382301292 140 393355551 141 404647817 142 416181482 143 427959962 144 439986697 145 452265151 146 464798812 147 477591192 148 490645827 149 503966277 150 517556126 151 531418982 152 545558477 153 559978267 154 574682032 155 589673476 156 604956327 157 620534337 158 636411282 159 652590962 160 669077201 161 685873847 162 702984772 163 720413872 164 738165067 165 756242301 166 774649542 167 793390782 168 812470037 169 831891347 170 851658776 171 871776412 172 892248367 173 913078777 174 934271802 175 955831626 176 977762457 177 1000068527 178 1022754092 179 1045823432 180 1069280851 181 1093130677 182 1117377262 183 1142024982 184 1167078237 185 1192541451 186 1218419072 187 1244715572 188 1271435447 189 1298583217 190 1326163426 191 1354180642 192 1382639457 193 1411544487 194 1440900372 195 1470711776 196 1500983387 197 1531719917 198 1562926102 199 1594606702 200 1626766501 201 1659410307 202 1692542952 203 1726169292 204 1760294207 205 1794922601 206 1830059402 207 1865709562 208 1901878057 209 1938569887 210 1975790076 211 2013543672 212 2051835747 213 2090671397 214 2130055742 215 2169993926 216 2210491117 217 2251552507 218 2293183312 219 2335388772 220 2378174151 221 2421544737 222 2465505842 223 2510062802 224 2555220977 225 2600985751 226 2647362532 227 2694356752 228 2741973867 229 2790219357 230 2839098726 231 2888617502 232 2938781237 233 2989595507 234 3041065912 235 3093198076 236 3145997647 237 3199470297 238 3253621722 239 3308457642 240 3363983801 241 3420205967 242 3477129932 243 3534761512 244 3593106547 245 3652170901 246 3711960462 247 3772481142 248 3833738877 249 3895739627 250 3958489376 251 4021994132 252 4086259927 253 4151292817 254 4217098882 255 4283684226 256 4351054977 257 4419217287 258 4488177332 259 4557941312 260 4628515451 261 4699905997 262 4772119222 263 4845161422 264 4919038917 265 4993758051 266 5069325192 267 5145746732 268 5223029087 269 5301178697 270 5380202026 271 5460105562 272 5540895817 273 5622579327 274 5705162652 275 5788652376 276 5873055107 277 5958377477 278 6044626142 279 6131807782 280 6219929101 281 6308996827 282 6399017712 283 6489998532 284 6581946087 285 6674867201 286 6768768722 287 6863657522 288 6959540497 289 7056424567 290 7154316676 291 7253223792 292 7353152907 293 7454111037 294 7556105222 295 7659142526 296 7763230037 297 7868374867 298 7974584152 299 8081865052 300 8190224751 301 8299670457 302 8410209402 303 8521848842 304 8634596057 305 8748458351 306 8863443052 307 8979557512 308 9096809107 309 9215205237 310 9334753326 311 9455460822 312 9577335197 313 9700383947 314 9824614592 315 9950034676 316 10076651767 317 10204473457 318 10333507362 319 10463761122 320 10595242401 321 10727958887 322 10861918292 323 10997128352 324 11133596827 325 11271331501 326 11410340182 327 11550630702 328 11692210917 329 11835088707 330 11979271976 331 12124768652 332 12271586687 333 12419734057 334 12569218762 335 12720048826 336 12872232297 337 13025777247 338 13180691772 339 13336983992 340 13494662051 341 13653734117 342 13814208382 343 13976093062 344 14139396397 345 14304126651 346 14470292112 347 14637901092 348 14806961927 349 14977482977 350 15149472626 351 15322939282 352 15497891377 353 15674337367 354 15852285732 355 16031744976 356 16212723627 357 16395230237 358 16579273382 359 16764861662 360 16952003701 361 17140708147 362 17330983672 363 17522838972 364 17716282767 365 17911323801 366 18107970842 367 18306232682 368 18506118137 369 18707636047 370 18910795276 371 19115604712 372 19322073267 373 19530209877 374 19740023502 375 19951523126 376 20164717757 377 20379616427 378 20596228192 379 20814562132 380 21034627351 381 21256432977 382 21479988162 383 21705302082 384 21932383937 385 22161242951 386 22391888372 387 22624329472 388 22858575547 389 23094635917 390 23332519926 391 23572236942 392 23813796357 393 24057207587 394 24302480072 395 24549623276 396 24798646687 397 25049559817 398 25302372202 399 25557093402 400 25813733001 401 26072300607 402 26332805852 403 26595258392 404 26859667907 405 27126044101 406 27394396702 407 27664735462 408 27937070157 409 28211410587 410 28487766576 411 28766147972 412 29046564647 413 29329026497 414 29613543442 415 29900125426 416 30188782417 417 30479524407 418 30772361412 419 31067303472 420 31364360651 421 31663543037 422 31964860742 423 32268323902 424 32573942677 425 32881727251 426 33191687832 427 33503834652 428 33818177967 429 34134728057 430 34453495226 431 34774489802 432 35097722137 433 35423202607 434 35750941612 435 36080949576 436 36413236947 437 36747814197 438 37084691822 439 37423880342 440 37765390301 441 38109232267 442 38455416832 443 38803954612 444 39154856247 445 39508132401 446 39863793762 447 40221851042 448 40582314977 449 40945196327 450 41310505876 451 41678254432 452 42048452827 453 42421111917 454 42796242582 455 43173855726 456 43553962277 457 43936573187 458 44321699432 459 44709352012 460 45099541951 461 45492280297 462 45887578122 463 46285446522 464 46685896617 465 47088939551 466 47494586492 467 47902848632 468 48313737187 469 48727263397 470 49143438526 471 49562273862 472 49983780717 473 50407970427 474 50834854352 475 51264443876 476 51696750407 477 52131785377 478 52569560242 479 53010086482 480 53453375601 481 53899439127 482 54348288612 483 54799935632 484 55254391787 485 55711668701 486 56171778022 487 56634731422 488 57100540597 489 57569217267 490 58040773176 491 58515220092 492 58992569807 493 59472834137 494 59956024922 495 60442154026 496 60931233337 497 61423274767 498 61918290252 499 62416291752 500 62917291251 501 63421300757 502 63928332302 503 64438397942 504 64951509757 505 65467679851 506 65986920352 507 66509243412 508 67034661207 509 67563185937 510 68094829826 511 68629605122 512 69167524097 513 69708599047 514 70252842292 515 70800266176 516 71350883067 517 71904705357 518 72461745462 519 73022015822 520 73585528901 521 74152297187 522 74722333192 523 75295649452 524 75872258527 525 76452173001 526 77035405482 527 77621968602 528 78211875017 529 78805137407 530 79401768476 531 80001780952 532 80605187587 533 81212001157 534 81822234462 535 82435900326 536 83053011597 537 83673581147 538 84297621872 539 84925146692 540 85556168551 541 86190700417 542 86828755282 543 87470346162 544 88115486097 545 88764188151 546 89416465412 547 90072330992 548 90731798027 549 91394879677 550 92061589126 551 92731939582 552 93405944277 553 94083616467 554 94764969432 555 95450016476 556 96138770927 557 96831246137 558 97527455482 559 98227412362 560 98931130201 561 99638622447 562 100349902572 563 101064984072 564 101783880467 565 102506605301 566 103233172142 567 103963594582 568 104697886237 569 105436060747 570 106178131776 571 106924113012 572 107674018167 573 108427860977 574 109185655202 575 109947414626 576 110713153057 577 111482884327 578 112256622292 579 113034380832 580 113816173851 581 114602015277 582 115391919062 583 116185899182 584 116983969637 585 117786144451 586 118592437672 587 119402863372 588 120217435647 589 121036168617 590 121859076426 591 122686173242 592 123517473257 593 124352990687 594 125192739772 595 126036734776 596 126884989987 597 127737519717 598 128594338302 599 129455460102 600 130320899501 601 131190670907 602 132064788752 603 132943267492 604 133826121607 605 134713365601 606 135605014002 607 136501081362 608 137401582257 609 138306531287 610 139215943076 611 140129832272 612 141048213547 613 141971101597 614 142898511142 615 143830456926 616 144766953717 617 145708016307 618 146653659512 619 147603898172 620 148558747151 621 149518221337 622 150482335642 623 151451105002 624 152424544377 625 153402668751 626 154385493132 627 155373032552 628 156365302067 629 157362316757 630 158364091726 631 159370642102 632 160381983037 633 161398129707 634 162419097312 635 163444901076 636 164475556247 637 165511078097 638 166551481922 639 167596783042 640 168646996801 641 169702138567 642 170762223732 643 171827267712 644 172897285947 645 173972293901 646 175052307062 647 176137340942 648 177227411077 649 178322533027 650 179422722376 651 180527994732 652 181638365727 653 182753851017 654 183874466282 655 185000227226 656 186131149577 657 187267249087 658 188408541532 659 189555042712 660 190706768451 661 191863734597 662 193025957022 663 194193451622 664 195366234317 665 196544321051 666 197727727792 667 198916470532 668 200110565287 669 201310028097 670 202514875026 671 203725122162 672 204940785617 673 206161881527 674 207388426052 675 208620435376 676 209857925707 677 211100913277 678 212349414342 679 213603445182 680 214863022101 681 216128161427 682 217398879512 683 218675192732 684 219957117487 685 221244670201 686 222537867322 687 223836725322 688 225141260697 689 226451489967 690 227767429676 691 229089096392 692 230416506707 693 231749677237 694 233088624622 695 234433365526 696 235783916637 697 237140294667 698 238502516352 699 239870598452 700 241244557751 701 242624411057 702 244010175202 703 245401867042 704 246799503457 705 248203101351 706 249612677652 707 251028249312 708 252449833307 709 253877446637 710 255311106326 711 256750829422 712 258196632997 713 259648534147 714 261106549992 715 262570697676 716 264040994367 717 265517457257 718 267000103562 719 268488950522 720 269984015401 721 271485315487 722 272992868092 723 274506690552 724 276026800227 725 277553214501 726 279085950782 727 280625026502 728 282170459117 729 283722266107 730 285280464976 731 286845073252 732 288416108487 733 289993588257 734 291577530162 735 293167951826 736 294764870897 737 296368305047 738 297978271972 739 299594789392 740 301217875051 741 302847546717 742 304483822182 743 306126719262 744 307776255797 745 309432449651 746 311095318712 747 312764880892 748 314441154127 749 316124156377 750 317813905626 751 319510419882 752 321213717177 753 322923815567 754 324640733132 755 326364487976 756 328095098227 757 329832582037 758 331576957582 759 333328243062 760 335086456701 761 336851616747 762 338623741472 763 340402849172 764 342188958167 765 343982086801 766 345782253442 767 347589476482 768 349403774337 769 351225165447 770 353053668276 771 354889301312 772 356732083067 773 358582032077 774 360439166902 775 362303506126 776 364175068357 777 366053872227 778 367939936392 779 369833279532 780 371733920351 781 373641877577 782 375557169962 783 377479816282 784 379409835337 785 381347245951 786 383292066972 787 385244317272 788 387204015747 789 389171181317 790 391145832926 791 393127989542 792 395117670157 793 397114893787 794 399119679472 795 401132046276 796 403152013287 797 405179599617 798 407214824402 799 409257706802 800 411308266001 801 413366521207 802 415432491652 803 417506196592 804 419587655307 805 421676887101 806 423773911302 807 425878747262 808 427991414357 809 430111931987 810 432240319576 811 434376596572 812 436520782447 813 438672896697 814 440832958842 815 443000988426 816 445177005017 817 447361028207 818 449553077612 819 451753172872 820 453961333651 821 456177579637 822 458401930542 823 460634406102 824 462875026077 825 465123810251 826 467380778432 827 469645950452 828 471919346167 829 474200985457 830 476490888226 831 478789074402 832 481095563937 833 483410376807 834 485733533012 835 488065052576 836 490404955547 837 492753261997 838 495109992022 839 497475165742 840 499848803301 841 502230924867 842 504621550632 843 507020700812 844 509428395647 845 511844655401 846 514269500362 847 516702950842 848 519145027177 849 521595749727 850 524055138876 851 526523215032 852 528999998627 853 531485510117 854 533979769982 855 536482798726 856 538994616877 857 541515244987 858 544044703632 859 546583013412 860 549130194951 861 551686268897 862 554251255922 863 556825176722 864 559408052017 865 561999902551 866 564600749092 867 567210612432 868 569829513387 869 572457472797 870 575094511526 871 577740650462 872 580395910517 873 583060312627 874 585733877752 875 588416626876 876 591108581007 877 593809761177 878 596520188442 879 599239883882 880 601968868601 881 604707163727 882 607454790412 883 610211769832 884 612978123187 885 615753871701 886 618539036622 887 621333639222 888 624137700797 889 626951242667 890 629774286176 891 632606852692 892 635448963607 893 638300640337 894 641161904322 895 644032777026 896 646913279937 897 649803434567 898 652703262452 899 655612785152 900 658532024251 901 661461001357 902 664399738102 903 667348256142 904 670306577157 905 673274722851 906 676252714952 907 679240575212 908 682238325407 909 685245987337 910 688263582826 911 691291133722 912 694328661897 913 697376189247 914 700433737692 915 703501329176 916 706578985667 917 709666729157 918 712764581662 919 715872565222 920 718990701901 921 722119013787 922 725257522992 923 728406251652 924 731565221927 925 734734456001 926 737913976082 927 741103804402 928 744303963217 929 747514474807 930 750735361476 931 753966645552 932 757208349387 933 760460495357 934 763723105862 935 766996203326 936 770279810197 937 773573948947 938 776878642072 939 780193912092 940 783519781551 941 786856273017 942 790203409082 943 793561212362 944 796929705497 945 800308911151 946 803698852012 947 807099550792 948 810511030227 949 813933313077 950 817366422126 951 820810380182 952 824265210077 953 827730934667 954 831207576832 955 834695159476 956 838193705527 957 841703237937 958 845223779682 959 848755353762 960 852297983201 961 855851691047 962 859416500372 963 862992434272 964 866579515867 965 870177768301 966 873787214742 967 877407878382 968 881039782437 969 884682950147 970 888337404776 971 892003169612 972 895680267967 973 899368723177 974 903068558602 975 906779797626 976 910502463657 977 914236580127 978 917982170492 979 921739258232 980 925507866851 981 929288019877 982 933079740862 983 936883053382 984 940697981037 985 944524547451 986 948362776272 987 952212691172 988 956074315847 989 959947674017 990 963832789426 991 967729685842 992 971638387057 993 975558916887 994 979491299172 995 983435557776 996 987391716587 997 991359799517 998 995339830502 999 999331833502 1000 1003335832501