0 0 1 0 2 0 3 0 4 0 5 0 6 1 7 0 8 0 9 1 10 1 11 2 12 2 13 2 14 2 15 3 16 4 17 5 18 6 19 7 20 8 21 10 22 12 23 15 24 17 25 20 26 23 27 27 28 33 29 38 30 44 31 51 32 59 33 68 34 79 35 91 36 104 37 119 38 136 39 155 40 178 41 202 42 230 43 261 44 296 45 335 46 379 47 428 48 483 49 544 50 612 51 688 52 773 53 867 54 972 55 1088 56 1217 57 1360 58 1518 59 1693 60 1887 61 2101 62 2337 63 2599 64 2886 65 3203 66 3553 67 3937 68 4360 69 4826 70 5336 71 5897 72 6513 73 7188 74 7928 75 8740 76 9627 77 10599 78 11663 79 12825 80 14095 81 15484 82 16997 83 18650 84 20454 85 22419 86 24561 87 26895 88 29434 89 32198 90 35207 91 38477 92 42031 93 45895 94 50088 95 54642 96 59586 97 64947 98 70762 99 77066 100 83895 101 91294 102 99308 103 107981 104 117367 105 127522 106 138501 107 150370 108 163200 109 177058 110 192026 111 208188 112 225629 113 244449 114 264753 115 286645 116 310247 117 335685 118 363090 119 392609 120 424399 121 458619 122 495448 123 535076 124 577699 125 623535 126 672817 127 725781 128 782695 129 843837 130 909501 131 980007 132 1055696 133 1136924 134 1224078 135 1317571 136 1417834 137 1525336 138 1640578 139 1764080 140 1896410 141 2038169 142 2189988 143 2352551 144 2526584 145 2712848 146 2912166 147 3125409 148 3353496 149 3597415 150 3858216 151 4137002 152 4434957 153 4753342 154 5093480 155 5456793 156 5844791 157 6259059 158 6701300 159 7173317 160 7677011 161 8214417 162 8787688 163 9399099 164 10051074 165 10746187 166 11487149 167 12276853 168 13118366 169 14014918 170 14969955 171 15987125 172 17070273 173 18223499 174 19451137 175 20757762 176 22148238 177 23627713 178 25201618 179 26875724 180 28656137 181 30549296 182 32562037 183 34701595 184 36975593 185 39392127 186 41959752 187 44687489 188 47584907 189 50662117 190 53929779 191 57399194 192 61082295 193 64991669 194 69140642 195 73543291 196 78214452 197 83169830 198 88426008 199 94000459 200 99911673 201 106179161 202 112823482 203 119866381 204 127330792 205 135240885 206 143622200 207 152501674 208 161907686 209 171870211 210 182420855 211 193592907 212 205421512 213 217943719 214 231198537 215 245227139 216 260072909 217 275781519 218 292401156 219 309982576 220 328579207 221 348247389 222 369046451 223 391038836 224 414290357 225 438870308 226 464851596 227 492311037 228 521329491 229 551992006 230 584388171 231 618612252 232 654763384 233 692945956 234 733269774 235 775850298 236 820809056 237 868273854 238 918379051 239 971266012 240 1027083379 241 1085987365 242 1148142288 243 1213720875 244 1282904611 245 1355884341 246 1432860618 247 1514044123 248 1599656336 249 1689929941 250 1785109326 251 1885451320 252 1991225685 253 2102715686 254 2220218925 255 2344047915 256 2474530738 257 2612011981 258 2756853420 259 2909434758 260 3070154707 261 3239431754 262 3417705036 263 3605435551 264 3803107045 265 4011227032 266 4230328145 267 4460969174 268 4703736244 269 4959244321 270 5228138443 271 5511095040 272 5808823664 273 6122068394 274 6451609352 275 6798264671 276 7162892093 277 7546390729 278 7949703276 279 8373817849 280 8819770017 281 9288645281 282 9781581208 283 10299769750 284 10844460044 285 11416960871 286 12018643295 287 12650943839 288 13315367309 289 14013489796 290 14746962291 291 15517513890 292 16326955247 293 17177182655 294 18070181704 295 19008031247 296 19992907985 297 21027090670 298 22112964625 299 23253026914 300 24449891172 301 25706292722 302 27025094448 303 28409292299 304 29862021103 305 31386561236 306 32986344861 307 34664962581 308 36426170959 309 38273899625 310 40212258862 311 42245548074 312 44378263908 313 46615108864 314 48961000861 315 51421082496 316 54000730790 317 56705568033 318 59541472288 319 62514588464 320 65631340573 321 68898443647 322 72322916314 323 75912094644 324 79673645665 325 83615581648 326 87746275713 327 92074477185 328 96609327782 329 101360379218 330 106337610640 331 111551446938 332 117012778631 333 122732981631 334 128723937943 335 134998058149 336 141568303740 337 148448210582 338 155651914264 339 163194175364 340 171090406016 341 179356698460 342 188009853654 343 197067411303 344 206547682023 345 216469779736 346 226853655539 347 237720134011 348 249090949791 349 260988785832 350 273437314328 351 286461237994 352 300086333277 353 314339496449 354 329248790194 355 344843492395 356 361154147995 357 378212621600 358 396052152483 359 414707412960 360 434214567740 361 454611335894 362 475937056578 363 498232755935 364 521541216893 365 545907053149 366 571376784499 367 597998915492 368 625824018626 369 654904819169 370 685296283746 371 717055713825 372 750242841245 373 784919927900 374 821151870784 375 859006309534 376 898553738494 377 939867624800 378 983024529314 379 1028104232624 380 1075189867711 381 1124368055862 382 1175729048336 383 1229366875304 384 1285379498590 385 1343868970864 386 1404941602772 387 1468708134569 388 1535283914883 389 1604789088243 390 1677348787842 391 1753093336183 392 1832158455467 393 1914685483962 394 2000821601150 395 2090720063685 396 2184540448126 397 2282448903539 398 2384618416006 399 2491229080844 400 2602468385926 401 2718531508028 402 2839621618096 403 2965950198829 404 3097737376634 405 3235212263827 406 3378613314428 407 3528188695973 408 3684196672903 409 3846906005075 410 4016596364085 411 4193558762569 412 4378096000515 413 4570523131169 414 4771167941661 415 4980371452640 416 5198488439467 417 5425887970188 418 5662953964590 419 5910085777120 420 6167698798819 421 6436225082604 422 6716113995107 423 7007832889850 424 7311867806439 425 7628724199201 426 7958927689757 427 8303024848660 428 8661584009569 429 9035196110341 430 9424475566539 431 9830061180848 432 10252617082870 433 10692833704908 434 11151428797504 435 11629148479158 436 12126768325965 437 12645094505382 438 13184964948297 439 13747250565428 440 14332856512736 441 14942723499571 442 15577829146292 443 16239189396058 444 16927859974476 445 17644937904332 446 18391563080160 447 19168919896528 448 19978238937437 449 20820798731982 450 21697927570183 451 22611005386532 452 23561465717122 453 24550797723870 454 25580548293990 455 26652324221010 456 27767794460581 457 28928692470003 458 30136818637950 459 31394042797665 460 32702306833178 461 34063627385262 462 35480098650635 463 36953895284321 464 38487275412441 465 40082583749022 466 41742254827142 467 43468816352476 468 45264892672661 469 47133208373454 470 49076592010535 471 51097979970074 472 53200420470120 473 55387077712036 474 57661236175211 475 60026305068063 476 62485822944907 477 65043462482405 478 67703035429173 479 70468497738915 480 73343954881137 481 76333667343553 482 79442056337808 483 82673709702396 484 86033388018011 485 89526030947954 486 93156763797391 487 96930904308181 488 100853969702512 489 104931683969577 490 109169985413254 491 113575034474794 492 118153221825491 493 122911176748220 494 127855775823120 495 132994151912922 496 138333703467898 497 143882104167292 498 149647312892978 499 155637584056865 500 161861478300400 501 168327873562233 502 175045976537496 503 182025334548296 504 189275847822185 505 196807782204031 506 204631782322112 507 212758885206440 508 221200534386323 509 229968594489779 510 239075366343994 511 248533602605441 512 258356523944688 513 268557835785817 514 279151745631341 515 290152981000013 516 301576807978191 517 313439050418639 518 325756109815987 519 338544985861100 520 351823297711000 521 365609306005683 522 379921935636179 523 394780799302932 524 410206221898754 525 426219265722624 526 442841756566156 527 460096310710477 528 478006362841389 529 496596194928205 530 515890966107389 531 535916743580820 532 556700534578184 533 578270319427891 534 600655085748947 535 623884863817530 536 647990763156168 537 673005010361299 538 698960988226991 539 725893276217069 540 753837692304865 541 782831336242715 542 812912634318632 543 844121385622599 544 876498809889840 545 910087596983955 546 944931958045759 547 981077678381547 548 1018572172158767 549 1057464538939519 550 1097805622132047 551 1139648069433825 552 1183046395302207 553 1228057045539093 554 1274738464070061 555 1323151161959659 556 1373357788756144 557 1425423206254155 558 1479414564722494 559 1535401381698635 560 1593455623446586 561 1653651789131590 562 1716066997822671 563 1780781078427930 564 1847876662623714 565 1917439280898458 566 1989557461825251 567 2064322834633061 568 2141830235207472 569 2222177815645606 570 2305467157444491 571 2391803388464742 572 2481295303806237 573 2574055490684744 574 2670200457463902 575 2769850766992133 576 2873131174343962 577 2980170769134484 578 3091103122569796 579 3206066439345209 580 3325203714575265 581 3448662895932698 582 3576597051122458 583 3709164540890556 584 3846529197761363 585 3988860510644776 586 4136333815530065 587 4289130492478827 588 4447438169074182 589 4611450930562712 590 4781369536921389 591 4957401647024089 592 5139762050166194 593 5328672905200282 594 5524363987477642 595 5727072943877480 596 5937045556199643 597 6154536013138226 598 6379807191142573 599 6613130944467301 600 6854788404652980 601 7105070289771005 602 7364277223762952 603 7632720066141903 604 7910720252419542 605 8198610145620154 606 8496733399177385 607 8805445331611200 608 9125113313378978 609 9456117166228530 610 9798849575486761 611 10153716515713637 612 10521137690084997 613 10901546983976512 614 11295392933218364 615 11703139207422927 616 12125265108899691 617 12562266087671434 618 13014654273035227 619 13482959022229321 620 13967727486767854 621 14469525196932124 622 14988936665031447 623 15526566008046549 624 16083037590194981 625 16658996686087447 626 17255110165143827 627 17872067197864629 628 18510579984686562 629 19171384508153130 630 19855241309056731 631 20562936287346381 632 21295281528600373 633 22053116156785762 634 22837307214171275 635 23648750569266809 636 24488371853583216 637 25357127428158515 638 26256005380803388 639 27186026554939084 640 28148245611060090 641 29143752121861317 642 30173671701990544 643 31239167173551414 644 32341439768492476 645 33481730368938302 646 34661320786689155 647 35881535083130042 648 37143740930708080 649 38449351017316042 650 39799824494937285 651 41196668473823171 652 42641439563663405 653 44135745463227663 654 45681246599873588 655 47279657820514326 656 48932750135658273 657 50642352518052492 658 52410353757666144 659 54238704374774460 660 56129418592822716 661 58084576372962662 662 60106325512184032 663 62196883806880660 664 64358541283915296 665 66593662501281314 666 68904688920375884 667 71294141352136346 668 73764622479328108 669 76318819457190875 670 78959506594898563 671 81689548120328477 672 84511901030557108 673 87429618030758386 674 90445850564227046 675 93563851936173304 676 96786980534204893 677 100118703148467292 678 103562598394336680 679 107122360240844356 680 110801801648073215 681 114604858316691336 682 118535592553088643 683 122598197253649398 684 126797000011621902 685 131136467350363324 686 135621209086810370 687 140255982828961384 688 145045698611485656 689 149995423673658382 690 155110387383759300 691 160395986314418372 692 165857789473486847 693 171501543694953736 694 177333179194793011 695 183358815296732145 696 189584766332878324 697 196017547724526108 698 202663882248584066 699 209530706495011931 700 216625177521067862 701 223954679708289946 702 231526831828100107 703 239349494322346013 704 247430776805236239 705 255779045793096357 706 264402932668823160 707 273311341888070868 708 282513459434182852 709 292018761529358307 710 301837023609716242 711 311978329571907892 712 322453081299433926 713 333272008477010731 714 344446178701332154 715 355987007897107485 716 367906271047461304 717 380216113247799398 718 392929061092807226 719 406058034406474292 720 419616358325072138 721 433617775743606265 722 448076460136515081 723 463007028763437041 724 478424556271496390 725 494344588705835680 726 510783157940187797 727 527756796539950254 728 545282553070525688 729 563378007863779855 730 582061289256178573 731 601351090312493302 732 621266686049078762 733 641827951171475656 734 663055378341453563 735 684970096988748216 736 707593892683541103 737 730949227086128911 738 755059258490394402 739 779947862978535235 740 805639656204944330 741 832160015827328584 742 859535104604053459 743 887791894177175806 744 916958189560856344 745 947062654355800829 746 978134836710895978 747 1010205196053476014 748 1043305130610670989 749 1077467005744854786 750 1112724183126522355 751 1149111050769003735 752 1186663053950044953 753 1225416727045639597 754 1265409726302644435 755 1306680863577392529 756 1349270141067917836 757 1393218787068634046 758 1438569292777048327 759 1485365450182547683 760 1533652391068605590 761 1583476627160558670 762 1634886091451623923 763 1687930180741219660 764 1742659799420530426 765 1799127404540842316 766 1857387052201658346 767 1917494445296563634 768 1979506982655463335 769 2043483809623402368 770 2109485870117221415 771 2177575960202032564 772 2247818783231195480 773 2320281006594609358 774 2395031320120952169 775 2472140496181312122 776 2551681451542888949 777 2633729311022355282 778 2718361472990402804 779 2805657676780341631 780 2895700072054635574 781 2988573290185321863 782 3084364517705729752 783 3183163571892033198 784 3285062978535384844 785 3390158051966973333 786 3498546977399583695 787 3610330895651612282 788 3725613990321217228 789 3844503577479656035 790 3967110197955401464 791 4093547712282503547 792 4223933398388183248 793 4358388052097358247 794 4497036090533843331 795 4640005658499641059 796 4787428737916643592 797 4939441260417290139 798 5096183223172561008 799 5257798808048806038 800 5424436504187319933 801 5596249234102593576 802 5773394483398516602 803 5956034434204423269 804 6144336102435092047 805 6338471478982397463 806 6538617674949150595 807 6744957071038103707 808 6957677471212938285 809 7176972260751139036 810 7403040568811329968 811 7636087435641770363 812 7876323984560058505 813 8123967598837014737 814 8379242103622141907 815 8642377953051695591 816 8913612422683593336 817 9193189807408148997 818 9481361624987555140 819 9778386825380535343 820 10084532006013696729 821 10400071633165378525 822 10725288269631621417 823 11060472808849364162 824 11405924715656601054 825 11761952273873416161 826 12128872840893695092 827 12507013109482336595 828 12896709376977344822 829 13298307822102509849 830 13712164789601826305 831 14138647082911768210 832 14578132265094343788 833 15031008968259744429 834 15497677211712821961 835 15978548729064943793 836 16474047304559153055 837 16984609118862472180 838 17510683104587046804 839 18052731311808738682 840 18611229283858213078 841 19186666443668012898 842 19779546490966602435 843 20390387810617363641 844 21019723892409615639 845 21668103762616838374 846 22336092427644893606 847 23024271330102816782 848 23733238817637527289 849 24463610624882086184 850 25216020368877651689 851 25991120058338775834 852 26789580617140693657 853 27612092422418569836 854 28459365857678944362 855 29332131881333407448 856 30231142611076702487 857 31157171924542582246 858 32111016076681368942 859 33093494334316266932 860 34105449628347514674 861 35147749224084994585 862 36221285410204022633 863 37326976206832053786 864 38465766093286560141 865 39638626755999518050 866 40846557857178011279 867 42090587824764049793 868 43371774664273034903 869 44691206793105521974 870 46050003897941675123 871 47449317815845383486 872 48890333439721472607 873 50374269648785423326 874 51902380264723935257 875 53475955034242470125 876 55096320638713227405 877 56764841731657385410 878 58482922004814671838 879 60252005283572099106 880 62073576652545641799 881 63949163612129413582 882 65880337266847244440 883 67868713546365176390 884 69915954460045855234 885 72023769385947830253 886 74193916395198198314 887 76428203612691302520 888 78728490615090047920 889 81096689867133776347 890 83534768197282866709 891 86044748313756043443 892 88628710362045865108 893 91288793525026184360 894 94027197666793315906 895 96846185021414403621 896 99748081927787058283 897 102735280611844584269 898 105810241017375298448 899 108975492686757473185 900 112233636692944157119 901 115587347624068932416 902 119039375622079339413 903 122592548476840081196 904 126249773777187758724 905 130014041120457399646 906 133888424382039298467 907 137876084046567377284 908 141980269602381841442 909 146204322000950267909 910 150551676182977234524 911 155025863672977457474 912 159630515244132122480 913 164369363655297587404 914 169246246462084053214 915 174265108903970126478 916 179430006869472484395 917 184745109941442111012 918 190214704524610780785 919 195843197057568849460 920 201635117311411797467 921 207595121777349364781 922 213727997145632912883 923 220038663878217472060 924 226532179877635847888 925 233213744254628699596 926 240088701197140107813 927 247162543943353941741 928 254440918861517968742 929 261929629639373415999 930 269634641586078732593 931 277562086049593418188 932 285718264952564115287 933 294109655449831841043 934 302742914710762267897 935 311624884829683274801 936 320762597867796748880 937 330163281030021020851 938 339834361980309059192 939 349783474299076866824 940 360018463086472771365 941 370547390715313967674 942 381378542737613059363 943 392520433948720945740 944 403981814613215537544 945 415771676856769773452 946 427899261228343924811 947 440374063437158355424 948 453205841269015065310 949 466404621686656390675 950 479980708118969057400 951 493944687943962751124 952 508307440170581586869 953 523080143324535980576 954 538274283543472879107 955 553901662886941385999 956 569974407866749944816 957 586504978203451912476 958 603506175814846030941 959 620991154042528207328 960 638973427122682668682 961 657466879907461631025 962 676485777843464124175 963 696044777213988078984 964 716158935651903127160 965 736843722930165534449 966 758115032037172862006 967 779989190544342494286 968 802482972273485540976 969 825613609271737482398 970 849398804102007652360 971 873856742457111436559 972 899006106105953656477 973 924866086180347565858 974 951456396811271189587 975 978797289123583157314 976 1006909565598452522500 977 1035814594812991052369 978 1065534326566813909988 979 1096091307405504612582 980 1127508696551212080054 981 1159810282250863325274 982 1193020498552744248295 983 1227164442522472197167 984 1262267891909659390212 985 1298357323276855557502 986 1335459930602650082121 987 1373603644371110532902 988 1412817151160045603897 989 1453129913740894688288 990 1494572191703365682941 991 1537175062618277239425 992 1580970443752399852728 993 1625991114349433997785 994 1672270738491623405511 995 1719843888556865488172 996 1768746069286551027261 997 1819013742479752267134 998 1870684352329770125973 999 1923796351419449604340 1000 1978389227392088656706