4 1
5 3
6 8
7 21
8 54
9 133
10 309
11 674
12 1383
13 2683
14 4950
15 8735
16 14820
17 24285
18 38587
19 59652
20 89981
21 132771
22 192052
23 272841
24 381314
25 524997
26 712977
27 956134
28 1267395
29 1662011
30 2157858
31 2775763
32 3539856
33 4477949
34 5621943
35 7008264
36 8678329
37 10679043
38 13063328
39 15890685
40 19227790
41 23149125
42 27737645
43 33085482
44 39294687
45 46478011
46 54759726
47 64276487
48 75178236
49 87629149
50 101808627
51 117912332
52 136153269
53 156762915
54 179992396
55 206113713
56 235421018
57 268231941
58 304888969
59 345760878
60 391244219
61 441764859
62 497779578
63 559777723
64 628282920
65 703854845
66 787091055
67 878628880
68 979147377
69 1089369347
70 1210063416
71 1342046181
72 1486184422
73 1643397381
74 1814659109
75 2001000882
76 2203513687
77 2423350779
78 2661730310
79 2919938031
80 3199330068
81 3501335773
82 3827460651
83 4179289364
84 4558488813
85 4966811299
86 5406097764
87 5878281113
88 6385389618
89 6929550405
90 7512993025
91 8138053110
92 8807176115
93 9522921147
94 10287964882
95 11105105571
96 11977267136
97 12907503357
98 13899002151
99 14955089944
100 16079236137
101 17275057667
102 18546323664
103 19896960205
104 21331055166
105 22852863173
106 24466810653
107 26177500986
108 27989719759
109 29908440123
110 31938828254
111 34086248919
112 36356271148
113 38754674013
114 41287452515
115 43960823580
116 46781232165
117 49755357475
118 52890119292
119 56192684417
120 59670473226
121 63331166341
122 67182711417
123 71233330046
124 75491524779
125 79966086267
126 84666100522
127 89600956299
128 94780352600
129 100214306301
130 105913159903
131 111887589408
132 118148612321
133 124707595779
134 131576264808
135 138766710709
136 146291399574
137 154163180933
138 162395296533
139 171001389250
140 179995512135
141 189392137595
142 199206166710
143 209452938687
144 220148240452
145 231308316381
146 242949878171
147 255090114852
148 267746702941
149 280937816739
150 294682138772
151 308998870377
152 323907742434
153 339429026245
154 355583544561
155 372392682758
156 389878400163
157 408063241531
158 426970348674
159 446623472243
160 467046983664
161 488265887229
162 510305832343
163 533193125928
164 556954744985
165 581618349315
166 607212294400
167 633765644445
168 661308185582
169 689870439237
170 719483675661
171 750179927626
172 781992004287
173 814953505211
174 849098834574
175 884463215527
176 921082704732
177 958994207069
178 998235490515
179 1038845201196
180 1080862878613
181 1124328971043
182 1169284851116
183 1215772831569
184 1263836181178
185 1313519140869
186 1364866940009
187 1417925812878
188 1472743015323
189 1529366841595
190 1587846641370
191 1648232836955
192 1710576940680
193 1774931572477
194 1841350477647
195 1909888544816
196 1980601824081
197 2053547545347
198 2128784136856
199 2206371243909
200 2286369747782
201 2368841784837
202 2453850765829
203 2541461395410
204 2631739691831
205 2724753006843
206 2820570045798
207 2919260887951
208 3020897006964
209 3125551291613
210 3233298066699
211 3344213114164
212 3458373694413
213 3575858567843
214 3696748016580
215 3821123866425
216 3949069509010
217 4080669924165
218 4216011702497
219 4355183068182
220 4498273901971
221 4645375764411
222 4796581919282
223 4951987357251
224 5111688819744
225 5275784823037
226 5444375682567
227 5617563537464
228 5795452375305
229 5978148057091
230 6165758342448
231 6358392915053
232 6556163408286
233 6759183431109
234 6967568594173
235 7181436536154
236 7400906950319
237 7626101611323
238 7857144402238
239 8094161341815
240 8337280611980
241 8586632585565
242 8842349854275
243 9104567256892
244 9373421907717
245 9649053225251
246 9931602961116
247 10221215229217
248 10518036535146
249 10822215805829
250 11133904419417
251 11453256235422
252 11780427625099
253 12115577502075
254 12458867353226
255 12810461269803
256 13170525978808
257 13539230874621
258 13916748050879
259 14303252332608
260 14698921308609
261 15103935364099
262 15518477713608
263 15942734434133
264 16376894498550
265 16821149809285
266 17275695232245
267 17740728631010
268 18216450901287
269 18703066005627
270 19200781008406
271 19709806111071
272 20230354687652
273 20762643320541
274 21306891836539
275 21863323343172
276 22432164265277
277 23013644381859
278 23607996863220
279 24215458308361
280 24836268782658
281 25470671855813
282 26118914640081
283 26781247828774
284 27457925735043
285 28149206330939
286 28855351286754
287 29576626010643
288 30313299688528
289 31065645324285
290 31833939780215
291 32618463817800
292 33419502138745
293 34237343426307
294 35072280386912
295 35924609792061
296 36794632520526
297 37682653600837
298 38588982254061
299 39513931936874
300 40457820384927
301 41420969656507
302 42403706176494
303 43406360780615
304 44429268759996
305 45472769906013
306 46537208555443
307 47622933635916
308 48730298711669
309 49859662029603
310 51011386565644
311 52185840071409
312 53383395121178
313 54604429159173
314 55849324547145
315 57118468612270
316 58412253695355
317 59731077199355
318 61075341638202
319 62445454685947
320 63841829226216
321 65264883401981
322 66715040665647
323 68192729829456
324 69698385116209
325 71232446210307
326 72795358309112
327 74387572174629
328 76009544185510
329 77661736389381
330 79344616555493
331 81058658227698
332 82804340777751
333 84582149458939
334 86392575460038
335 88236115959599
336 90113274180564
337 92024559445213
338 93970487230443
339 95951579223380
340 97968363377325
341 100021373968035
342 102111151650340
343 104238243515097
344 106403203146482
345 108606590679621
346 110848972858561
347 113130923094582
348 115453021524851
349 117815855071419
350 120220017500562
351 122666109482467
352 125154738651264
353 127686519665405
354 130262074268391
355 132882031349848
356 135547027006953
357 138257704606211
358 141014714845584
359 143818715816973
360 146670373069054
361 149570359670469
362 152519356273373
363 155518051177338
364 158567140393615
365 161667327709755
366 164819324754590
367 168023851063575
368 171281634144492
369 174593409543517
370 177959920911651
371 181381920071516
372 184860167084517
373 188395430318371
374 191988486515004
375 195640120858817
376 199351127045322
377 203122307350149
378 206954472698425
379 210848442734526
380 214805045892203
381 218825119465083
382 222909509677546
383 227059071755979
384 231274670000408
385 235557177856509
386 239907477987999
387 244326462349408
388 248815032259233
389 253374098473475
390 258004581259560
391 262707410470645
392 267483525620310
393 272333875957637
394 277259420542677
395 282261128322306
396 287339978206471
397 292496959144827
398 297733070203766
399 303049320643839
400 308446729997572
401 313926328147677
402 319489155405659
403 325136262590820
404 330868711109661
405 336687573035683
406 342593931189588
407 348588879219881
408 354673521683874
409 360848974129093
410 367116363175089
411 373476826595654
412 379931513401443
413 386481583923003
414 393128209894210
415 399872574536115
416 406715872641200
417 413659310658045
418 420704106776407
419 427851491012712
420 435102705295961
421 442459003554051
422 449921651800512
423 457491928221661
424 465171123264174
425 472960539723077
426 480861492830157
427 488875310342794
428 497003332633215
429 505246912778171
430 513607416649038
431 522086223002343
432 530684723570716
433 539404323154269
434 548246439712403
435 557212504456044
436 566303961940309
437 575522270157603
438 584868900631148
439 594345338508945
440 603953082658170
441 613693645760005
442 623568554404905
443 633579349188302
444 643727584806747
445 654014830154491
446 664442668420506
447 675012697185947
448 685726528522056
449 696585789088509
450 707592120232207
451 718747178086512
452 730052633670929
453 741510172991235
454 753121497140056
455 764888322397893
456 776812380334598
457 788895417911301
458 801139197582789
459 813545497400338
460 826116111114999
461 838852848281339
462 851757534361638
463 864832010830543
464 878078135280180
465 891497781525725
466 905092839711435
467 918865216417140
468 932816834765197
469 946949634527907
470 961265572235396
471 975766621283961
472 990454772044882
473 1005332031973701
474 1020400425719969
475 1035661995237462
476 1051118799894867
477 1066772916586939
478 1082626439846130
479 1098681481954691
480 1114940173057248
481 1131404661273853
482 1148077112813511
483 1164959712088184
484 1182054661827273
485 1199364183192579
486 1216890515893744
487 1234635918304173
488 1252602667577438
489 1270793059764165
490 1289209409929405
491 1307854052270490
492 1326729340235375
493 1345837646641467
494 1365181363794942
495 1384762903610551
496 1404584697731916
497 1424649197652317
498 1444958874835971
499 1465516220839804
500 1486323747435717
501 1507383986733347
502 1528699491303324
503 1550272834301025
504 1572106609590826
505 1594203431870853
506 1616565936798233
507 1639196781114846
508 1662098642773579
509 1685274221065083
510 1708726236745034
511 1732457432161899
512 1756470571385208
513 1780768440334333
514 1805353846907775
515 1830229621112960
516 1855398615196545
517 1880863703775235
518 1906627783967112
519 1932693775523477
520 1959064620961206
521 1985743285695621
522 2012732758173877
523 2040036050008866
524 2067656196113639
525 2095596254836347
526 2123859308095702
527 2152448461516959
528 2181366844568420
529 2210617610698461
530 2240203937473083
531 2270129026713988
532 2300396104637181
533 2331008421992099
534 2361969254201268
535 2393281901500489
536 2424949689079554
537 2456975967223493
538 2489364111454353
539 2522117522673510
540 2555239627304515
541 2588733877436475
542 2622603750967970
543 2656852751751507
544 2691484409738512
545 2726502281124861
546 2761909948496951
547 2797711020978312
548 2833909134376761
549 2870507951332099
550 2907511161464352
551 2944922481522557
552 2982745655534094
553 3020984454954565
554 3059642678818221
555 3098724153888938
556 3138232734811743
557 3178172304264891
558 3218546773112494
559 3259360080557703
560 3300616194296444
561 3342319110671709
562 3384472854828403
563 3427081480868748
564 3470149072008245
565 3513679740732195
566 3557677628952780
567 3602146908166705
568 3647091779613402
569 3692516474433797
570 3738425253829641
571 3784822409223406
572 3831712262418747
573 3879099165761531
574 3926987502301434
575 3975381685954107
576 4024286161663912
577 4073705405567229
578 4123643925156335
579 4174106259443856
580 4225096979127793
581 4276620686757123
582 4328682016897976
583 4381285636300389
584 4434436244065638
585 4488138571814149
586 4542397383853989
587 4597217477349938
588 4652603682493143
589 4708560862671355
590 4765093914639750
591 4822207768692335
592 4879907388833940
593 4938197772952797
594 4997083952993707
595 5056570995131796
596 5116663999946861
597 5177368102598307
598 5238688473000676
599 5300630315999769
600 5363198871549362
601 5426399414888517
602 5490237256719489
603 5554717743386230
604 5619846257053491
605 5685628215886523
606 5752069074231378
607 5819174322795811
608 5886949488830784
609 5955400136312573
610 6024531866125479
611 6094350316245144
612 6164861161922473
613 6236070115868163
614 6307982928437840
615 6380605387817805
616 6453943320211390
617 6528002590025925
618 6602789100060317
619 6678308791693242
620 6754567645071951
621 6831571679301691
622 6909326952635742
623 6987839562666071
624 7067115646514604
625 7147161381025117
626 7227982982955747
627 7309586709172124
628 7391978856841125
629 7475165763625251
630 7559153807877628
631 7643949408837633
632 7729559026827146
633 7815989163447429
634 7903246361776633
635 7991337206567934
636 8080268324448299
637 8170046384117883
638 8260678096550058
639 8352170215192075
640 8444529536166360
641 8537762898472445
642 8631877184189535
643 8726879318679712
644 8822776270791777
645 8919575053065731
646 9017282721937896
647 9115906377946677
648 9215453165938966
649 9315930275277189
650 9417344940046997
651 9519704439265602
652 9623016097090759
653 9727287283030395
654 9832525412152886
655 9938737945297983
656 10045932389288388
657 10154116297141981
658 10263297268284699
659 10373482948764068
660 10484681031463389
661 10596899256316579
662 10710145410523668
663 10824427328766953
664 10939752893427810
665 11056130034804165
666 11173566731328625
667 11292071009787270
668 11411650945539107
669 11532314662736187
670 11654070334544386
671 11776926183364851
672 11900890481056112
673 12025971549156861
674 12152177759109399
675 12279517532483752
676 12407999341202457
677 12537631707766019
678 12668423205479040
679 12800382458677021
680 12933518142953838
681 13067838985389893
682 13203353764780941
683 13340071311867594
684 13478000509565503
685 13617150293196219
686 13757529650718734
687 13899147622961703
688 14042013303856348
689 14186135840670045
690 14331524434240595
691 14478188339211180
692 14626136864266005
693 14775379372366627
694 14925925280988972
695 15077784062361041
696 15230965243701306
697 15385478407457797
698 15541333191547881
699 15698539289598734
700 15857106451188507
701 16017044482088187
702 16178363244504154
703 16341072657321435
704 16505182696347656
705 16670703394557693
706 16837644842339023
707 17006017187737776
708 17175830636705489
709 17347095453346563
710 17519821960166424
711 17694020538320389
712 17869701627863238
713 18046875727999493
714 18225553397334405
715 18405745254125650
716 18587461976535735
717 18770714302885115
718 18955513031906022
719 19141869022997007
720 19329793196478196
721 19519296533847261
722 19710390078036107
723 19903084933668276
724 20097392267317069
725 20293323307764387
726 20490889346260292
727 20690101736783289
728 20890971896301330
729 21093511305033541
730 21297731506712673
731 21503644108848278
732 21711260782990611
733 21920593264995259
734 22131653355288498
735 22344452919133379
736 22559003886896544
737 22775318254315773
738 22993408082768263
739 23213285499539640
740 23434962698093705
741 23658451938342915
742 23883765546919600
743 24110915917447917
744 24339915510816542
745 24570776855452101
746 24803512547593341
747 25038135251566042
748 25274657700058671
749 25513092694398779
750 25753453104830142
751 25995751870790647
752 26240002001190924
753 26486216574693725
754 26734408739994051
755 26984591716100028
756 27236778792614533
757 27490983330017571
758 27747218759949404
759 28005498585494433
760 28265836381465834
761 28528245794690949
762 28792740544297433
763 29059334422000158
764 29328041292388875
765 29598875093216635
766 29871849835688970
767 30146979604753835
768 30424278559392312
769 30703760932910077
770 30985441033229631
771 31269333243183296
772 31555452020806977
773 31843811899634691
774 32134427488993864
775 32427313474301397
776 32722484617360502
777 33019955756658309
778 33319741807664245
779 33621857763129186
780 33926318693385383
781 34233139746647163
782 34542336149312406
783 34853923206264799
784 35167916301176868
785 35484330896813789
786 35803182535337979
787 36124486838614468
788 36448259508517053
789 36774516327235235
790 37103273157581940
791 37434545943302025
792 37768350709381570
793 38104703562357957
794 38443620690630737
795 38785118364773286
796 39129212937845251
797 39475920845705787
798 39825258607327586
799 40177242825111699
800 40531890185203152
801 40889217457807357
802 41249241497507319
803 41611979243581640
804 41977447720323321
805 42345664037359363
806 42716645389971168
807 43090409059415741
808 43466972413247694
809 43846352905642053
810 44228568077717869
811 44613635557862634
812 45001573062057503
813 45392398394203323
814 45786129446447470
815 46182784199511495
816 46582380723019580
817 46984937175827805
818 47390471806354227
819 47799002952909772
820 48210549044029941
821 48625128598807331
822 49042760227224972
823 49463462630490481
824 49887254601371034
825 50314155024529157
826 50744182876859337
827 51177357227825454
828 51613697239799035
829 52053222168398331
830 52495951362828218
831 52941904266220923
832 53391100415977576
833 53843559444110589
834 54299301077586863
835 54758345138671824
836 55220711545274289
837 55686420311292163
838 56155491546958968
839 56627945459191205
840 57103802351936550
841 57583082626522885
842 58065806782008165
843 58551995415531122
844 59041669222662807
845 59534848997758971
846 60031555634313286
847 60531810125311407
848 61035633563585876
849 61543047142171869
850 62054072154663787
851 62568729995572692
852 63087042160684589
853 63609030247419555
854 64134715955191716
855 64664121085770073
856 65197267543640178
857 65734177336366661
858 66274872574956609
859 66819375474223798
860 67367708353153779
861 67919893635269819
862 68475953848999698
863 69035911628043363
864 69599789711741440
865 70167610945444605
866 70739398280883815
867 71315174776541400
868 71894963598023017
869 72478788018430467
870 73066671418735376
871 73658637288153741
872 74254709224521342
873 74854910934670021
874 75459266234804829
875 76067799050882042
876 76680533418988047
877 77297493485719099
878 77918703508561950
879 78544187856275351
880 79173971009272428
881 79808077560003933
882 80446532213342371
883 81089359786967004
884 81736585211749733
885 82388233532141859
886 83044329906561724
887 83704899607783233
888 84369968023325258
889 85039560655841925
890 85713703123513785
891 86392421160439870
892 87075740617030635
893 87763687460401787
894 88456287774769002
895 89153567761843531
896 89855553741228696
897 90562272150817277
898 91273749547189791
899 91990012606013664
900 92711088122443297
901 93437003011521027
902 94167784308578984
903 94903459169641845
904 95644054871830486
905 96389598813766533
906 97140118515977813
907 97895641621304706
908 98656195895307399
909 99421809226674043
910 100192509627629814
911 100968325234346879
912 101749284307355268
913 102535415231954653
914 103326746518627035
915 104123306803450340
916 104925124848512925
917 105732229542328995
918 106544649900254932
919 107362415064906537
920 108185554306577186
921 109014097023656901
922 109848072743052337
923 110687511120607686
924 111532441941526499
925 112382895120794427
926 113238900703602882
927 114100488865773619
928 114967689914184240
929 115840534287194621
930 116719052555074263
931 117603275420430568
932 118493233718638041
933 119388958418268419
934 120290480621521728
935 121197831564658269
936 122111042618431534
937 123030145288522053
938 123955171215972173
939 124886152177621770
940 125823120086544895
941 126766106992487355
942 127715145082305230
943 128670266680404327
944 129631504249180572
945 130598890389461341
946 131572457840947731
947 132552239482657772
948 133538268333370581
949 134530577552071459
950 135529200438397932
951 136534170433086737
952 137545521118421754
953 138563286218682885
954 139587499600595881
955 140618195273783118
956 141655407391215323
957 142699170249664251
958 143749518290156314
959 144806486098427163
960 145870108405377224
961 146940420087528189
962 148017456167480463
963 149101251814371568
964 150191842344335505
965 151289263220963075
966 152393550055763160
967 153504738608624965
968 154622864788281222
969 155747964652772357
970 156880074409911621
971 158019230417751186
972 159165469185049207
973 160318827371737851
974 161479341789392294
975 162647049401700687
976 163821987324935092
977 165004192828423389
978 166193703335022155
979 167390556421590516
980 168594789819464973
981 169806441414935203
982 171025549249720836
983 172252151521449209
984 173486286584134098
985 174727992948655429
986 175977309283239969
987 177234274413942998
988 178498927325130963
989 179771307159965115
990 181051453220886130
991 182339404970099715
992 183635202030063200
993 184938884183973117
994 186250491376253767
995 187570063713046776
996 188897641462701641
997 190233265056267267
998 191576975087984496
999 192928812315779629
1000 194288817661758942
1001 195657032212704197
1002 197033497220569149
1003 198418254102977050