1 1
2 12
3 143
4 770
5 3368
6 12632
7 38566
8 98968
9 222351
10 450682
11 843169
12 1479116
13 2460912
14 3917228
15 6006056
16 8917888
17 12878847
18 18153806
19 25049515
20 33917724
21 45158308
22 59222392
23 76615476
24 97900560
25 123701269
26 154704978
27 191665937
28 235408396
29 286829730
30 346903564
31 416682898
32 497303232
33 589985691
34 696040150
35 816868359
36 953967068
37 1108931152
38 1283456736
39 1479344320
40 1698501904
41 1942948113
42 2214815322
43 2516352781
44 2849929740
45 3218038574
46 3623297908
47 4068455742
48 4556392576
49 5090124535
50 5672806494
51 6307735203
52 6998352412
53 7748247996
54 8561163080
55 9440993164
56 10391791248
57 11417770957
58 12523309666
59 13712951625
60 14991411084
61 16363575418
62 17834508252
63 19409452586
64 21093833920
65 22893263379
66 24813540838
67 26860658047
68 29040801756
69 31360356840
70 33825909424
71 36444250008
72 39222376592
73 42167497801
74 45287036010
75 48588630469
76 52080140428
77 55769648262
78 59665462596
79 63776121430
80 68110395264
81 72677290223
82 77486051182
83 82546164891
84 87867363100
85 93459625684
86 99333183768
87 105498522852
88 111966385936
89 118747776645
90 125853962354
91 133296477313
92 141087125772
93 149237985106
94 157761408940
95 166670030274
96 175976764608
97 185694813067
98 195837665526
99 206419103735
100 217453204444
101 228954342528
102 240937194112
103 253416739696
104 266408267280
105 279927375489
106 293989976698
107 308612300157
108 323810895116
109 339602633950
110 356004715284
111 373034667118
112 390710349952
113 409049959911
114 428072031870
115 447795442579
116 468239413788
117 489423515372
118 511367668456
119 534092148540
120 557617588624
121 581964982333
122 607155687042
123 633211427001
124 660154296460
125 688006762794
126 716791669628
127 746532239962
128 777252079296
129 808975178755
130 841725918214
131 875529069423
132 910409799132
133 946393672216
134 983506654800
135 1021775117384
136 1061225837968
137 1101886005177
138 1143783221386
139 1186945505845
140 1231401297804
141 1277179459638
142 1324309279972
143 1372820476806
144 1422743200640
145 1474108037599
146 1526946012558
147 1581288592267
148 1637167688476
149 1694615661060
150 1753665321144
151 1814349934228
152 1876703223312
153 1940759372021
154 2006553027730
155 2074119304689
156 2143493787148
157 2214712532482
158 2287812074316
159 2362829425650
160 2439802081984
161 2518768024443
162 2599765722902
163 2682834139111
164 2768012729820
165 2855341449904
166 2944860755488
167 3036611607072
168 3130635472656
169 3226974330865
170 3325670674074
171 3426767511533
172 3530308372492
173 3636337309326
174 3744898900660
175 3856038254494
176 3969801011328
177 4086233347287
178 4205381977246
179 4327294157955
180 4452017691164
181 4579600926748
182 4710092765832
183 4843542663916
184 4980000634000
185 5119517249709
186 5262143648418
187 5407931534377
188 5556933181836
189 5709201438170
190 5864789727004
191 6023752051338
192 6186142996672
193 6352017734131
194 6521432023590
195 6694442216799
196 6871105260508
197 7051478699592
198 7235620680176
199 7423589952760
200 7615445875344
201 7811248416553
202 8011058158762
203 8214936301221
204 8422944663180
205 8635145687014
206 8851602441348
207 9072378624182
208 9297538566016
209 9527147232975
210 9761270229934
211 9999973803643
212 10243324845852
213 10491390896436
214 10744240146520
215 11001941441604
216 11264564284688
217 11532178839397
218 11804855933106
219 12082667060065
220 12365684384524
221 12653980743858
222 12947629651692
223 13246705301026
224 13551282567360
225 13861437011819
226 14177244884278
227 14498783126487
228 14826129375196
229 15159361965280
230 15498559932864
231 15843803018448
232 16195171670032
233 16552747046241
234 16916611019450
235 17286846178909
236 17663535833868
237 18046764016702
238 18436615486036
239 18833175729870
240 19236530968704
241 19646768158663
242 20063974994622
243 20488239913331
244 20919652096540
245 21358301474124
246 21804278727208
247 22257675291292
248 22718583359376
249 23187095885085
250 23663306585794
251 24147309945753
252 24639201219212
253 25139076433546
254 25647032392380
255 26163166678714
256 26687577658048
257 27220364481507
258 27761627088966
259 28311466212175
260 28869983377884
261 29437280910968
262 30013461937552
263 30598630388136
264 31192891000720
265 31796349323929
266 32409111720138
267 33031285368597
268 33662978268556
269 34304299242390
270 34955357938724
271 35616264835558
272 36287131243392
273 36968069308351
274 37659192015310
275 38360613191019
276 39072447507228
277 39794810483812
278 40527818491896
279 41271588756980
280 42026239362064
281 42791889250773
282 43568658230482
283 44356666975441
284 45156037029900
285 45966890811234
286 46789351613068
287 47623543608402
288 48469591852736
289 49327622287195
290 50197761741654
291 51080137937863
292 51974879492572
293 52882115920656
294 53801977638240
295 54734595965824
296 55680103131408
297 56638632273617
298 57610317444826
299 58595293614285
300 59593696671244
301 60605663428078
302 61631331623412
303 62670839925246
304 63724327934080
305 64791936186039
306 65873806155998
307 66970080260707
308 68080901861916
309 69206415269500
310 70346765744584
311 71502099502668
312 72672563716752
313 73858306520461
314 75059477011170
315 76276225253129
316 77508702280588
317 78757060100922
318 80021451697756
319 81302031034090
320 82598953055424
321 83912373692883
322 85242449866342
323 86589339487551
324 87953201463260
325 89334195698344
326 90732483098928
327 92148225575512
328 93581586046096
329 95032728439305
330 96501817697514
331 97989019779973
332 99494501665932
333 101018431357766
334 102560977884100
335 104122311302934
336 105702602704768
337 107302024215727
338 108920749000686
339 110558951266395
340 112216806264604
341 113894490295188
342 115592180709272
343 117310055912356
344 119048295367440
345 120807079598149
346 122586590191858
347 124387009802817
348 126208522155276
349 128051312046610
350 129915565350444
351 131801469019778
352 133709211090112
353 135638980682571
354 137590968007030
355 139565364365239
356 141562362153948
357 143582154868032
358 145624937103616
359 147690904561200
360 149780254048784
361 151893183484993
362 154029891902202
363 156190579449661
364 158375447396620
365 160584698135454
366 162818535184788
367 165077163192622
368 167360787939456
369 169669616341415
370 172003856453374
371 174363717472083
372 176749409739292
373 179161144744876
374 181599135129960
375 184063594690044
376 186554738378128
377 189072782307837
378 191617943756546
379 194190441168505
380 196790494157964
381 199418323512298
382 202074151195132
383 204758200349466
384 207470695300800
385 210211861560259
386 212981925827718
387 215781115994927
388 218609661148636
389 221467791573720
390 224355738756304
391 227273735386888
392 230222015363472
393 233200813794681
394 236210367002890
395 239250912527349
396 242322689127308
397 245425936785142
398 248560896709476
399 251727811338310
400 254926924342144
401 258158480627103
402 261422726338062
403 264719908861771
404 268050276829980
405 271414080122564
406 274811569870648
407 278242998459732
408 281708619532816
409 285208687993525
410 288743460009234
411 292313193014193
412 295918145712652
413 299558578081986
414 303234751375820
415 306946928127154
416 310695372151488
417 314480348549947
418 318302123712406
419 322160965320615
420 326057142351324
421 329990925079408
422 333962585080992
423 337972395236576
424 342020629734160
425 346107564072369
426 350233475063578
427 354398640837037
428 358603340841996
429 362847855850830
430 367132467962164
431 371457460603998
432 375823118536832
433 380229727856791
434 384677575998750
435 389166951739459
436 393698145200668
437 398271447852252
438 402887152515336
439 407545553365420
440 412246945935504
441 416991627119213
442 421779895173922
443 426612049723881
444 431488391763340
445 436409223659674
446 441374849156508
447 446385573376842
448 451441702826176
449 456543545395635
450 461691410365094
451 466885608406303
452 472126451586012
453 477414253369096
454 482749328621680
455 488131993614264
456 493562566024848
457 499041364942057
458 504568710868266
459 510144925722725
460 515770332844684
461 521445256996518
462 527170024366852
463 532944962573686
464 538770400667520
465 544646669134479
466 550574099899438
467 556553026329147
468 562583783235356
469 568666706877940
470 574802134968024
471 580990406671108
472 587231862610192
473 593526844868901
474 599875696994610
475 606278764001569
476 612736392374028
477 619248930069362
478 625816726521196
479 632440132642530
480 639119500828864
481 645855184961323
482 652647540409782
483 659496924035991
484 666403694196700
485 673368210746784
486 680390835042368
487 687471929943952
488 694611859819536
489 701810990547745
490 709069689520954
491 716388325648413
492 723767269359372
493 731206892606206
494 738707568867540
495 746269673151374
496 753893581998208
497 761579673484167
498 769328327224126
499 777139924374835
500 785014847638044
501 792953481263628
502 800956211052712
503 809023424360796
504 817155510100880
505 825352858746589
506 833615862335298
507 841944914471257
508 850340410328716
509 858802746655050
510 867332321773884
511 875929535588218
512 884594789583552
513 893328486831011
514 902131031990470
515 911002831313679
516 919944292647388
517 928955825436472
518 938037840727056
519 947190751169640
520 956414971022224
521 965710916153433
522 975079004045642
523 984519653798101
524 994033286130060
525 1003620323383894
526 1013281189528228
527 1023016310161062
528 1032826112512896
529 1042711025449855
530 1052671479476814
531 1062707906740523
532 1072820741032732
533 1083010417793316
534 1093277374113400
535 1103622048738484
536 1114044882071568
537 1124546316176277
538 1135126794779986
539 1145786763276945
540 1156526668731404
541 1167346959880738
542 1178248087138572
543 1189230502597906
544 1200294660034240
545 1211441014908699
546 1222670024371158
547 1233982147263367
548 1245377844122076
549 1256857577182160
550 1268421810379744
551 1280071009355328
552 1291805641456912
553 1303626175743121
554 1315533082986330
555 1327526835675789
556 1339607908020748
557 1351776775953582
558 1364033917132916
559 1376379810946750
560 1388814938515584
561 1401339782695543
562 1413954828081502
563 1426660561010211
564 1439457469563420
565 1452346043571004
566 1465326774614088
567 1478400156028172
568 1491566682906256
569 1504826852101965
570 1518181162232674
571 1531630113682633
572 1545174208606092
573 1558813950930426
574 1572549846359260
575 1586382402375594
576 1600312128244928
577 1614339535018387
578 1628465135535846
579 1642689444429055
580 1657012978124764
581 1671436254847848
582 1685959794624432
583 1700584119285016
584 1715309752467600
585 1730137219620809
586 1745067048007018
587 1760099766705477
588 1775235906615436
589 1790476000459270
590 1805820582785604
591 1821270189972438
592 1836825360230272
593 1852486633605231
594 1868254551982190
595 1884129659087899
596 1900112500494108
597 1916203623620692
598 1932403577738776
599 1948712913973860
600 1965132185308944
601 1981661946587653
602 1998302754517362
603 2015055167672321
604 2031919746496780
605 2048897053308114
606 2065987652299948
607 2083192109545282
608 2100510992999616
609 2117944872504075
610 2135494319788534
611 2153159908474743
612 2170942214079452
613 2188841814017536
614 2206859287605120
615 2224995216062704
616 2243250182518288
617 2261624772010497
618 2280119571491706
619 2298735169831165
620 2317472157818124
621 2336331128164958
622 2355312675510292
623 2374417396422126
624 2393645889400960
625 2412998754882919
626 2432476595242878
627 2452080014797587
628 2471809619808796
629 2491666018486380
630 2511649820991464
631 2531761639439548
632 2552002087903632
633 2572371782417341
634 2592871340978050
635 2613501383550009
636 2634262532067468
637 2655155410437802
638 2676180644544636
639 2697338862250970
640 2718630693402304
641 2740056769829763
642 2761617725353222
643 2783314195784431
644 2805146818930140
645 2827116234595224
646 2849223084585808
647 2871468012712392
648 2893851664792976
649 2916374688656185
650 2939037734144394
651 2961841453116853
652 2984786499452812
653 3007873529054646
654 3031103199850980
655 3054476171799814
656 3077993106891648
657 3101654669152607
658 3125461524647566
659 3149414341483275
660 3173513789811484
661 3197760541832068
662 3222155271796152
663 3246698656009236
664 3271391372834320
665 3296234102695029
666 3321227528078738
667 3346372333539697
668 3371669205702156
669 3397118833263490
670 3422721906997324
671 3448479119756658
672 3474391166476992
673 3500458744179451
674 3526682551973910
675 3553063291062119
676 3579601664740828
677 3606298378404912
678 3633154139550496
679 3660169657778080
680 3687345644795664
681 3714682814421873
682 3742181882589082
683 3769843567346541
684 3797668588863500
685 3825657669432334
686 3853811533471668
687 3882130907529502
688 3910616520286336
689 3939269102558295
690 3968089387300254
691 3997078109608963
692 4026236006726172
693 4055563818041756
694 4085062285096840
695 4114732151586924
696 4144574163365008
697 4174589068444717
698 4204777617003426
699 4235140561385385
700 4265678656104844
701 4296392657849178
702 4327283325482012
703 4358351420046346
704 4389597704767680
705 4421022945057139
706 4452627908514598
707 4484413364931807
708 4516380086295516
709 4548528846790600
710 4580860422803184
711 4613375592923768
712 4646075137950352
713 4678959840891561
714 4712030486969770
715 4745287863624229
716 4778732760514188
717 4812365969522022
718 4846188284756356
719 4880200502555190
720 4914403421489024
721 4948797842363983
722 4983384568224942
723 5018164404358651
724 5053138158296860
725 5088306639819444
726 5123670660957528
727 5159231035996612
728 5194988581479696
729 5230944116210405
730 5267098461256114
731 5303452439951073
732 5340006877899532
733 5376762602978866
734 5413720445342700
735 5450881237424034
736 5488245813938368
737 5525815011886827
738 5563589670559286
739 5601570631537495
740 5639758738698204
741 5678154838216288
742 5716759778567872
743 5755574410533456
744 5794599587201040
745 5833836163969249
746 5873284998550458
747 5912946950973917
748 5952822883588876
749 5992913661067710
750 6033220150409044
751 6073743220940878
752 6114483744323712
753 6155442594553671
754 6196620647965630
755 6238018783236339
756 6279637881387548
757 6321478825789132
758 6363542502162216
759 6405829798582300
760 6448341605482384
761 6491078815656093
762 6534042324260802
763 6577233028820761
764 6620651829230220
765 6664299627756554
766 6708177329043388
767 6752285840113722
768 6796626070373056
769 6841198931612515
770 6886005338011974
771 6931046206143183
772 6976322454972892
773 7021835005865976
774 7067584782588560
775 7113572711311144
776 7159799720611728
777 7206266741478937
778 7252974707315146
779 7299924553939605
780 7347117219591564
781 7394553644933398
782 7442234773053732
783 7490161549470566
784 7538334922134400
785 7586755841431359
786 7635425260186318
787 7684344133666027
788 7733513419582236
789 7782934078094820
790 7832607071814904
791 7882533365807988
792 7932713927597072
793 7983149727165781
794 8033841736961490
795 8084790931898449
796 8135998289360908
797 8187464789206242
798 8239191413768076
799 8291179147859410
800 8343428978775744
801 8395941896298203
802 8448718892696662
803 8501760962732871
804 8555069103663580
805 8608644315243664
806 8662487599729248
807 8716599961880832
808 8770982408966416
809 8825635950764625
810 8880561599567834
811 8935760370185293
812 8991233279946252
813 9046981348703086
814 9103005598834420
815 9159307055248254
816 9215886745385088
817 9272745699221047
818 9329884949271006
819 9387305530591715
820 9445008480784924
821 9502994840000508
822 9561265650939592
823 9619821958857676
824 9678664811567760
825 9737795259443469
826 9797214355422178
827 9856923155008137
828 9916922716275596
829 9977214099871930
830 10037798369020764
831 10098676589525098
832 10159849829770432
833 10221319160727891
834 10283085655957350
835 10345150391610559
836 10407514446434268
837 10470178901773352
838 10533144841573936
839 10596413352386520
840 10659985523369104
841 10723862446290313
842 10788045215532522
843 10852534928094981
844 10917332683596940
845 10982439584280774
846 11047856735015108
847 11113585243297942
848 11179626219259776
849 11245980775666735
850 11312650027923694
851 11379635094077403
852 11446937094819612
853 11514557153490196
854 11582496396080280
855 11650755951235364
856 11719336950258448
857 11788240527113157
858 11857467818426866
859 11927019963493825
860 11996898104278284
861 12067103385417618
862 12137636954225452
863 12208499960694786
864 12279693557501120
865 12351218900005579
866 12423077146258038
867 12495269457000247
868 12567796995668956
869 12640660928399040
870 12713862424026624
871 12787402654092208
872 12861282792843792
873 12935504017240001
874 13010067506953210
875 13084974444372669
876 13160226014607628
877 13235823405490462
878 13311767807579796
879 13388060414163630
880 13464702421262464
881 13541695027632423
882 13619039434768382
883 13696736846907091
884 13774788471030300
885 13853195516867884
886 13931959196900968
887 14011080726365052
888 14090561323253136
889 14170402208318845
890 14250604605079554
891 14331169739819513
892 14412098841592972
893 14493393142227306
894 14575053876326140
895 14657082281272474
896 14739479597231808
897 14822247067155267
898 14905385936782726
899 14988897454645935
900 15072782872071644
901 15157043443184728
902 15241680424911312
903 15326695076981896
904 15412088661934480
905 15497862445117689
906 15584017694693898
907 15670555681642357
908 15757477679762316
909 15844784965676150
910 15932478818832484
911 16020560521509318
912 16109031358817152
913 16197892618702111
914 16287145591949070
915 16376791572184779
916 16466831855880988
917 16557267742357572
918 16648100533785656
919 16739331535190740
920 16830962054455824
921 16922993402324533
922 17015426892404242
923 17108263841169201
924 17201505567963660
925 17295153395004994
926 17389208647386828
927 17483672653082162
928 17578546742946496
929 17673832250720955
930 17769530513035414
931 17865642869411623
932 17962170662266332
933 18059115236914416
934 18156477941572000
935 18254260127359584
936 18352463148305168
937 18451088361347377
938 18550137126338586
939 18649610806048045
940 18749510766165004
941 18849838375301838
942 18950595004997172
943 19051782029719006
944 19153400826867840
945 19255452776779799
946 19357939262729758
947 19460861670934467
948 19564221390555676
949 19668019813703260
950 19772258335438344
951 19876938353776428
952 19982061269690512
953 20087628487114221
954 20193641412944930
955 20300101457046889
956 20407010032254348
957 20514368554374682
958 20622178442191516
959 20730441117467850
960 20839158004949184
961 20948330532366643
962 21057960130440102
963 21168048232881311
964 21278596276397020
965 21389605700692104
966 21501077948472688
967 21613014465449272
968 21725416700339856
969 21838286104873065
970 21951624133791274
971 22065432244853733
972 22179711898839692
973 22294464559551526
974 22409691693817860
975 22525394771496694
976 22641575265478528
977 22758234651689487
978 22875374409094446
979 22992996019700155
980 23111100968558364
981 23229690743768948
982 23348766836483032
983 23468330740906116
984 23588383954301200
985 23708927976991909
986 23829964312365618
987 23951494466876577
988 24073519950049036
989 24196042274480370
990 24319062955844204
991 24442583512893538
992 24566605467463872
993 24691130344476331
994 24816159671940790
995 24941694980958999
996 25067737805727708
997 25194289683541792
998 25321352154797376
999 25448926762994960
1000 25577015054742544