1 1
2 924
3 8989
4 37270
5 145233
6 525796
7 1605490
8 4136952
9 9435413
10 19632414
11 37957424
12 69050898
13 119351315
14 197524064
15 314935542
16 486171662
17 729604121
18 1068003424
19 1529198580
20 2146783422
21 2960869583
22 4018886128
23 5376425842
24 7098138174
25 9258668837
26 11943646064
27 15250713520
28 19290609870
29 24188295003
30 30084122912
31 37135061230
32 45515957422
33 55420851633
34 67064336192
35 80682961772
36 96536690206
37 114910393959
38 136115402256
39 160491093866
40 188406536542
41 220262173117
42 256491554256
43 297563117864
44 343982015150
45 396291983347
46 455077265088
47 520964574438
48 594625109582
49 676776612169
50 768185473312
51 869668886244
52 982097045630
53 1106395393535
54 1243546912048
55 1394594462562
56 1560643171710
57 1742862863957
58 1942490540848
59 2160832906912
60 2399268942222
61 2659252521611
62 2942315080544
63 3250068327646
64 3584207003886
65 3946511688417
66 4338851651072
67 4763187751516
68 5221575385054
69 5716167475095
70 6249217512272
71 6823082640218
72 7440226787998
73 8103223849197
74 8814760907664
75 9577641509912
76 10394788984174
77 11269249806115
78 12204197011200
79 13202933653718
80 14268896312462
81 15405658643065
82 16616934976992
83 17906583967188
84 19278612280382
85 20737178336047
86 22286596092016
87 23931338876754
88 25676043268286
89 27525513019781
90 29484723031792
91 31558823371152
92 33753143336526
93 36073195570619
94 38524680219040
95 41113489135822
96 43845710135598
97 46727631292433
98 49765745285312
99 52966753790284
100 56337571919262
101 59885332705479
102 63617391635600
103 67541331228490
104 71664965660638
105 75996345438237
106 80543762115920
107 85315753062152
108 90321106271278
109 95568865222227
110 101068333783872
111 106829081167046
112 112860946923214
113 119174045989801
114 125778773782176
115 132685811332292
116 139906130473982
117 147450999074911
118 155331986315184
119 163560968012610
120 172150131994622
121 181111983516853
122 190459350728368
123 200205390183552
124 210363592400654
125 220947787466987
126 231972150690784
127 243451208299710
128 255399843186030
129 267833300698433
130 280767194480512
131 294217512355900
132 308200622260062
133 322733278218743
134 337832626373072
135 353516211051322
136 369801980887326
137 386708294985549
138 404253929132816
139 422458082056696
140 441340381730542
141 460920891725187
142 481220117607296
143 502259013384374
144 524058987996430
145 546641911854297
146 570030123424608
147 594246435861428
148 619314143684542
149 645257029504399
150 672099370793712
151 699865946705714
152 728582044939070
153 758273468649445
154 788966543407728
155 820688124204912
156 853465602503630
157 887326913336347
158 922300542450208
159 958415533498542
160 995701495279022
161 1034188609018481
162 1073907635704384
163 1114889923462956
164 1157167414983966
165 1200772654992167
166 1245738797765392
167 1292099614699306
168 1339889501918814
169 1389143487936125
170 1439897241355472
171 1492187078624488
172 1546049971832238
173 1601523556553907
174 1658646139742144
175 1717456707665062
176 1777994933890894
177 1840301187319305
178 1904416540259360
179 1970382776554148
180 2038242399752062
181 2108038641324735
182 2179815468931632
183 2253617594731298
184 2329490483739262
185 2407480362232597
186 2487634226201136
187 2569999849845344
188 2654625794120846
189 2741561415329611
190 2830856873757792
191 2922563142360222
192 3016732015491566
193 3113416117684129
194 3212668912472320
195 3314544711263772
196 3419098682257118
197 3526386859406423
198 3636466151432272
199 3749394350879514
200 3865230143221662
201 3984033116011949
202 4105863768081040
203 4230783518781400
204 4358854717278318
205 4490140651887587
206 4624705559459840
207 4762614634811542
208 4903934040202638
209 5048730914860857
210 5197073384552672
211 5349030571200916
212 5504672602549054
213 5664070621872111
214 5827296797734256
215 5994424333793042
216 6165527478650302
217 6340681535749701
218 6519962873320944
219 6703448934370640
220 6891218246719822
221 7083350433088123
222 7279926221224608
223 7481027454085262
224 7686737100057134
225 7897139263229137
226 8112319193709504
227 8332363297989900
228 8557359149356190
229 8787395498345863
230 9022562283252112
231 9262950640674570
232 9508652916116702
233 9759762674629853
234 10016374711503952
235 10278585063004872
236 10546491017158446
237 10820191124581139
238 11099785209357376
239 11385374379963526
240 11677061040238542
241 11974948900401257
242 12279142988114336
243 12589749659594884
244 12906876610771710
245 13230632888489247
246 13561128901758128
247 13898476433052418
248 14242788649653502
249 14594180115040629
250 14952766800328112
251 15318666095749184
252 15691996822186510
253 16072879242749355
254 16461435074397408
255 16857787499611262
256 17262061178109550
257 17674382258612737
258 18094878390653568
259 18523678736434172
260 18960913982729822
261 19406716352839351
262 19861219618582224
263 20324559112342266
264 20796871739158046
265 21278295988859917
266 21768971948253712
267 22269041313351096
268 22778647401646574
269 23297935164441155
270 23827051199212672
271 24366143762032758
272 24915362780030478
273 25474859863902617
274 26044788320470624
275 26625303165284212
276 27216561135271614
277 27818720701436495
278 28431942081601520
279 29056387253198578
280 29692219966105662
281 30339605755530405
282 30998711954940272
283 31669707709039408
284 32352763986792142
285 33048053594493147
286 33755751188884256
287 34476033290317934
288 35209078295967406
289 35955066493083441
290 36714180072297792
291 37486603140973292
292 38272521736600606
293 39072123840241639
294 39885599390019600
295 40713140294655722
296 41554940447052638
297 42411195737924413
298 43282104069473232
299 44167865369112744
300 45068681603238062
301 45984756791042419
302 46916297018380480
303 47863510451678310
304 48826607351889998
305 49805800088500937
306 50801303153577760
307 51813333175864932
308 52842108934927998
309 53887851375343487
310 54950783620935472
311 56031130989058786
312 57129121004928894
313 58244983415998421
314 59378950206380336
315 60531255611317792
316 61702136131700622
317 62891830548628491
318 64100579938020704
319 65328627685272670
320 66576219499959022
321 67843603430583393
322 69131029879374848
323 70438751617130972
324 71767023798107614
325 73116103974955287
326 74486252113702224
327 75877730608784090
328 77290804298120350
329 78725740478237293
330 80182808919437712
331 81662281881017240
332 83164434126527342
333 84689542939084963
334 86237888136728832
335 87809752087822422
336 89405419726503566
337 91025178568180729
338 92669318725075936
339 94338132921814356
340 96031916511060542
341 97750967489201327
342 99495586512075376
343 101266076910749394
344 103062744707340990
345 104885898630888197
346 106735850133265648
347 108612913405147408
348 110517405392016462
349 112449645810220859
350 114409957163076512
351 116398664757016654
352 118416096717787950
353 120462584006693265
354 122538460436881088
355 124644062689681612
356 126779730330989470
357 128945805827693127
358 131142634564150928
359 133370564858713802
360 135629947980294622
361 137921138164984221
362 140244492632714064
363 142600371603965576
364 144989138316526126
365 147411159042291667
366 149866803104116032
367 152356442892706886
368 154880453883568334
369 157439214653990185
370 160033106900083872
371 162662515453865028
372 165327828300382718
373 168029436594895327
374 170767734680093104
375 173543120103367362
376 176355993634126334
377 179206759281157685
378 182095824310037680
379 185023599260587008
380 187990497964373262
381 190996937562260075
382 194043338522002912
383 197130124655891518
384 200257723138439022
385 203426564524117697
386 206637082765141376
387 209889715229294524
388 213184902717807966
389 216523089483281271
390 219904723247651792
391 223330255220210362
392 226800140115663646
393 230314836172243149
394 233874805169860880
395 237480512448311672
396 241132426925522158
397 244831021115846403
398 248576771148408192
399 252370156785489974
400 256211661440968462
401 260101772198796889
402 264040979831533920
403 268029778818919220
404 272068667366495678
405 276158147424278287
406 280298724705469680
407 284490908705222322
408 288735212719447358
409 293032153863670117
410 297382253091932272
411 301786035215740656
412 306244028923062734
413 310756766797368731
414 315324785336720416
415 319948624972906542
416 324628830090624942
417 329365949046711281
418 334160534189414464
419 339013141877718700
420 343924332500712222
421 348894670497002663
422 353924724374179088
423 359015066728320682
424 364166274263552094
425 369378927811645437
426 374653612351668944
427 379990917029682280
428 385391435178478510
429 390855764337372723
430 396384506272037312
431 401978266994383910
432 407637656782491982
433 413363290200584073
434 419155786119047712
435 425015767734503972
436 430943862589922686
437 436940702594784319
438 443006924045288496
439 449143167644609186
440 455350078523196542
441 461628306259125397
442 467978504898490416
443 474401332975847904
444 480897453534704270
445 487467534148051147
446 494112246938947168
447 500832268601146398
448 507628280419773422
449 514500968292045089
450 521451022748038912
451 528479138971508124
452 535586016820743390
453 542772360849481175
454 550038880327858768
455 557386289263415962
456 564815306422143390
457 572326655349577517
458 579921064391942288
459 587599266717337432
460 595362000336973422
461 603210008126453091
462 611144037847099904
463 619164842167332886
464 627273178684088206
465 635469809944287417
466 643755503466352352
467 652131031761766676
468 660597172356684094
469 669154707813583215
470 677804425752969072
471 686547118875121298
472 695383584981888958
473 704314626998532037
474 713341052995609584
475 722463676210914512
476 731683315071455054
477 741000793215482875
478 750416939514567840
479 759932588095719438
480 769548578363554862
481 779265755022513745
482 789084968099119552
483 799007072964287628
484 809032930355679902
485 819163406400106247
486 829399372635972496
487 839741706035775114
488 850191289028642526
489 860749009522923101
490 871415760928819792
491 882192442181071432
492 893079957761680686
493 904079217722688659
494 915191137708996160
495 926416638981231622
496 937756648438665678
497 949212098642172393
498 960783927837237152
499 972473079977011204
500 984280504745412862
501 996207157580275359
502 1008253999696541360
503 1020421998109504130
504 1032712125658095358
505 1045125361028219637
506 1057662688776135600
507 1070325099351883712
508 1083113589122760718
509 1096029160396840747
510 1109072821446543072
511 1122245586532246526
512 1135548475925950574
513 1148982515934983041
514 1162548738925754496
515 1176248183347559292
516 1190081893756423262
517 1204050920838998071
518 1218156321436502224
519 1232399158568708730
520 1246780501457979422
521 1261301425553345933
522 1275963012554637328
523 1290766350436654392
524 1305712533473390574
525 1320802662262299587
526 1336037843748609664
527 1351419191249684470
528 1366947824479430670
529 1382624869572752153
530 1398451459110050912
531 1414428732141774580
532 1430557834213010622
533 1446839917388127183
534 1463276140275460592
535 1479867668052049522
536 1496615672488415806
537 1513521331973391909
538 1530585831538995056
539 1547810362885348016
540 1565196124405646542
541 1582744321211173467
542 1600456165156359456
543 1618332874863890414
544 1636375675749861550
545 1654585800048978097
546 1672964486839802688
547 1691512982070049388
548 1710232538581924382
549 1729124416137513319
550 1748189881444215312
551 1767430208180223594
552 1786846677020052830
553 1806440575660113085
554 1826213198844330448
555 1846165848389814312
556 1866299833212571310
557 1886616469353265907
558 1907117080003027648
559 1927802995529305062
560 1948675553501766222
561 1969736098718245961
562 1990985983230739744
563 2012426566371444196
564 2034059214778844286
565 2055885302423847167
566 2077906210635962672
567 2100123328129530466
568 2122538051029993854
569 2145151782900220245
570 2167965934766868272
571 2190981925146801568
572 2214201180073549198
573 2237625133123812747
574 2261255225444020064
575 2285092905776925662
576 2309139630488257774
577 2333396863593412065
578 2357866076784192000
579 2382548749455595868
580 2407446368732650462
581 2432560429497291415
582 2457892434415290192
583 2483443893963227738
584 2509216326455514782
585 2535211258071458797
586 2561430222882377616
587 2587874762878759704
588 2614546427997471086
589 2641446776149008931
590 2668577373244801792
591 2695939793224556502
592 2723535618083651726
593 2751366437900578169
594 2779433850864425440
595 2807739463302415572
596 2836284889707483198
597 2865071752765902383
598 2894101683384960112
599 2923376320720676434
600 2952897312205571262
601 2982666313576477829
602 3012684988902402800
603 3042955010612433040
604 3073478059523689038
605 3104255824869324987
606 3135290004326575520
607 3166582304044849102
608 3198134438673868078
609 3229948131391855377
610 3262025113933767872
611 3294367126619576396
612 3326975918382592414
613 3359853246797841351
614 3393000878110482576
615 3426420587264276042
616 3460114157930095582
617 3494083382534488861
618 3528330062288283984
619 3562856007215242760
620 3597663036180760622
621 3632752976920613203
622 3668127666069749568
623 3703788949191132102
624 3739738680804623054
625 3775978724415917737
626 3812510952545524384
627 3849337246757790660
628 3886459497689976830
629 3923879605081375583
630 3961599477802478512
631 3999621033884189250
632 4037946200547083262
633 4076576914230714293
634 4115515120622967472
635 4154762774689459072
636 4194321840702982926
637 4234194292273003499
638 4274382112375195616
639 4314887293381030846
640 4355711837087410542
641 4396857754746345537
642 4438327067094682496
643 4480121804383876924
644 4522244006409812830
645 4564695722542669047
646 4607479011756832208
647 4650595942660856378
648 4694048593527469342
649 4737839052323625549
650 4781969416740605712
651 4826441794224163064
652 4871258302004716270
653 4916421067127588995
654 4961932226483296128
655 5007793926837876662
656 5054008324863273230
657 5100577587167758297
658 5147503890326407008
659 5194789420911616692
660 5242436375523673022
661 5290446960821362831
662 5338823393552633584
663 5387567900585299506
664 5436682718937794366
665 5486170095809970917
666 5536032288613946992
667 5586271565004998256
668 5636890202912497614
669 5687890490570901275
670 5739274726550781472
671 5791045219789905838
672 5843204289624363438
673 5895754265819737457
674 5948697488602324544
675 6002036308690400812
676 6055773087325534494
677 6109910196303945255
678 6164450018007910160
679 6219394945437216298
680 6274747382240660062
681 6330509742747593085
682 6386684451999514832
683 6443273945781711848
684 6500280670654943662
685 6557707083987175347
686 6615555653985356736
687 6673828859727248294
688 6732529191193293646
689 6791659149298538761
690 6851221245924597792
691 6911218003951665572
692 6971651957290576766
693 7032525650914911679
694 7093841640893148720
695 7155602494420863522
696 7217810789852974718
697 7280469116736036373
698 7343580075840577072
699 7407146279193485664
700 7471170350110443662
701 7535654923228404299
702 7600602644538118240
703 7666016171416705950
704 7731898172660276718
705 7798251328516594337
706 7865078330717789440
707 7932381882513118492
708 8000164698701769438
709 8068429505665714007
710 8137179041402606672
711 8206416055558730266
712 8276143309461988254
713 8346363576154943661
714 8417079640427904656
715 8488294298852056792
716 8560010359812641902
717 8632230643542183651
718 8704957982153759744
719 8778195219674320790
720 8851945212078055822
721 8926210827319804473
722 9000994945368515808
723 9076300458240753812
724 9152130270034249534
725 9228487296961499887
726 9305374467383413104
727 9382794721843000850
728 9460751013099116990
729 9539246306160243013
730 9618283578318320112
731 9697865819182627920
732 9777996030713709902
733 9858677227257345403
734 9939912435578568352
735 10021704694895732622
736 10104057056914624046
737 10186972585862619089
738 10270454358522890176
739 10354505464268657676
740 10439129005097488542
741 10524328095665641607
742 10610105863322459536
743 10696465448144807434
744 10783410002971558110
745 10870942693438123997
746 10959066698011035728
747 11047785208022567368
748 11137101427705408302
749 11227018574227381779
750 11317539877726210112
751 11408668581344326534
752 11500407941263733710
753 11592761226740908905
754 11685731720141755808
755 11779322716976603012
756 11873537525935249150
757 11968379468922054687
758 12063851881091080368
759 12159958110881272322
760 12256701520051693822
761 12354085483716803701
762 12452113390381781424
763 12550788641977898816
764 12650114653897938446
765 12750094855031658667
766 12850732687801305312
767 12952031608197170046
768 13053995085813195374
769 13156626603882626305
770 13259929659313708672
771 13363907762725434108
772 13468564438483331678
773 13573903224735306167
774 13679927673447523024
775 13786641350440339962
776 13894047835424285214
777 14002150722036082445
778 14110953617874722320
779 14220460144537580728
780 14330673937656583662
781 14441598646934418755
782 14553237936180793472
783 14665595483348739958
784 14778674980570966542
785 14892480134196255897
786 15007014664825909856
787 15122282307350240884
788 15238286810985110206
789 15355031939308512591
790 15472521470297207792
791 15590759196363398642
792 15709748924391455806
793 15829494475774689189
794 15949999686452166000
795 16071268406945575472
796 16193304502396140238
797 16316111852601574363
798 16439694352053088032
799 16564055909972438894
800 16689200450349030062
801 16815131911977054769
802 16941854248492687680
803 17069371428411322860
804 17197687435164858398
805 17326806267139027687
806 17456731937710777360
807 17587468475285691882
808 17719019923335464798
809 17851390340435416637
810 17984583800302059472
811 18118604391830708136
812 18253456219133138094
813 18389143401575289971
814 18525670073815020736
815 18663040385839901542
816 18801258503005062222
817 18940328606071082441
818 19080254891241929504
819 19221041570202942820
820 19362692870158865022
821 19505213033871919743
822 19648606319699936048
823 19792877001634519522
824 19938029369339270014
825 20084067728188046037
826 20230996399303275824
827 20378819719594315040
828 20527542041795851150
829 20677167734506354443
830 20827701182226575712
831 20979146785398090590
832 21131508960441890542
833 21284792139797020513
834 21439000771959263232
835 21594139321519870172
836 21750212269204339166
837 21907224111911238679
838 22065179362751078736
839 22224082551085228506
840 22383938222564880542
841 22544750939170061677
842 22706525279248690576
843 22869265837555681944
844 23032977225292097390
845 23197664070144342947
846 23363331016323413248
847 23529982724604182358
848 23697623872364741262
849 23866259153625782009
850 24035893279090028512
851 24206530976181714004
852 24378176989086105150
853 24550836078789072815
854 24724513023116709488
855 24899212616774993362
856 25074939671389499070
857 25251699015545155077
858 25429495494826047728
859 25608333971855271952
860 25788219326334828622
861 25969156455085568571
862 26151150272087183264
863 26334205708518242126
864 26518327712796276526
865 26703521250617910417
866 26889791304999037632
867 27077142876315045836
868 27265580982341087134
869 27455110658292395335
870 27645736956864649872
871 27837464948274386378
872 28030299720299453918
873 28224246378319518877
874 28419310045356615504
875 28615495862115743112
876 28812808987025509934
877 29011254596278823635
878 29210837883873628480
879 29411564061653689158
880 29613438359349421262
881 29816466024618768425
882 30020652323088126112
883 30226002538393312068
884 30432521972220583422
885 30640215944347700447
886 30849089792685036976
887 31059148873316737474
888 31270398560541920766
889 31482844246915930421
890 31696491343291631792
891 31911345278860755712
892 32127411501195288846
893 32344695476288910699
894 32563202688598477280
895 32782938641085551422
896 33003908855257979758
897 33226118871211516353
898 33449574247671492992
899 33674280562034536124
900 33900243410410330462
901 34127468407663429239
902 34355961187455111120
903 34585727402285283770
904 34816772723534434078
905 35049102841505625037
906 35282723465466539280
907 35517640323691569272
908 35753859163503954158
909 35991385751317963267
910 36230225872681126272
911 36470385332316510006
912 36711869954165041934
913 36954685581427880281
914 37198838076608830816
915 37444333321556810292
916 37691177217508356542
917 37939375685130185231
918 38188934664561793264
919 38439860115458108850
920 38692158017032188222
921 38945834368097959013
922 39200895187113010288
923 39457346512221429232
924 39715194401296684494
925 39974444931984556187
926 40235104201746112544
927 40497178327900733230
928 40760673447669179310
929 41025595718216709873
930 41291951316696245312
931 41559746440291577260
932 41828987306260625182
933 42099680151978739623
934 42371831234982052112
935 42645446833010871722
936 42920533244053128286
937 43197096786387862269
938 43475143798628761296
939 43754680639767743336
940 44035713689218586542
941 44318249346860605747
942 44602294033082375616
943 44887854188825500454
944 45174936275628430670
945 45463546775670325897
946 45753692191814964768
947 46045379047654701348
948 46338613887554468222
949 46633403276695826239
950 46929753801121060912
951 47227672067777325474
952 47527164704560830590
953 47828238360361080725
954 48130899705105157168
955 48435155429802047712
956 48741012246587022990
957 49048476888766059467
958 49357556110860309088
959 49668256688650615582
960 49980585419222077422
961 50294549121008657441
962 50610154633837839104
963 50927408818975329436
964 51246318559169808606
965 51566890758697726167
966 51889132343408143952
967 52213050260767625626
968 52538651479905172894
969 52865942991657208365
970 53194931808612605072
971 53525624965157762648
972 53858029517521730158
973 54192152543821375587
974 54528001144106601984
975 54865582440405610262
976 55204903576770208654
977 55545971719321168825
978 55888794056293628640
979 56233377798082541588
980 56579730177288172862
981 56927858448761642095
982 57277769889650512752
983 57629471799444428178
984 57982971500020794302
985 58338276335690508997
986 58695393673243738096
987 59054330901995738064
988 59415095433832725326
989 59777694703257792251
990 60142136167436869792
991 60508427306244736782
992 60876575622311075886
993 61246588641066576209
994 61618473910789082560
995 61992239002649791372
996 62367891510759493278
997 62745439052214862343
998 63124889267144791952
999 63506249818756777354
1000 63889528393383344862