3 1
4 3
5 13
6 38
7 97
8 217
9 453
10 868
11 1585
12 2756
13 4606
14 7440
15 11679
16 17849
17 26674
18 39060
19 56144
20 79387
21 110575
22 151904
23 206063
24 276332
25 366561
26 481484
27 626586
28 808431
29 1034636
30 1314242
31 1657500
32 2076601
33 2585262
34 3199504
35 3937370
36 4819788
37 5869993
38 7114928
39 8584354
40 10312345
41 12336555
42 14699852
43 17449157
44 20637831
45 24324066
46 28573424
47 33457410
48 39056216
49 45456710
50 52756184
51 61059735
52 70484235
53 81155919
54 93214638
55 106810683
56 122110329
57 139291867
58 158551452
59 180099367
60 204166244
61 230998360
62 260865472
63 294055113
64 330880825
65 371676712
66 416806148
67 466655134
68 521642979
69 582214425
70 648850832
71 722062585
72 802400868
73 890448623
74 986834692
75 1092223288
76 1207328759
77 1332905366
78 1469762762
79 1618754046
80 1780794041
81 1956845580
82 2147938536
83 2355156440
84 2579656364
85 2822653515
86 3085444384
87 3369389268
88 3675936313
89 4006604393
90 4363008156
91 4746838555
92 5159891663
93 5604046804
94 6081296416
95 6593724564
96 7143537968
97 7733041820
98 8364675120
99 9040983741
100 9764656979
101 10538501025
102 11365476854
103 12248670629
104 13191336473
105 14196863745
106 15268821204
107 16410924717
108 17627082948
109 18921361602
110 20298034608
111 21761544835
112 23316556857
113 24967918126
114 26720713460
115 28580222332
116 30551979499
117 32641728339
118 34855483264
119 37199483539
120 39680257628
121 42304572685
122 45079505724
123 48012388710
124 51110881727
125 54382918576
126 57836782098
127 61481044976
128 65324652601
129 69376859002
130 73647311936
131 78145989350
132 82883286860
133 87869948925
134 93117164624
135 98636493462
136 104439963609
137 110539998263
138 116949516524
139 123681853953
140 130750872535
141 138170875350
142 145956719248
143 154123730102
144 162687818376
145 171665388034
146 181073462024
147 190929584755
148 201251950555
149 212059306755
150 223371085310
151 235207298975
152 247588683705
153 260536587831
154 274073117708
155 288221027523
156 303003868388
157 318445870652
158 334572104672
159 351408355533
160 368981287353
161 387318318660
162 406447790436
163 426398833386
164 447201548595
165 468886866589
166 491486731824
167 515033962429
168 539562438740
169 565106954299
170 591703417972
171 619388696100
172 648200818759
173 678178822618
174 709362961562
175 741794540146
176 775516138809
177 810571437816
178 847005446936
179 884864330116
180 924195639852
181 965048131775
182 1007472014656
183 1051518754792
184 1097241330809
185 1144694038805
186 1193932752188
187 1245014716023
188 1297998823583
189 1352945399784
190 1409916482880
191 1468975608680
192 1530188097632
193 1593620827512
194 1659342538336
195 1727423593401
196 1797936289699
197 1870954619765
198 1946554587846
199 2024813959465
200 2105812596569
201 2189632194685
202 2276356623940
203 2366071667049
204 2458865366468
205 2554827749318
206 2654051194704
207 2756630145447
208 2862661481657
209 2972244233322
210 3085479960404
211 3202472451560
212 3323328125627
213 3448155716343
214 3577066680480
215 3710174883447
216 3847597014348
217 3989452256889
218 4135862727084
219 4286953129330
220 4442851201167
221 4603687370260
222 4769595206498
223 4940711063428
224 5117174554297
225 5299128177798
226 5486717801584
227 5680092288946
228 5879403990092
229 6084808352401
230 6296464436976
231 6514534512330
232 6739184578841
233 6970583963395
234 7208905852044
235 7454326867325
236 7707027627559
237 7967192306698
238 8235009201968
239 8510670294698
240 8794371826616
241 9086313842430
242 9386700794168
243 9695741065359
244 10013647584171
245 10340637348599
246 10676932048718
247 11022757572675
248 11378344658425
249 11743928380371
250 12119748810364
251 12506050505375
252 12903083178084
253 13311101164384
254 13730364124928
255 14161136492305
256 14603688182329
257 15058294042272
258 15525234572228
259 16004795352182
260 16497267795843
261 17002948556385
262 17522140290512
263 18055151065281
264 18602295132740
265 19163892314567
266 19740268810724
267 20331756561744
268 20938694068119
269 21561425753694
270 22200302796138
271 22855682467110
272 23527928998329
273 24217412898340
274 24924511829832
275 25649609927536
276 26393098687148
277 27155376258931
278 27936848373856
279 28737927612732
280 29559034344121
281 30400595994625
282 31263047998940
283 32146833044755
284 33052402061679
285 33980213440572
286 34930734034784
287 35904438380668
288 36901809711504
289 37923339151508
290 38969526770320
291 40040880750325
292 41137918454003
293 42261165592457
294 43411157306006
295 44588437305069
296 45793558993049
297 47027084579385
298 48289586215860
299 49581645110885
300 50903852679620
301 52256809629450
302 53641127154160
303 55057425990411
304 56506337625913
305 57988503357158
306 59504575511988
307 61055216477332
308 62641099967627
309 64262910022363
310 65921342289088
311 67617103022235
312 69350910381116
313 71123493397541
314 72935593321500
315 74787962557374
316 76681366024799
317 78616580096184
318 80594393973170
319 82615608591704
320 84681038048057
321 86791508471250
322 88947859464864
323 91150942980798
324 93401624777292
325 95700783258981
326 98049310986384
327 100448113482046
328 102898110756441
329 105400236115471
330 107955437703212
331 110564677274425
332 113228931790711
333 115949192157822
334 118726464838864
335 121561770592990
336 124456146106088
337 127410642693178
338 130426327984488
339 133504284591339
340 136645611809915
341 139851424288555
342 143122853749662
343 146461047619367
344 149867170806841
345 153342404296111
346 156887946943724
347 160505014071995
348 164194839285476
349 167958673025220
350 171797784444704
351 175713459924885
352 179707004969145
353 183779742719804
354 187933015872548
355 192168185152578
356 196486631290579
357 200889753458277
358 205378971264112
359 209955723190277
360 214621468608564
361 219377686175635
362 224225875912532
363 229167557557948
364 234204272668135
365 239337582971682
366 244569072490298
367 249900345850394
368 255333030469689
369 260868774825360
370 266509250661752
371 272256151260060
372 278111193667628
373 284076116922983
374 290152684353152
375 296342681753808
376 302647919708409
377 309070231769901
378 315611476802172
379 322273537115631
380 329058320878911
381 335967760208080
382 343003813600896
383 350168464027600
384 357463721388224
385 364891620555760
386 372454223905984
387 380153619312753
388 387991922701123
389 395971276044253
390 404093849940326
391 412361841560305
392 420777477299673
393 429343010676789
394 438060725008676
395 446932931311009
396 455961970998468
397 465150213734030
398 474500060206480
399 484013939928751
400 493694314040249
401 503543673106850
402 513564539948564
403 523759467387264
404 534131041153883
405 544681877583615
406 555414626548704
407 566331969155327
408 577436620702508
409 588731328325137
410 600218874034828
411 611902072308810
412 623783773157167
413 635866859713436
414 648154251328770
415 660648901107052
416 673353799083449
417 686271969703774
418 699406475030224
419 712760412222474
420 726336916771148
421 740139159921785
422 754170351995184
423 768433739753970
424 782932609750937
425 797670285697371
426 812650131839948
427 827875550270261
428 843349984391111
429 859076916166962
430 875059869619056
431 891302408077650
432 907808137706520
433 924580704694710
434 941623798872984
435 958941150844807
436 976536535632459
437 994413769809823
438 1012576715178734
439 1031029275839563
440 1049775401962105
441 1068819086793675
442 1088164370460508
443 1107815336977687
444 1127776118081636
445 1148050890176104
446 1168643878261824
447 1189559352818265
448 1210801633764665
449 1232375087343640
450 1254284130114180
451 1276533225769550
452 1299126889230115
453 1322069683395241
454 1345366223268368
455 1369021172710793
456 1393039248599588
457 1417425217513887
458 1442183899995332
459 1467320167166568
460 1492838945024823
461 1518745211062310
462 1545043998593546
463 1571740393306446
464 1598839537694905
465 1626346627540284
466 1654266916378024
467 1682605711981064
468 1711368380861100
469 1740560344680859
470 1770187084863392
471 1800254138932900
472 1830767105158969
473 1861731638899353
474 1893153457279772
475 1925038335463691
476 1957392111442959
477 1990220682234276
478 2023530008705696
479 2057326111775076
480 2091615077273072
481 2126403052066700
482 2161696249036016
483 2197500943122477
484 2233823476342419
485 2270670253837425
486 2308047748925238
487 2345962499073333
488 2384421111066393
489 2423430256902769
490 2462996678999700
491 2503127186091805
492 2543828658474692
493 2585108043824722
494 2626972362562096
495 2669428703591571
496 2712484229704249
497 2756146173320350
498 2800421841930356
499 2845318613757100
500 2890843943319339
501 2937005357012835
502 2983810458713600
503 3031266925361059
504 3079382512601628
505 3128165050289213
506 3177622448254204
507 3227762691720982
508 3278593847117567
509 3330124057495232
510 3382361548379474
511 3435314623104960
512 3488991668794937
513 3543401151611178
514 3598551622775040
515 3654451713819542
516 3711110142652748
517 3768535708723149
518 3826737299214544
519 3885723884124390
520 3945504522501337
521 4006088357525735
522 4067484622790508
523 4129702637292913
524 4192751811850007
525 4256641644001318
526 4321381724467984
527 4386981732057606
528 4453451440167752
529 4520800711599986
530 4589039505201096
531 4658177870585955
532 4728225954823451
533 4799193997161555
534 4871092335758654
535 4943931402315695
536 5017721728948409
537 5092473942726183
538 5168198772590028
539 5244907043893683
540 5322609685368036
541 5401317723567180
542 5481042289976928
543 5561794615365469
544 5643586036938681
545 5726427992693044
546 5810332028618468
547 5895309792954010
548 5981373043538035
549 6068533641966381
550 6156803560990384
551 6246194878677325
552 6336719785857044
553 6428390580183019
554 6521219673729588
555 6615219586953300
556 6710402956339079
557 6806782528363882
558 6904371167192538
559 7003181848539842
560 7103227667520313
561 7204521832408360
562 7307077672538072
563 7410908632065716
564 7516028277920300
565 7622450293462287
566 7730188486591424
567 7839256783301304
568 7949669235838329
569 8061440016258629
570 8174583424638908
571 8289113882527335
572 8405045941315039
573 8522394275580600
574 8641173691513792
575 8761399120262456
576 8883085626409248
577 9006248401210216
578 9130902771235616
579 9257064191499817
580 9384748254155491
581 9513970681625925
582 9644747335353350
583 9777094208820665
584 9911027436467289
585 10046563286599917
586 10183718170362884
587 10322508634651353
588 10462951371136964
589 10605063209068118
590 10748861124466640
591 10894362232814775
592 11041583798307513
593 11190543226542042
594 11341258073826516
595 11493746039754264
596 11648024976687099
597 11804112882213895
598 11962027908690720
599 12121788355701895
600 12283412679657740
601 12446919486138025
602 12612327539667820
603 12779655755942946
604 12948923211663823
605 13120149136763428
606 13293352924299938
607 13468554122564692
608 13645772445156537
609 13825027762969398
610 14006340114325808
611 14189729696967010
612 14375216878246476
613 14562822186997601
614 14752566323912560
615 14944470153287194
616 15138554713460249
617 15334841208560819
618 15533351019008780
619 15734105693137389
620 15937126957882727
621 16142436710281050
622 16350057028219824
623 16560010161937658
624 16772318544837752
625 16987004784860526
626 17204091675489784
627 17423602186997631
628 17645559477513451
629 17869986884271431
630 18096907934743182
631 18326346337755475
632 18558325994819321
633 18792870991117507
634 19030005606897724
635 19269754308462735
636 19512141759628388
637 19757192812581488
638 20004932519538048
639 20255386123468449
640 20508579069820985
641 20764536997249680
642 21023285749403972
643 21284851365521702
644 21549260092422851
645 21816538374967281
646 22086712868115024
647 22359810427386705
648 22635858120991236
649 22914883220148855
650 23196913211426724
651 23481975786924160
652 23770098856676055
653 24061310538840814
654 24355639172172458
655 24653113306068598
656 24953761713254329
657 25257613379689812
658 25564697517323272
659 25875043554001312
660 26188681146291884
661 26505640169252035
662 26825950729466592
663 27149643154672908
664 27476748006869945
665 27807296071945777
666 28141318372857948
667 28478846159115779
668 28819910920180399
669 29164544374801420
670 29512778484488672
671 29864645442851660
672 30220177689143888
673 30579407897454468
674 30942368990476112
675 31309094128548453
676 31679616723499059
677 32053970427689561
678 32432189147930582
679 32814307034377341
680 33200358494672281
681 33590378182689705
682 33984401012752756
683 34382462148380885
684 34784597016582084
685 35190841296447130
686 35601230933673584
687 36015802129006363
688 36434591352837433
689 36857635333649238
690 37284971072690996
691 37716635832266180
692 38152667150644683
693 38593102830193899
694 39037980952367936
695 39487339865841579
696 39941218201577468
697 40399654860801365
698 40862689030309340
699 41330360170283886
700 41802708029679519
701 42279772634041800
702 42761594300972274
703 43248213627786024
704 43739671507220793
705 44236009114932610
706 44737267925284704
707 45243489698846062
708 45754716498261068
709 46270990675583797
710 46792354888396048
711 47318852086976910
712 47850525530501977
713 48387418774215871
714 48929575685713580
715 49477040431945897
716 50029857495753399
717 50588071662704334
718 51151728037711184
719 51720872031871534
720 52295549379168168
721 52875806123140010
722 53461688633839144
723 54053243594331355
724 54650518017737147
725 55253559233735291
726 55862414905688798
727 56477133016975671
728 57097761888376121
729 57724350164230047
730 58356946829909676
731 58995601197980075
732 59640362925758180
733 60291282001297620
734 60948408761213344
735 61611793876490277
736 62281488370394809
737 62957543604286508
738 63640011295617444
739 64328943503565298
740 65024392647302675
741 65726411491451125
742 66435053164438768
743 67150371143957397
744 67872419275409396
745 68601251757183299
746 69336923159375124
747 70079488408881900
748 70829002808212775
749 71585522020585650
750 72349102088829050
751 73119799420294250
752 73897670806036025
753 74682773405539776
754 75475164765993528
755 76274902807018188
756 77082045840031788
757 77896652552792247
758 78718782029044992
759 79548493732877728
760 80385847528460793
761 81230903664405085
762 82083722793596156
763 82944365957361631
764 83812894605593215
765 84689370580723104
766 85573856137940224
767 86466413929169824
768 87367107023384960
769 88275998890392544
770 89193153421437312
771 90118634912793825
772 91052508086466179
773 91994838073783213
774 92945690436194982
775 93905131148671361
776 94873226620795609
777 95850043679965861
778 96835649592585956
779 97830112047270161
780 98833499176132292
781 99845879537790750
782 100867322138959376
783 101897896417252287
784 102937672262873529
785 103986720001425170
786 105045110415696788
787 106112914728270768
788 107190204623618203
789 108277052230500879
790 109373530144167520
791 110479711408759055
792 111595669539606252
793 112721478505429057
794 113857212750945356
795 115002947178863866
796 116158757172594799
797 117324718578246060
798 118500907727436866
799 119687401419084860
800 120884276942535609
801 122091612059140110
802 123309485025487760
803 124537974574987194
804 125777159941203788
805 127027120839228233
806 128287937489334704
807 129559690598136642
808 130842461382349977
809 132136331549952267
810 133441383324052044
811 134757699423832485
812 136085363088746247
813 137424458059243138
814 138775068601071600
815 140137279486009762
816 141511176016274648
817 142896844005034534
818 144294369801148504
819 145703840269459575
820 147125342815642507
821 148558965366500335
822 150004796394921518
823 151462924899954523
824 152933440432100217
825 154416433073163963
826 155911993461657884
827 157420212772656391
828 158941182743309412
829 160474995652472696
830 162021744346561216
831 163581522218953705
832 165154423235957561
833 166740541916216840
834 168339973356789764
835 169952813212328190
836 171579157721500259
837 173219103685940793
838 174872748496787088
839 176540190113632793
840 178221527091177956
841 179916858557951055
842 181626284243309188
843 183349904455927704
844 185087820110915191
845 186840132708306614
846 188606944360294218
847 190388357769485470
848 192184476256489145
849 193995403737937516
850 195821244754188904
851 197662104447353400
852 199518088589113004
853 201389303558508779
854 203275856370121248
855 205177854651618420
856 207095406672054329
857 209028621319420617
858 210977608129064348
859 212942477260997627
860 214923339528680783
861 216920306376089460
862 218933489906617632
863 220963002860148276
864 223008958642077360
865 225071471300139132
866 227150655553800624
867 229246626770840989
868 231359500996867539
869 233489394931898689
870 235636425960002678
871 237800712125631685
872 239982372163636249
873 242181525475349985
874 244398292158727252
875 246632792984431501
876 248885149426097348
877 251155483636166626
878 253443918476531376
879 255750577494117027
880 258075584951650361
881 260419065803246350
882 262781145725302260
883 265161951091828700
884 267561609005729899
885 269980247273878387
886 272417994438521984
887 274874979752362163
888 277351333210088924
889 279847185523199853
890 282362668151926460
891 284897913279793350
892 287453053845673023
893 290028223518348752
894 292623556728699026
895 295239188643997584
896 297875255200494649
897 300531893077453530
898 303209239729862080
899 305907433362473030
900 308626612962646860
901 311366918274125725
902 314128489830278480
903 316911468927607606
904 319715997659126233
905 322542218887868823
906 325390276280401388
907 328260314280062177
908 331152478140879447
909 334066913900541558
910 337003768414448528
911 339963189328685910
912 342945325114211336
913 345950325039554786
914 348978339205418120
915 352029518517101139
916 355104014719236699
917 358201980368220579
918 361323568867083390
919 364468934437643199
920 367638232155795897
921 370831617923389975
922 374049248503654284
923 377291281493076643
924 380557875356970212
925 383849189401071196
926 387165383807529184
927 390506619606223341
928 393873058710891961
929 397264863890452516
930 400682198805271652
931 404125227978200650
932 407594116831274931
933 411089031656464317
934 414610139652513584
935 418157608895696605
936 421731608376799188
937 425332307971584923
938 428959878478213108
939 432614491587415684
940 436296319920058055
941 440005536997319930
942 443742317278400282
943 447506836130406162
944 451299269866498361
945 455119795715487576
946 458968591860124824
947 462845837406701540
948 466751712423485996
949 470686397910027615
950 474650075836039744
951 478642929110407560
952 482665141620217465
953 486716898199768949
954 490798384669751868
955 494909787805958743
956 499051295378914079
957 503223096122286472
958 507425379772666432
959 511658337037982472
960 515922159637428704
961 520217040269577560
962 524543172652765152
963 528900751492899993
964 533289972523998755
965 537711032475998997
966 542164129115446598
967 546649461213001289
968 551167228584587609
969 555717632058592605
970 560300873517169092
971 564917155863437385
972 569566683062942148
973 574249660110543078
974 578966293072341072
975 583716789052257223
976 588501356234113209
977 593320203848214346
978 598173542213585492
979 603061582704239176
980 607984537791886651
981 612942621011890455
982 617936047006131616
983 622965031488966295
984 628029791290250444
985 633130544320977625
986 638267509616784684
987 643440907303270098
988 648650958639657743
989 653897885984119348
990 659181912837597666
991 664503263808806180
992 669862164658539193
993 675258842264348134
994 680693524665011696
995 686166441025216274
996 691677821680187468
997 697227898100043825
998 702816902934921200
999 708445069978999146
1000 714112634215787289