6 6 7 0 8 7 9 7 10 15 11 15 12 38 13 39 14 67 15 84 16 131 17 160 18 242 19 293 20 421 21 537 22 730 23 912 24 1234 25 1533 26 2021 27 2525 28 3269 29 4053 30 5185 31 6394 32 8080 33 9948 34 12425 35 15219 36 18893 37 23006 38 28319 39 34379 40 42024 41 50788 42 61736 43 74279 44 89795 45 107674 46 129483 47 154660 48 185221 49 220424 50 262820 51 311800 52 370306 53 437872 54 518230 55 610866 56 720505 57 846928 58 995698 59 1167111 60 1368178 61 1599409 62 1869590 63 2180145 64 2541617 65 2956567 66 3438210 67 3990177 68 4629033 69 5360424 70 6204349 71 7169267 72 8280164 73 9548244 74 11004706 75 12665368 76 14568228 77 16734862 78 19212672 79 22029839 80 25245321 81 28896759 82 33056198 83 37773472 84 43138053 85 49213764 86 56111540 87 63914405 88 72758337 89 82750331 90 94058663 91 106818932 92 121239093 93 137492125 94 155832768 95 176480726 96 199750163 97 225916422 98 255366343 99 288446816 100 325631168 101 367354352 102 414197776 103 466702617 104 525582132 105 591510609 106 665358957 107 747965044 108 840394695 109 943682564 110 1059131157 111 1188019513 112 1331933666 113 1492450305 114 1671502991 115 1871027145 116 2093376925 117 2340927639 118 2616537366 119 2923115591 120 3264133618 121 3643142614 122 4064353146 123 4532098396 124 5051473962 125 5627756712 126 6267112851 127 6975951586 128 7761725607 129 8632213713 130 9596405784 131 10663728034 132 11845020467 133 13151679555 134 14596760890 135 16194032380 136 17959191808 137 19908846585 138 22061860469 139 24438229459 140 27060596161 141 29953014331 142 33142622308 143 36658316985 144 40532602624 145 44800137413 146 49499810413 147 54673152173 148 60366629619 149 66629946114 150 73518580200 151 81091933121 152 89416174395 153 98562228227 154 108608920960 155 119640839323 156 131751812229 157 145042591531 158 159624753906 159 175618196673 160 193155455396 161 212379057771 162 233446306646 163 256526437977 164 281805974538 165 309485683416 166 339786509460 167 372946389157 168 409226829227 169 448909518010 170 492303691412 171 539742545799 172 591591408920 173 648244031799 174 710131662623 175 777719158644 176 851515144930 177 932067962028 178 1019976957115 179 1115888374770 180 1220507912431 181 1334596502251 182 1458984377664 183 1594566787274 184 1742319650451 185 1903295352749 186 2078640188731 187 2269590204358 188 2477490750465 189 2703792450989 190 2950073009884 191 3218033521105 192 3509522802772 193 3826534050991 194 4171232147151 195 4545950798598 196 4953223043595 197 5395779188383 198 5876580915849 199 6398820086942 200 6965957051621 201 7581720558637 202 8250150636191 203 8975600063474 204 9762782395134 205 10616775172763 206 11543073931008 207 12547597550491 208 13636748806573 209 14817422525098 210 16097073517413 211 17483727901935 212 18986059574320 213 20613405338467 214 22375850786124 215 24284250210499 216 26350323105284 217 28586679508423 218 31006928745798 219 33625711216548 220 36458820690054 221 39523243966720 222 42837298496624 223 46420681012505 224 50294622739983 225 54481948566060 226 59007251826652 227 63896966120823 228 69179562224465 229 74885634324987 230 81048122290156 231 87702414717303 232 94886599494510 233 102641586767810 234 111011391507686 235 120043279197189 236 129788084969744 237 140300385633940 238 151638859755600 239 163866490577102 240 177050972397033 241 191264948718017 242 206586471445617 243 223099279690631 244 240893318196549 245 260065063469567 246 280718109206249 247 302963546349794 248 326920624793968 249 352717195433424 250 380490457557394 251 410387472647980 252 442566008653838 253 477195135462544 254 514456179320384 255 554543411901678 256 597665128571651 257 644044445251048 258 693920516686564 259 747549455891565 260 805205711329554 261 867183126442541 262 933796495661205 263 1005382784642151 264 1082302888318723 265 1164943033666742 266 1253716766815643 267 1349066563920444 268 1451466076096383 269 1561421978231859 270 1679476505104245 271 1806209570126841 272 1942241631129143 273 2088236116209327 274 2244902660661499 275 2412999882971760 276 2593339040621237 277 2786787202820302 278 2994271380043763 279 3216782147276475 280 3455378306796815 281 3711191023811934 282 3985429090716507 283 4279383642619885 284 4594434101038525 285 4932053546763025 286 5293815428215336 287 5681399680333492 288 6096600294776759 289 6541332282106856 290 7017640214565344 291 7527706142669260 292 8073859232089821 293 8658584761344579 294 9284534990980900 295 9954539381935227 296 10671616853854702 297 11438987382915728 298 12260085822198841 299 13138575059378520 300 14078361595054726 301 15083610459715749 302 16158762771853447 303 17308552640338440 304 18538026947450873 305 19852564492806018 306 21257898278464371 307 22760137178180923 308 24365791037528131 309 26081795189394329 310 27915538715810858 311 29874892172290676 312 31968239402312068 313 34204508872874224 314 36593209482289789 315 39144465960941149 316 41869059161167449 317 44778466034982062 318 47884904956338623 319 51201380844416836 320 54741736137173261 321 58520701700397516 322 62553954139985291 323 66858173217056036 324 71451106271349394 325 76351632943300109 326 81579837576073133 327 87157082144706338 328 93106087600848243 329 99451016019919957 330 106217561970305257 331 113433045003175122 332 121126512259067541 333 129328842562273917 334 138072861613554989 335 147393459104203222 336 157327718005960468 337 167915046279330581 338 179197321952997405 339 191219041190586008 340 204027481041487709 341 217672865841711928 342 232208549742080266 343 247691203641515295 344 264181019848009983 345 281741922004157042 346 300441794500557294 347 320352718144729400 348 341551227254809477 349 364118574132704139 350 388141017109311757 351 413710117242732857 352 440923060952513380 353 469882992764386167 354 500699376594886745 355 533488368793316746 356 568373222609339305 357 605484706277388921 358 644961555706523850 359 686950942902587934 360 731608982500750910 361 779101256413528519 362 829603380472774679 363 883301591869905093 364 940393382872063945 365 1001088158374638975 366 1065607944452544752 367 1134188124161351644 368 1207078229568713529 369 1284542764868782220 370 1366862091498312694 371 1454333348660025203 372 1547271442215900020 373 1646010073835753717 374 1750902845568211646 375 1862324410099089066 376 1980671704215173775 377 2106365234064426660 378 2239850452212550990 379 2381599193331456683 380 2532111211195120621 381 2691915781952209039 382 2861573419205308985 383 3041677663941389271 384 3232856997860188707 385 3435776841131817746 386 3651141686381359235 387 3879697327796698681 388 4122233240627292536 389 4379585067773521918 390 4652637272406236745 391 4942325911024245258 392 5249641589845289543 393 5575632556515654232 394 5921407994258361970 395 6288141467959499615 396 6677074593788379741 397 7089520879266492723 398 7526869810202432731 399 7990591128684653215 400 8482239383700991466 401 9003458695793782400 402 9555987822784672909 403 10141665465095134696 404 10762435903583834865 405 11420354905402669525 406 12117595997087211068 407 12856457037306734381 408 13639367195175818577 409 14468894263382155736 410 15347752419235620222 411 16278810359583450219 412 17265099930403811763 413 18309825173677249659 414 19416371920545980404 415 20588317849934792914 416 21829443150476313542 417 23143741701361882151 418 24535432919419495748 419 26008974184479241903 420 27569074000401980064 421 29220705800217797903 422 30969122563607636716 423 32819872151458812428 424 34778813537364529346 425 36852133837119351858 426 39046366328492008329 427 41368409358639471966 428 43825546344824618220 429 46425466762056964616 430 49176288337672765217 431 52086580342833743358 432 55165388216291260795 433 58422259406816373018 434 61867270686177621560 435 65511056815503192241 436 69364840834663116439 437 73440465854149352034 438 77750428638077705467 439 82307914854595798643 440 87126836302810886947 441 92221869989454125668 442 97608499386416126104 443 103303057739651214614 444 109322773784169744372 445 115685819733215471350 446 122411361921810243739 447 129519613970649980262 448 137031892877926292013 449 144970677903498087627 450 153359672682364487101 451 162223870430839511576 452 171589622714114033398 453 181484711638103594252 454 191938425968438992074 455 202981641039833948755 456 214646902995382789066 457 226968517220201095676 458 239982641548626102879 459 253727384111419103024 460 268242906444937403196 461 283571531731980097461 462 299757858842243305746 463 316848882046618002724 464 334894117122981129177 465 353945733733553278427 466 374058694845108017471 467 395290903079717129006 468 417703354825058510862 469 441360302001433703152 470 466329422377007471196 471 492681998339821873833 472 520493105085569444385 473 549841808143588889559 474 580811371272791832199 475 613489474666540534774 476 647968444576929954291 477 684345494316858192248 478 722722977835440925059 479 763208655848012154554 480 805915975808093509159 481 850964365729155324351 482 898479543243037228678 483 948593839933408312886 484 1001446542438738791646 485 1057184250398545729872 486 1115961252853609974225 487 1177939923214476525730 488 1243291134534922503169 489 1312194695250806337418 490 1384839807257353966011 491 1461425546537998579513 492 1542161368365265162828 493 1627267637346623040277 494 1716976184495697047009 495 1811530891669224594040 496 1911188305723348697736 497 2016218282806067159958 498 2126904665326839910711 499 2243545992106285698369 500 2366456244450320095570 501 2495965628748243768381 502 2632421398559536346544 503 2776188716897546420760 504 2927651561913506023305 505 3087213676810839110872 506 3255299567452272384423 507 3432355548625686049698 508 3618850842712179126073 509 3815278731874505523849 510 4022157767813821239957 511 4240033040382729230971 512 4469477509433184100031 513 4711093401376188047698 514 4965513675190571642476 515 5233403559568444302789 516 5515462166323578085572 517 5812424181984527092553 518 6125061643121270698293 519 6454185797586998005014 520 6800649057682469323857 521 7165347047713270976497 522 7549220752444968840237 523 7953258769246553692414 524 8378499670967826728140 525 8826034482695314410594 526 9297009280019444086107 527 9792627912350044898682 528 10314154859550095376590 529 10862918225858878275693 530 11440312880066974469361 531 12047803746393628451326 532 12686929255781146080016 533 13359304962586796724580 534 14066627337203617668348 535 14810677740175534157662 536 15593326589226002388466 537 16416537725410390471373 538 17282372990775918173764 539 18192997024450759954256 540 19150682290593788744263 541 20157814345910411941679 542 21216897361304959459352 543 22330559906237790030686 544 23501561011595334385749 545 24732796520591403993393 546 26027305744852628501092 547 27388278436251678009036 548 28819062093103133964361 549 30323169612434594432045 550 31904287308536899992912 551 33566283310769534671120 552 35313216362551647478209 553 37149345035902882665069 554 39079137385341818424741 555 41107281057030044694424 556 43238693879010342351000 557 45478534950100514760787 558 47832216255508915454088 559 50305414828569641946590 560 52904085489074747010563 561 55634474179615183196567 562 58503131933029037836992 563 61516929494577677485050 564 64683072634797046688892 565 68009118179066031082684 566 71502990792936629344288 567 75173000551920293164619 568 79027861338142356774035 569 83076710095465309258680 570 87329126989152365570092 571 91795156504854801451955 572 96485329536973487978312 573 101410686504661499302615 574 106582801549843534658234 575 112013807859332231990710 576 117716424170117952460304 577 123703982504084114231426 578 129990457196335448257741 579 136590495267953613209477 580 143519448212922867080746 581 150793405255030131085336 582 158429228150519559063159 583 166444587597760872251734 584 174858001336274834462100 585 183688874002335872524616 586 192957538830628742537754 587 202685301275693283631887 588 212894484650386181690151 589 223608477862209493609676 590 234851785353161004332902 591 246650079331726145540501 592 259030254411823807768449 593 272020484755810639139076 594 285650283846306391831787 595 299950566993206952170594 596 314953716711461547054314 597 330693651086087700841147 598 347205895271751082440432 599 364527656254412986950312 600 382697901035139189900198 601 401757438375604417878413 602 421749004279258649419141 603 442717351360810319602964 604 464709342293064434692494 605 487774047498079480033125 606 511962847288053611478453 607 537329538638503589776493 608 563930446816934428281147 609 591824542066565185680878 610 621073561587630794850373 611 651742137034355456286042 612 683897927791103393930061 613 717611760265992460954264 614 752957773488271538052881 615 790013571269740007728360 616 828860381241267144719995 617 869583221048645512249838 618 912271072045720219255504 619 957017060795115502902781 620 1003918648743696130147034 621 1053077830411486924278229 622 1104601340492889704470277 623 1158600870239841128861003 624 1215193293560169534200094 625 1274500903234448204227327 626 1336651657721973245139575 627 1401779438995784805858445 628 1470024321917929048764182 629 1541532855634727635641565 630 1616458357547289084590819 631 1694961220380378400698366 632 1777209232952681308428634 633 1863377915218728771328686 634 1953650868237400611228409 635 2048220139688552482570948 636 2147286605648989766491324 637 2251060369305090889071226 638 2359761177374407733947091 639 2473618854974163286659094 640 2592873759775278802145583 641 2717777256245746351280200 642 2848592210893918609571783 643 2985593509387151591213211 644 3129068596534424705977812 645 3279318040086201050862488 646 3436656119424827375319192 647 3601411440183302545785252 648 3773927575957563258959994 649 3954563738241987649993583 650 4143695475852894629403829 651 4341715405069531546028720 652 4549033971865383596590074 653 4766080247567683467540919 654 4993302759435136672570448 655 5231170357609441300159058 656 5480173120057692706811924 657 5740823297089046353182162 658 6013656297200517401578561 659 6299231715974032715903196 660 6598134409929002174517609 661 6910975617203129398906862 662 7238394127127687104294417 663 7581057500733432826344747 664 7939663344428957201507535 665 8314940639065028211726725 666 8707651126817022714995184 667 9118590758291486811912154 668 9548591202495173709225888 669 9998521422281422584906935 670 10469289318135757140250997 671 10961843443142100256157858 672 11477174792233707571758329 673 12016318668815927103186199 674 12580356632127354799501479 675 13170418528692967992942099 676 13787684611520178710585712 677 14433387750680355747371409 678 15108815739234831273867933 679 15815313698461255252914914 680 16554286586673044191832069 681 17327201815927455257332527 682 18135591981276519611878568 683 18981057707224569261030732 684 19865270616438104329551563 685 20789976425770818350655790 686 21756998175073533653330538 687 22768239594284361751477514 688 23825688614727988194048656 689 24931421030588061596686398 690 26087604316978739155119553 691 27296501611087160479433352 692 28560475863351169206624311 693 29881994165694171760328228 694 31263632264364176186175232 695 32708079264994814827532327 696 34218142538066183357044836 697 35796752833028744364112430 698 37446969609950899444716139 699 39171986597652484921396530 700 40975137587923759350614655 701 42859902475549080529914723 702 44829913554534544276404354 703 46888962081078365162852474 704 49041005114548643779070687 705 51290172647894603029812295 706 53640775039692279856650829 707 56097310760211281562871440 708 58664474464716627485546287 709 61347165407431958893419469 710 64150496210474062704505884 711 67079802002310206422914329 712 70140649941233713767241855 713 73338849139626956721396822 714 76680461005789433405877977 715 80171810020417699731021368 716 83819494965901609013803283 717 87630400626949174151645601 718 91611709982204217613899312 719 95770916906911324779154256 720 100115839407913946487510525 721 104654633412708385010504795 722 109395807135592940014943516 723 114348236044439287671151797 724 119521178453021076032906427 725 124924291764378193343673974 726 130567649392201028645530521 727 136461758387823367475129079 728 142617577802023480319622141 729 149046537811503718179994693 730 155760559641642521299342330 731 162772076317856018789488714 732 170094054279750827108534462 733 177740015893072033271235872 734 185724062896424413484765065 735 194060900820653534751243336 736 202765864420886534407160519 737 211854944162234923956338896 738 221344813802424112234409880 739 231252859115719225508162913 740 241597207804939253852298022 741 252396760649567804146849536 742 263671223940563005632609063 743 275441143253806548738645504 744 287727938616910464919225583 745 300553941125569494527847724 746 313942431068623392942639880 747 327917677622606024341512686 748 342504980179746990471242638 749 357730711375159727606438280 750 373622361882366859270851345 751 390208587048250901869684872 752 407519255442179987803921255 753 425585499396179193268897558 754 444439767616942340268729719 755 464115879952799379134648639 756 484649084402960756260283644 757 506076116458896689471184571 758 528435260872218365753956135 759 551766415946199165223633531 760 576111160452908223633428481 761 601512823280954107553527984 762 628016555924019640201582135 763 655669407923670135221057374 764 684520405385475379393681495 765 714620632691085729034918172 766 746023317534863267554077758 767 778783919417592728762159121 768 812960221736189662692317918 769 848612427612597719100699955 770 885803259611923831665105623 771 924598063504514116861836597 772 965064916234028664610674070 773 1007274738258638395493094002 774 1051301410440357796642009246 775 1097221895663037117294150590 776 1145116365368003123763577758 777 1195068331202328465317123377 778 1247164781983792650487375409 779 1301496326193109094092477841 780 1358157340213738724311173549 781 1417246122546685015245270109 782 1478865054238123518417585154 783 1543120765765401922292358854 784 1610124310638169795765367807 785 1679991345979737994200535235 786 1752842320365812344067286422 787 1828802669206798035671816886 788 1908003017972798152172309159 789 1990579393570249756675255077 790 2076673444193015678465236444 791 2166432667981400003310927854 792 2260010650837447848931871789 793 2357567313756436204770523366 794 2459269170050448446449951945 795 2565289592852439198078297068 796 2675809093306356279684860507 797 2791015609862445522199732905 798 2911104809115285427303458469 799 3036280398636785728743981582 800 3166754452276159635211516526 801 3302747748414784007093320155 802 3444490121685092270686442565 803 3592220828679863027796214158 804 3746188928201060329040665587 805 3906653676616017074917303083 806 4073884938913224136262555958 807 4248163616070152123913650291 808 4429782089371806172834138133 809 4619044682340527378398655091 810 4816268140965763531479174723 811 5021782132946123242467502415 812 5235929766686315301661096775 813 5459068130817083714721537909 814 5691568855038769076513836546 815 5933818693116702303556186421 816 6186220128891554381157778588 817 6449192006197568859542127394 818 6723170183619096053085960143 819 7008608215048051736805701284 820 7305978057045180134411708097 821 7615770804042791806489264308 822 7938497452469872899618272775 823 8274689694918040262455085842 824 8624900745513230796772271691 825 8989706197698593924454122749 826 9369704915683893158619041864 827 9765519960860537277671913148 828 10177799554534874330052280743 829 10607218078379679118571225489 830 11054477114061224143431601499 831 11520306523550371778855750954 832 12005465571687822207559498001 833 12510744092628737412202066155 834 13036963701858207671297063800 835 13584979055528459863412396398 836 14155679158939837341157966705 837 14749988726051693130591097035 838 15368869591985712354488736567 839 16013322180553327844443936431 840 16684387028920896221143485102 841 17383146371600869362760790864 842 18110725786045242405482369590 843 18868295902197958513141440445 844 19657074178457483681236105027 845 20478326746587437975015912522 846 21333370328214665524736542561 847 22223574225647548172340117781 848 23150362389856337365683326769 849 24115215568557961351478948693 850 25119673537464756232659460462 851 26165337417865060126820781127 852 27253872083829210700905015794 853 28387008662451374057481847494 854 29566547130672474048685767521 855 30794359012355407898888360207 856 32072390179428491461909396165 857 33402663761048702128547380623 858 34787283164891686337007920899 859 36228435214821559909456570668 860 37728393409360347706808675910 861 39289521305534188995918640788 862 40914276032852506657213588386 863 42605211942345676484380077360 864 44364984395778952307856254518 865 46196353700342700114852634836 866 48102189194325320643356193392 867 50085473489471463534195833619 868 52149306875949597570993034474 869 54296911896064189000892606973 870 56531638093085438823390598308 871 58856966941796794679223723410 872 61276516967615571265901560845 873 63794049061386549629511122997 874 66413471997222230442200906308 875 69138848161026506038187495008 876 71974399497632365238398541695 877 74924513684767262651680178397 878 77993750542375133770082765485 879 81186848686128457224019100777 880 84508732434302176012274333246 881 87964518977508693538299050582 882 91559525821156303773245238963 883 95299278510845499025612540208 884 99189518651307267685178578404 885 103236212229866077318991753623 886 107445558255828353552504718614 887 111823997727604297449150467120 888 116378222939819503351822606034 889 121115187143110411946833838986 890 126042114569778962222482486557 891 131166510838952161134579176121 892 136496173755408691426374520558 893 142039204516740219116605562244 894 147804019344069068048514646270 895 153799361552087232417641779350 896 160034314074776020690240513871 897 166518312463749451763556302891 898 173261158376802069008201328087 899 180273033574869149175864761944 900 187564514446291162552859666262 901 195146587077948308241438924450 902 203030662893564496486317355815 903 211228594880204172829576753365 904 219752694424772166568763671428 905 228615748783104466954275396550 906 237831039205081682243315867480 907 247412359740032258871973435758 908 257374036747597549687369323948 909 267730949140127924950010921300 910 278498549383649677883627721893 911 289692885285405843917097114652 912 301330622597014853975520546106 913 313429068463325371266463791611 914 326006195748161734841976988464 915 339080668269265064332879736112 916 352671866975931811789835385480 917 366799917104043885767605252303 918 381485716344467627176859141706 919 396750964062078860751343741080 920 412618191604046995625780932034 921 429110793737385012937056795953 922 446253061257247130925393022631 923 464070214808930485341380690257 924 482588439968118391255632840046 925 501834923625485224114706220089 926 521837891723478032962539496831 927 542626648394788148062306539288 928 564231616553843070514533666210 929 586684379994471059550400051898 930 610017727048838481303583419932 931 634265695864714976642650380669 932 659463621360209058253079422954 933 685648183917214119552117632014 934 712857459877042227822482063273 935 741130973903973008164042465718 936 770509753284842780172205007193 937 801036384235212504779855200318 938 832755070285222792397240788208 939 865711692820832745264122151234 940 899953873858893107414316423778 941 935531041137280327941324627532 942 972494495604268868864101192216 943 1010897481394296191400995717888 944 1050795258380436533017842927334 945 1092245177397091955469124813672 946 1135306758229796674994456031164 947 1180041770472453615084862333920 948 1226514317355951442961808448206 949 1274790922655780206997144756526 950 1324940620790151850568924307655 951 1377035050224066168669640730010 952 1431148550298928003209121521492 953 1487358261611538928538179878066 954 1545744230070748480431594228999 955 1606389514764570637665743060265 956 1669380299775350494736244927535 957 1734806010085411350594253411806 958 1802759431720731398093251630724 959 1873336836285392037103364597540 960 1946638110045022372706885096719 961 2022766887723029364517473079145 962 2101830691179274710917479482126 963 2183941073146822738786800032897 964 2269213766208671531646868124711 965 2357768837202769032810128907028 966 2449730847250349316825094756753 967 2545229017609470020354140240699 968 2644397401562842038666347099123 969 2747375062556376737727471685230 970 2854306258812596020034153652765 971 2965340634650907341150104024627 972 3080633418755011446445904221428 973 3200345629636126608048775364492 974 3324644288549562464244895873673 975 3453702640131190990513294607183 976 3587700381029835788661749567762 977 3726823896821255590051992593090 978 3871266507499539343773473934387 979 4021228721852070003029940128449 980 4176918501035069886361281715456 981 4338551531677813095065692824687 982 4506351508855210181013653904042 983 4680550429280326845073555810373 984 4861388895080835174894356410178 985 5049116428536091128571345923010 986 5243991798164842418383198597692 987 5446283356567163137147093207414 988 5656269390438456222124687715224 989 5874238483187916412687459156782 990 6100489890609090144060436393135 991 6335333930065746409086280991899 992 6579092383672584593469359231673 993 6832098915966980123978048304366 994 7094699506585422805672453414928 995 7367252898476150888667602895454 996 7650131062198158919306580796692 997 7943719676875860208640255517517 998 8248418628398665037915684312681 999 8564642525475179941526266806945 1000 8892821234173109002407525001094