1 0 2 1 3 126 4 1168 5 7334 6 35749 7 137970 8 438984 9 1208246 10 2969389 11 6662480 12 13873100 13 27144408 14 50389581 15 89424014 16 152638280 17 251834530 18 403250693 19 628798516 20 957543164 21 1427453780 22 2087456085 23 2999819778 24 4242915176 25 5914375214 26 8134700605 27 11051347640 28 14843339788 29 19726445936 30 25958969789 31 33848196630 32 43757545320 33 56114475098 34 71419198421 35 90254252764 36 113294985980 37 141321011500 38 175228691333 39 216044706506 40 264940776264 41 323249589030 42 392482009805 43 474345630368 44 570764730316 45 683901718664 46 816180127405 47 970309230110 48 1149310360328 49 1356545006226 50 1595744759589 51 1871043198980 52 2187009788540 53 2548685875588 54 2961622871861 55 3431922704914 56 3966280627880 57 4572030477470 58 5257192471773 59 6030523641096 60 6901570986764 61 7880727464480 62 8979290890525 63 10209525870758 64 11584728854056 65 13119296413514 66 14828796860405 67 16730045297580 68 18841182220668 69 21181755777116 70 23772807794789 71 26636963693530 72 29798526394760 73 33283574345878 74 37120063777901 75 41337935316464 76 45969225067980 77 51048180304440 78 56611379872013 79 62697859450286 80 69349241790664 81 76609872064130 82 84526958450245 83 93150718100948 84 102534528614396 85 112735085155764 86 123812563363605 87 135830788182050 88 148857408760808 89 162964079566606 90 178226647851389 91 194725347624280 92 212545000275980 93 231775222005968 94 252510638204541 95 274851104943414 96 298901937730280 97 324774147684410 98 352584685292053 99 382456691902076 100 414519759123964 101 448910196291980 102 485771306160965 103 525253669000938 104 567515435259336 105 612722626961414 106 661049448021005 107 712678603635520 108 767801628940748 109 826619227102696 110 889341617025389 111 956188890855230 112 1027391381464200 113 1103190040095858 114 1183836824359781 115 1269595096761764 116 1360740033958780 117 1457559046929380 118 1560352212251893 119 1669432714684466 120 1785127301242664 121 1907776746972030 122 2037736332614685 123 2175376334370728 124 2321082525956876 125 2475256693166464 126 2638317161136605 127 2810699334529990 128 2992856250840488 129 3185259147033386 130 3388398039732789 131 3602782319170380 132 3828941357111420 133 4067425128975548 134 4318804850371621 135 4583673628267514 136 4862647127017480 137 5156364249471350 138 5465487833391533 139 5790705363405456 140 6132729698722764 141 6492299816848280 142 6870181573523405 143 7267168479130318 144 7684082491795016 145 8121774827426914 146 8581126786934405 147 9063050600857460 148 9568490291660028 149 10098422553926676 150 10653857652709589 151 11235840340273730 152 11845450791489640 153 12483805558125038 154 13152058542288061 155 13851401989276664 156 14583067500090380 157 15348327063862320 158 16148494110470973 159 16984924583593046 160 17859018034460264 161 18772218736584730 162 19726016821719125 163 20721949437319708 164 21761601925781756 165 22846609025718764 166 23978656095558405 167 25159480359729930 168 26390872177719368 169 27674676336270566 170 29012793365011789 171 30407180875789280 172 31859854925990860 173 33372891406144328 174 34948427452077101 175 36588662881925214 176 38295861658281480 177 40072353375774290 178 41920534774370213 179 43842871278695236 180 45841898563671164 181 47920224146765380 182 50080529007153845 183 52325569232098898 184 54658177690845096 185 57081265736338014 186 59597824935072605 187 62210928825379400 188 64923734704458508 189 67739485444473056 190 70661511338015389 191 73693231973261030 192 76838158139127080 193 80099893760753418 194 83482137865626741 195 86988686580669164 196 90623435160614780 197 94390380047999260 198 98293620965089253 199 102337363038080026 200 106525918953891464 201 110863711149894230 202 115355274036899565 203 120005256255747888 204 124818422967833036 205 129799658179900664 206 134953967103461005 207 140286478549157870 208 145802447356437448 209 151507256858862146 210 157406421385416389 211 163505588798152980 212 169810543066530300 213 176327206878792308 214 183061644290744981 215 190020063412284514 216 197208819132034280 217 204634415880449230 218 212303510431748093 219 220222914745035416 220 228399598844977164 221 236840693742395280 222 245553494395148285 223 254545462709666678 224 263824230583513576 225 273397602989342714 226 283273561100627605 227 293460265459537340 228 303966059187336188 229 314799471237685836 230 325969219693230789 231 337484215105849130 232 349353563880952520 233 361586571706220998 234 374192747025159821 235 387181804555867264 236 400563668855403980 237 414348477930156200 238 428546586892586733 239 443168571664769406 240 458225232729104264 241 473727598926612530 242 489686931303212005 243 506114727004375268 244 523022723218574716 245 540422901169920164 246 558327490160396405 247 576748971662109810 248 595700083459954728 249 615193823845112126 250 635243455859794589 251 655862511593653480 252 677064796532265740 253 698864393958119488 254 721275669404519261 255 744313275162833414 256 767992154843507880 257 792327547991272170 258 817334994754965173 259 843030340612409996 260 869429741150768764 261 896549666902809980 262 924406908239522725 263 953018580319513658 264 982402128095624456 265 1012575331379209014 266 1043556309962511405 267 1075363528799587280 268 1108015803246213068 269 1141532304359229016 270 1175932564255763789 271 1211236481532790030 272 1247464326747461960 273 1284636747958687778 274 1322774776330391301 275 1361899831796918964 276 1402033728791049980 277 1443198682035069140 278 1485417312395363413 279 1528712652801005186 280 1573108154226786664 281 1618627691741171630 282 1665295570619632445 283 1713136532523841848 284 1762175761747190796 285 1812438891527105264 286 1863952010424636605 287 1916741668771801750 288 1970834885187151208 289 2026259153160044506 290 2083042447704114389 291 2141213232080402780 292 2200800464590653180 293 2261833605441245868 294 2324342623678263941 295 2388358004194179914 296 2453910754806654280 297 2521032413409939110 298 2589755055199381453 299 2660111299969522976 300 2732134319486293964 301 2805857844933801480 302 2881316174436213165 303 2958544180655239838 304 3037577318463721736 305 3118451632695824914 306 3201203765974356005 307 3285870966615705220 308 3372491096612929148 309 3461102639697486596 310 3551744709480142389 311 3644457057671555730 312 3739280082383071400 313 3836254836508233758 314 3935423036185545181 315 4036827069342992264 316 4140510004324864780 317 4246515598601394080 318 4354888307561739293 319 4465673293390851366 320 4578916434030746664 321 4694664332226723530 322 4812964324659056885 323 4933864491160707628 324 5057413664021585276 325 5183661437379903964 326 5312658176701173605 327 5444455028345369690 328 5579103929222826888 329 5716657616539403286 330 5857169637631463789 331 6000694359891232880 332 6147286980783068620 333 6297003537951211448 334 6449900919419563021 335 6606036873884052014 336 6765470021098145480 337 6928259862352066050 338 7094466791046276933 339 7264152103359798356 340 7437378009013920764 341 7614207642131881780 342 7794705072195075605 343 7978935315096365218 344 8166964344291069416 345 8358859102046198414 346 8554687510788513405 347 8754518484551987160 348 8958421940525244428 349 9166468810699562576 350 9378731053618014589 351 9595281666226338230 352 9816194695826116840 353 10041545252130858938 354 10271409519425565461 355 10505864768830375164 356 10744989370668880380 357 10988862806941707020 358 11237565683905954373 359 11491179744761091946 360 11749787882441912264 361 12013474152519140230 362 12282323786208301325 363 12556423203487452608 364 12835860026324382156 365 13120723092013884264 366 13411102466625719405 367 13707089458563869630 368 14008776632237701768 369 14316257821845652466 370 14629628145272050789 371 14948984018097695780 372 15274423167724808060 373 15606044647616976228 374 15943948851654720501 375 16288237528607297714 376 16639013796721373480 377 16996382158427188990 378 17360448515162851613 379 17731320182317380136 380 18109105904293137164 381 18493915869688282880 382 18885861726599886045 383 19285056598048329798 384 19691615097523651496 385 20105653344654457514 386 20527288981000055605 387 20956641185966449100 388 21393830692846838908 389 21838979804987280956 390 22292212412078148389 391 22753654006572049530 392 23223431700228854280 393 23701674240788483318 394 24188512028772116141 395 24684077134412475664 396 25188503314713848780 397 25701926030642503960 398 26224482464448168653 399 26756311537117230926 400 27297553925958331464 401 27848352082321013730 402 28408850249448101765 403 28979194480462476788 404 29559532656488925436 405 30150014504911734164 406 30750791617768706005 407 31362017470282277570 408 31983847439528415848 409 32616438823243976046 410 33259950858773203389 411 33914544742154063480 412 34580383647345087500 413 35257632745593420208 414 35946459224944760381 415 36647032309895885014 416 37359523281190450280 417 38084105495758763930 418 38820954406802225493 419 39570247584023132316 420 40332164734000551164 421 41106887720712956780 422 41894600586208340485 423 42695489571422493578 424 43509743137146171976 425 44337551985141850214 426 45179109079410774605 427 46034609667611027040 428 46904251302627312588 429 47788233864293185736 430 48686759581266431789 431 49600033053058321630 432 50528261272217459720 433 51471653646668946898 434 52430422022209581221 435 53404780705159821764 436 54394946485173241980 437 55401138658204200900 438 56423579049634462133 439 57462492037559492306 440 58518104576235172264 441 59590646219685656030 442 60680349145473114205 443 61787448178630100168 444 62912180815755279116 445 64054787249273261664 446 65215510391859285405 447 66394595901029489510 448 67592292203897529128 449 68808850522098278026 450 70044524896879369589 451 71299572214361327980 452 72574252230967042940 453 73868827599021343388 454 75183563892521426661 455 76518729633078901914 456 77874596316034207880 457 79251438436744166870 458 80649533517043438573 459 82069162131880638896 460 83510607936129890764 461 84974157691578575480 462 86460101294092054925 463 87968731800956136558 464 89500345458398054856 465 91055241729286744514 466 92633723321013182405 467 94236096213551576980 468 95862669687702185468 469 97513756353516540916 470 99189672178905872789 471 100890736518433506530 472 102617272142292029160 473 104369605265466009678 474 106148065577081064701 475 107952986269940061464 476 109784704070247251980 477 111643559267521133840 478 113529895744696834813 479 115444061008418820086 480 117386406219524722664 481 119357286223721099130 482 121357059582451914645 483 123386088603960562748 484 125444739374546227196 485 127533381790015394764 486 129652389587329329605 487 131802140376448321450 488 133983015672373521608 489 136195400927387182406 490 138439685563492117389 491 140716263005051201280 492 143025530711627730380 493 145367890211027465768 494 147743747132543183341 495 150153511240402556414 496 152597596467420198280 497 155076420948854693810 498 157590407056471450853 499 160139981432812203876 500 162725575025672003964 501 165347623122784530980 502 168006565386716565365 503 170702845889972458738 504 173436913150309444136 505 176209220166264628414 506 179020224452894511005 507 181870388077727874920 508 184760177696932897548 509 187690064591699330496 510 190660524704836599389 511 193672038677588676230 512 196725091886666578600 513 199820174481499351658 514 202957781421704390581 515 206138412514777962764 516 209362572454006790780 517 212630770856601558780 518 215943522302053206693 519 219301346370712878266 520 222704767682596390664 521 226154315936414095030 522 229650525948826999085 523 233193937693930024528 524 236785096342963273676 525 240424552304252181464 526 244112861263377430605 527 247850584223575509390 528 251638287546370793288 529 255476542992440033186 530 259365927762710134789 531 263307024539690115380 532 267300421529038125820 533 271346712501364427348 534 275446496834271214421 535 279600379554630176514 536 283808971381098693480 537 288072888766875560750 538 292392753942697142333 539 296769194960074851256 540 301202845734774858764 541 305694346090540935280 542 310244341803061327805 543 314853484644180580118 544 319522432426357203816 545 324251849047368109914 546 329042404535260712405 547 333894775093553616860 548 338809643146686808828 549 343787697385722258476 550 348829632814295859589 551 353936150794821622730 552 359107959094949044040 553 364345771934274572838 554 369650310031308102861 555 375022300650695413664 556 380462477650697490380 557 385971581530927651720 558 391550359480347417773 559 397199565425522050846 560 402919960079136704264 561 408712310988774115730 562 414577392585954783525 563 420515986235440565508 564 426528880284802642556 565 432616870114254789764 566 438780758186752900405 567 445021354098361709330 568 451339474628889664168 569 457735943792792894366 570 464211592890349229789 571 470767260559103222280 572 477403792825583125260 573 484122043157290788128 574 490922872514965423901 575 497807149405122210214 576 504775749932866685480 577 511829557854985903690 578 518969464633317313013 579 526196369488396325036 580 533511179453383543164 581 540914809428272620380 582 548408182234379718245 583 555992228669115540698 584 563667887561040917896 585 571436105825206917014 586 579297838518780458605 587 587254048896956418800 588 595305708469157199308 589 603453797055520748856 590 611699302843678021389 591 620043222445820858030 592 628486560956061281480 593 637030332008083193218 594 645675557833087465541 595 654423269318031422164 596 663274506064163702780 597 672230316445855508660 598 681291757669729228053 599 690459895834085441826 600 699735805988629311464 601 709120572194497353230 602 718615287584585603965 603 728221054424180185688 604 737938984171891277836 605 747770197540891507664 606 757715824560459771005 607 767777004637831497270 608 777954886620356374248 609 788250628857964549946 610 798665399265942330389 611 809200375388018393980 612 819856744459761544700 613 830635703472291028108 614 841538459236300435781 615 852566228446396225514 616 863720237745751886280 617 875001723791078778630 618 886411933317914682893 619 897952123206231089216 620 909623560546360265164 621 921427522705243138280 622 933365297392999032685 623 945438182729818300478 624 957647487313178890376 625 969994530285387897714 626 982480641401449141605 627 995107161097257816740 628 1007875440558123268988 629 1020786841787620945636 630 1033842737676774572789 631 1047044512073569614130 632 1060393559852799066920 633 1073891286986242652798 634 1087539110613180462621 635 1101338459111242116264 636 1115290772167592499980 637 1129397500850455145600 638 1143660107680974317533 639 1158080066705416875206 640 1172658863567714980264 641 1187397995582350719530 642 1202298971807583716405 643 1217363313119022805068 644 1232592552283542843516 645 1247988234033547743164 646 1263551915141580794405 647 1279285164495283369210 648 1295189563172703083528 649 1311266704517952503926 650 1327518194217219484589 651 1343945650375130222480 652 1360550703591466120140 653 1377334997038235547288 654 1394300186537101594061 655 1411447940637166910414 656 1428779940693116727880 657 1446297880943721161570 658 1464003468590697891973 659 1481898423877936327796 660 1499984480171084352764 661 1518263384037498760980 662 1536736895326560487125 663 1555406787250355739458 664 1574274846464724145256 665 1593342873150675020014 666 1612612681096172873405 667 1632086097778293266680 668 1651764964445750137868 669 1671651136201795712816 670 1691746482087494121789 671 1712052885165369843030 672 1732572242603432096360 673 1753306465759576311578 674 1774257480266363798101 675 1795427226116180743964 676 1816817657746777673980 677 1838430744127190498540 678 1860268468844044286213 679 1882332830188240894986 680 1904625841242031598664 681 1927149529966475846630 682 1949905939289287296845 683 1972897127193068263648 684 1996125166803933723596 685 2019592146480526024264 686 2043300169903421442605 687 2067251356164929741150 688 2091447839859287872008 689 2115891771173248980306 690 2140585315977067860389 691 2165530655915884019780 692 2190729988501503507580 693 2216185527204580665668 694 2241899501547200962741 695 2267874157195866072914 696 2294111756054882362280 697 2320614576360153948510 698 2347384912773381500253 699 2374425076476667944776 700 2401737395267532253964 701 2429324213654332480480 702 2457187892952099217565 703 2485330811378780657638 704 2513755364151900426536 705 2542463963585629371914 706 2571459039188272486005 707 2600743037760172144620 708 2630318423492028845948 709 2660187678063640634396 710 2690353300743062396389 711 2720817808486186216730 712 2751583736036743985800 713 2782653636026733449558 714 2814030079077268895981 715 2845715653899857673264 716 2877712967398103736780 717 2910024644769839423480 718 2942653329609686654093 719 2975601684012048765166 720 3008872388674534174664 721 3042468143001813086530 722 3076391665209908441285 723 3110645692430922321428 724 3145232980818199022076 725 3180156305651925998964 726 3215418461445173907605 727 3251022262050376949090 728 3286970540766254739688 729 3323266150445176923086 730 3359911963600971745789 731 3396910872517179817880 732 3434265789355754283020 733 3471979646266208623248 734 3510055395495213325821 735 3548496009496642641014 736 3587304481042072661480 737 3626483823331731955450 738 3666037070105905987733 739 3705967275756796564156 740 3746277515440837536764 741 3786970885191468008780 742 3828050502032364280005 743 3869519504091131775018 744 3911381050713458198216 745 3953638322577729161414 746 3996294521810107531405 747 4039352872100077746560 748 4082816618816456353228 749 4126689029123870014376 750 4170973392099702244589 751 4215673018851510127230 752 4260791242634912271240 753 4306331418971949266738 754 4352296925769917900261 755 4398691163440680392164 756 4445517555020449920380 757 4492779546290053696420 758 4540480605895674861173 759 4588624225470074469746 760 4637213919754294836264 761 4686253226719845511230 762 4735745707691373165725 763 4785694947469816658408 764 4836104554456048562956 765 4886978160775004435264 766 4938319422400301101405 767 4990132019279345249030 768 5042419655458933606568 769 5095186059211345996266 770 5148434983160932548789 771 5202170204411196368780 772 5256395524672372942460 773 5311114770389507580028 774 5366331792871032187301 775 5422050468417842662714 776 5478274698452878217480 777 5535008409651203918390 778 5592255554070597754413 779 5650020109282643529936 780 5708306078504330889164 781 5767117490730163777880 782 5826458400864778650445 783 5886332889856073731598 784 5946745064828850644296 785 6007699059218969716514 786 6069199032908020281605 787 6131249172358507288500 788 6193853690749555539708 789 6257016828113132876756 790 6320742851470793634389 791 6385036054970943686530 792 6449900760026628408680 793 6515341315453844883118 794 6581362097610379674941 795 6647967510535173508664 796 6715161986088214176780 797 6782949984090959013360 798 6851335992467288267453 799 6920324527384990712726 800 6989920133397782831464 801 7060127383587862912730 802 7130950879709001406165 803 7202395252330168874588 804 7274465160979702890236 805 7347165294290015221164 806 7420500370142840656005 807 7494475135815028816970 808 7569094368124880312648 809 7644362873579028583846 810 7720285488519868797389 811 7796867079273535144480 812 7874112542298427901900 813 7952026804334291616008 814 8030614822551845771181 815 8109881584702969306014 816 8189832109271440342280 817 8270471445624232493330 818 8351804674163369120293 819 8433836906478336906116 820 8516573285499060119164 821 8600018985649436939780 822 8684179213001439224885 823 8769059205429777087378 824 8854664232767129668776 825 8940999596959943485214 826 9028070632224799728605 827 9115882705205351906440 828 9204441215129835205388 829 9293751593969148965536 830 9383819306595513653789 831 9474649850941703726630 832 9566248758160857774120 833 9658621592786867338698 834 9751773952895345804021 835 9845711470265178750764 836 9940439810540657177980 837 10035964673394194990300 838 10132291792689632152933 839 10229426936646124918106 840 10327375908002624528264 841 10426144544182945803030 842 10525738717461427018605 843 10626164335129182489968 844 10727427339660949267916 845 10829533708882529364664 846 10932489456138828923405 847 11036300630462495748910 848 11140973316743156617928 849 11246513635897255789826 850 11352927745038496139589 851 11460221837648884336980 852 11568402143750381497340 853 11677474930077160731188 854 11787446500248473021461 855 11898323194942122858914 856 12010111392068555067880 857 12122817506945554256270 858 12236447992473558325373 859 12351009339311587476696 860 12466508076053790154764 861 12582950769406607366480 862 12700344024366556819325 863 12818694484398638322358 864 12938008831615361895656 865 13058293786956400035514 866 13179556110368865584405 867 13301802600988216656380 868 13425040097319790070268 869 13549275477420964744716 870 13674515659083956510789 871 13800767600019245799530 872 13928038298039639663560 873 14056334791244969593478 874 14185664158207426591501 875 14316033518157534966464 876 14447450031170766315980 877 14579920898354795163240 878 14713453362037397717613 879 14848054705954995229886 880 14983732255441843414664 881 15120493377619869414130 882 15258345481589157779045 883 15397296018619086944548 884 15537352482340117679996 885 15678522408936234993764 886 15820813377338044975605 887 15964233009416528060850 888 16108788970177450202408 889 16254488967956433438206 890 16401340754614687343389 891 16549352125735402858280 892 16698530920820809984780 893 16848885023489900845568 894 17000422361676819602141 895 17153150907829920729414 896 17307078679111497146280 897 17462213737598179703210 898 17618564190482009529653 899 17776138190272184745676 900 17934943934997483043964 901 18094989668409361649980 902 18256283680185736169765 903 18418834306135439836538 904 18582649928403364668936 905 18747738975676286055414 906 18914109923389372281005 907 19081771293933380514320 908 19250731656862540774348 909 19420999629103129398296 910 19592583875162733533389 911 19765493107340208177230 912 19939736085936327293000 913 20115321619465130527458 914 20292258564865967061381 915 20470555827716238123764 916 20650222362444839702780 917 20831267172546306988180 918 21013699310795662081493 919 21197527879463966512066 920 21382762030534580098664 921 21569410965920127698030 922 21757483937680175383485 923 21946990248239617598328 924 22137939250607776830476 925 22330340348598217356464 926 22524202997049274604605 927 22719536702045301688790 928 22916351021138634666088 929 23114655563572278072986 930 23314459990503312296789 931 23515774015227024340380 932 23718607403401763540220 933 23922969973274523799148 934 24128871595907253897221 935 24336322195403897445514 936 24545331749138164049480 937 24755910287982033250150 938 24968067896534992813133 939 25181814713354012937056 940 25397160931184257954764 941 25614116797190537102280 942 25832692613189495932205 943 26052898735882549949918 944 26274745577089562052616 945 26498243603983265352914 946 26723403339324432970405 947 26950235361697796376260 948 27178750305748713877628 949 27408958862420590830276 950 27640871779193053169589 951 27874499860320875851730 952 28109853967073667798440 953 28346945017976314940638 954 28585783989050182957661 955 28826381914055081310664 956 29068749884731990170380 957 29312899051046551841120 958 29558840621433328284573 959 29806585863040826348646 960 30056146101977292308264 961 30307532723557277326730 962 30560757172548975447925 963 30815830953422335731308 964 31072765630597950143356 965 31331572828696718820764 966 31592264232790294322405 967 31854851588652306488730 968 32119346703010369528968 969 32385761443798872958166 970 32654107740412558007789 971 32924397583960881135280 972 33196643027523166259660 973 33470856186404547351928 974 33747049238392703010701 975 34025234424015384655214 976 34305424046798739969480 977 34587630473526433233090 978 34871866134499564175813 979 35158143523797386994836 980 35446475199538831175164 981 35736873784144825755380 982 36029351964601428682645 983 36323922492723762902498 984 36620598185420760830696 985 36919391924960718856014 986 37220316659237663524605 987 37523385402038531058200 988 37828611233311161860108 989 38136007299433111664656 990 38445586813481280987389 991 38757363055502364535030 992 39071349372784122235880 993 39387559180127473553018 994 39706005960119416744341 995 40026703263406774735164 996 40349664708970769270780 997 40674903984402425018060 998 41002434846178805286853 999 41332271119940081043626 1000 41664426700767434891464