3 6
4 93
5 591
6 2381
7 7316
8 18761
9 42253
10 86281
11 163186
12 290181
13 490491
14 794613
15 1241696
16 1881041
17 2773721
18 3994321
19 5632798
20 7796461
21 10612071
22 14228061
23 18816876
24 24577433
25 31737701
26 40557401
27 51330826
28 64389781
29 80106643
30 98897541
31 121225656
32 147604641
33 178602161
34 214843553
35 257015606
36 305870461
37 362229631
38 426988141
39 501118788
40 585676521
41 681802941
42 790730921
43 913789346
44 1052407973
45 1208122411
46 1382579221
47 1577541136
48 1794892401
49 2036644233
50 2304940401
51 2602062926
52 2930437901
53 3292641431
54 3691405693
55 4129625116
56 4610362681
57 5136856341
58 5712525561
59 6340977978
60 7026016181
61 7771644611
62 8582076581
63 9461741416
64 10415291713
65 11447610721
66 12563819841
67 13769286246
68 15069630621
69 16470735023
70 17978750861
71 19600106996
72 21341517961
73 23209992301
74 25212841033
75 27357686226
76 29652469701
77 32105461851
78 34725270581
79 37520850368
80 40501511441
81 43676929081
82 47057153041
83 50652617086
84 54474148653
85 58532978631
86 62840751261
87 67409534156
88 72251828441
89 77380579013
90 82809184921
91 88551509866
92 94621892821
93 101035158771
94 107806629573
95 114952134936
96 122488023521
97 130431174161
98 138799007201
99 147609495958
100 156881178301
101 166633168351
102 176885168301
103 187657480356
104 198971018793
105 210847322141
106 223308565481
107 236377572866
108 250077829861
109 264433496203
110 279469418581
111 295211143536
112 311684930481
113 328917764841
114 346937371313
115 365772227246
116 385451576141
117 406005441271
118 427464639421
119 449860794748
120 473226352761
121 497594594421
122 522999650361
123 549476515226
124 577061062133
125 605790057251
126 635701174501
127 666833010376
128 699225098881
129 732917926593
130 767952947841
131 804372600006
132 842220318941
133 881540554511
134 922378786253
135 964781539156
136 1008796399561
137 1054472031181
138 1101858191241
139 1151005746738
140 1201966690821
141 1254794159291
142 1309542447221
143 1366267025696
144 1425024558673
145 1485872919961
146 1548871210321
147 1614079774686
148 1681560219501
149 1751375430183
150 1823589588701
151 1898268191276
152 1975478066201
153 2055287391781
154 2137765714393
155 2222983966666
156 2311014485781
157 2401931031891
158 2495808806661
159 2592724471928
160 2692756168481
161 2795983534961
162 2902487726881
163 3012351435766
164 3125658908413
165 3242495966271
166 3362950024941
167 3487110113796
168 3615066895721
169 3746912686973
170 3882741477161
171 4022648949346
172 4166732500261
173 4315091260651
174 4467826115733
175 4625039725776
176 4786836546801
177 4953322851401
178 5124606749681
179 5300798210318
180 5482009081741
181 5668353113431
182 5859945977341
183 6056905289436
184 6259350631353
185 6467403572181
186 6681187690361
187 6900828595706
188 7126453951541
189 7358193496963
190 7596179069221
191 7840544626216
192 8091426269121
193 8348962265121
194 8613293070273
195 8884561352486
196 9162912014621
197 9448492217711
198 9741451404301
199 10041941321908
200 10350116046601
201 10666132006701
202 10990148006601
203 11322325250706
204 11662827367493
205 12011820433691
206 12369472998581
207 12735956108416
208 13111443330961
209 13496110780153
210 13890137140881
211 14293703693886
212 14706994340781
213 15130195629191
214 15563496778013
215 16007089702796
216 16461169041241
217 16925932178821
218 17401579274521
219 17888313286698
220 18386339999061
221 18895868046771
222 19417108942661
223 19950277103576
224 20495589876833
225 21053267566801
226 21623533461601
227 22206613859926
228 22802738097981
229 23412138576543
230 24035050788141
231 24671713344356
232 25322368003241
233 25987259696861
234 26666636558953
235 27360749952706
236 28069854498661
237 28794208102731
238 29534071984341
239 30289710704688
240 31061392195121
241 31849387785641
242 32653972233521
243 33475423752046
244 34314024039373
245 35170058307511
246 36043815311421
247 36935587378236
248 37845670436601
249 38774364046133
250 39721971427001
251 40688799489626
252 41675158864501
253 42681363932131
254 43707732853093
255 44754587598216
256 45822253978881
257 46911061677441
258 48021344277761
259 49153439295878
260 50307688210781
261 51484436495311
262 52684033647181
263 53906833220116
264 55153192855113
265 56423474311821
266 57718043500041
267 59037270511346
268 60381529650821
269 61751199468923
270 63146662793461
271 64568306761696
272 66016522852561
273 67491706919001
274 68994259220433
275 70524584455326
276 72083091793901
277 73670194910951
278 75286312018781
279 76931865900268
280 78607283942041
281 80312998167781
282 82049445271641
283 83817066651786
284 85616308444053
285 87447621555731
286 89311461699461
287 91208289427256
288 93138570164641
289 95102774244913
290 97101376943521
291 99134858512566
292 101203704215421
293 103308404361471
294 105449454340973
295 107627354660036
296 109842610975721
297 112095734131261
298 114387240191401
299 116717650477858
300 119087491604901
301 121497295515051
302 123947599514901
303 126438946311056
304 128971884046193
305 131546966335241
306 134164752301681
307 136825806613966
308 139530699522061
309 142280006894103
310 145074310253181
311 147914196814236
312 150800259521081
313 153733097083541
314 156713314014713
315 159741520668346
316 162818333276341
317 165944373986371
318 169120270899621
319 172346658108648
320 175624175735361
321 178953469969121
322 182335193104961
323 185770003581926
324 189258566021533
325 192801551266351
326 196399636418701
327 200053504879476
328 203763846387081
329 207531357056493
330 211356739418441
331 215240702458706
332 219183961657541
333 223187239029211
334 227251263161653
335 231376769256256
336 235564499167761
337 239815201444281
338 244129631367441
339 248508550992638
340 252952729189421
341 257462941681991
342 262039971089821
343 266684606968396
344 271397645850073
345 276179891285061
346 281032153882521
347 285955251351786
348 290950008543701
349 296017257492083
350 301157837455301
351 306372594957976
352 311662383832801
353 317028065262481
354 322470507821793
355 327990587519766
356 333589187841981
357 339267199792991
358 345025521938861
359 350865060449828
360 356786729143081
361 362791449525661
362 368880150837481
363 375053770094466
364 381313252131813
365 387659549647371
366 394093623245141
367 400616441478896
368 407228980895921
369 413932226080873
370 420727169699761
371 427614812544046
372 434596163574861
373 441672239967351
374 448844067155133
375 456112678874876
376 463479117211001
377 470944432640501
378 478509684077881
379 486175938920218
380 493944273092341
381 501815771092131
382 509791526035941
383 517872639704136
384 526060222586753
385 534355393929281
386 542759281778561
387 551273023028806
388 559897763467741
389 568634657822863
390 577484869807821
391 586449572168916
392 595529946731721
393 604727184447821
394 614042485441673
395 623477059057586
396 633032123906821
397 642708907914811
398 652508648368501
399 662432591963808
400 672481994853201
401 682658122693401
402 692962250693201
403 703395663661406
404 713959656054893
405 724655532026791
406 735484605474781
407 746448200089516
408 757547649403161
409 768784296838053
410 780159495755481
411 791674609504586
412 803331011471381
413 815130085127891
414 827073224081413
415 839161832123896
416 851397323281441
417 863781121863921
418 876314662514721
419 888999390260598
420 901836760561661
421 914828239361471
422 927975303137261
423 941279438950276
424 954742144496233
425 968364928155901
426 982149309045801
427 996096817069026
428 1010208992966181
429 1024487388366443
430 1038933565838741
431 1053549098943056
432 1068335572281841
433 1083294581551561
434 1098427733594353
435 1113736646449806
436 1129222949406861
437 1144888283055831
438 1160734299340541
439 1176762661610588
440 1192975044673721
441 1209373134848341
442 1225958630016121
443 1242733239674746
444 1259698684990773
445 1276856698852611
446 1294209025923621
447 1311757422695336
448 1329503657540801
449 1347449510768033
450 1365596774673601
451 1383947253596326
452 1402502763971101
453 1421265134382831
454 1440236205620493
455 1459417830731316
456 1478811875075081
457 1498420216378541
458 1518244744789961
459 1538287362933778
460 1558549985965381
461 1579034541626011
462 1599742970297781
463 1620677225058816
464 1641839271738513
465 1663231088972921
466 1684854668260241
467 1706712014016446
468 1728805143631021
469 1751136087522823
470 1773706889196061
471 1796519605296396
472 1819576305667161
473 1842879073405701
474 1866430004919833
475 1890231209984426
476 1914284811798101
477 1938592947040051
478 1963157765926981
479 1987981432270168
480 2013066123532641
481 2038414030886481
482 2064027359270241
483 2089908327446486
484 2116059168059453
485 2142482127692831
486 2169179466927661
487 2196153460400356
488 2223406396860841
489 2250940579230813
490 2278758324662121
491 2306861964595266
492 2335253844818021
493 2363936325524171
494 2392911781372373
495 2422182601545136
496 2451751189807921
497 2481619964568361
498 2511791358935601
499 2542267820779758
500 2573051812791501
501 2604145812541751
502 2635552312541501
503 2667273820301756
504 2699312858393593
505 2731671964508341
506 2764353691517881
507 2797360607535066
508 2830695295974261
509 2864360355612003
510 2898358400647781
511 2932692060764936
512 2967363981191681
513 3002376822762241
514 3037733261978113
515 3073435991069446
516 3109487718056541
517 3145891166811471
518 3182649077119821
519 3219764204742548
520 3257239321477961
521 3295077215223821
522 3333280690039561
523 3371852566208626
524 3410795680300933
525 3450112885235451
526 3489807050342901
527 3529881061428576
528 3570337820835281
529 3611180247506393
530 3652411277049041
531 3694033861797406
532 3736050970876141
533 3778465590263911
534 3821280722857053
535 3864499388533356
536 3908124624215961
537 3952159483937381
538 3996607038903641
539 4041470377558538
540 4086752605648021
541 4132456846284691
542 4178586240012421
543 4225143944871096
544 4272133136461473
545 4319557008010161
546 4367418770434721
547 4415721652408886
548 4464468900427901
549 4513663778873983
550 4563309570081901
551 4613409574404676
552 4663967110279401
553 4714985514293181
554 4766468141249193
555 4818418364232866
556 4870839574678181
557 4923735182434091
558 4977108615831061
559 5030963321747728
560 5085302765677681
561 5140130431796361
562 5195449823028081
563 5251264461113166
564 5307577886675213
565 5364393659288471
566 5421715357545341
567 5479546579123996
568 5537890940856121
569 5596752078794773
570 5656133648282361
571 5716039324018746
572 5776472800129461
573 5837437790234051
574 5898938027514533
575 5960977264783976
576 6023559274555201
577 6086687849109601
578 6150366800566081
579 6214599960950118
580 6279391182262941
581 6344744336550831
582 6410663315974541
583 6477152032878836
584 6544214419862153
585 6611854429846381
586 6680076036146761
587 6748883232541906
588 6818280033343941
589 6888270473468763
590 6958858608506421
591 7030048514791616
592 7101844289474321
593 7174250050590521
594 7247269937133073
595 7320908109122686
596 7395168747679021
597 7470056055091911
598 7545574254892701
599 7621727591925708
600 7698520332419801
601 7775956764060101
602 7854041196059801
603 7932777959232106
604 8012171406062293
605 8092225910779891
606 8172945869430981
607 8254335699950616
608 8336399842235361
609 8419142758215953
610 8502568931930081
611 8586682869595286
612 8671489099681981
613 8756992172986591
614 8843196662704813
615 8930107164504996
616 9017728296601641
617 9106064699829021
618 9195121037714921
619 9284901996554498
620 9375412285484261
621 9466656636556171
622 9558639804811861
623 9651366568356976
624 9744841728435633
625 9839070109505001
626 9934056559310001
627 10029805948958126
628 10126323172994381
629 10223613149476343
630 10321680820049341
631 10420531150021756
632 10520169128440441
633 10620599768166261
634 10721828105949753
635 10823859202506906
636 10926698142595061
637 11030350035088931
638 11134820013056741
639 11240113233836488
640 11346234879112321
641 11453190154991041
642 11560984292078721
643 11669622545557446
644 11779110195262173
645 11889452545757711
646 12000654926415821
647 12112722691492436
648 12225661220205001
649 12339475916809933
650 12454172210680201
651 12569755556383026
652 12686231433757701
653 12803605347993531
654 12921882829707893
655 13041069435024416
656 13161170745651281
657 13282192368959641
658 13404139938062161
659 13527019111891678
660 13650835575279981
661 13775595039036711
662 13901303240028381
663 14027965941257516
664 14155588931941913
665 14284178027594021
666 14413739070100441
667 14544277927801546
668 14675800495571221
669 14808312694896723
670 14941820473958661
671 15076329807711096
672 15211846697961761
673 15348377173452401
674 15485927289939233
675 15624503130273526
676 15764110804482301
677 15904756449849151
678 16046446230995181
679 16189186339960068
680 16332982996283241
681 16477842447085181
682 16623770967148841
683 16770774859001186
684 16918860452994853
685 17068034107389931
686 17218302208435861
687 17369671170453456
688 17522147435917041
689 17675737475536713
690 17830447788340721
691 17986284901757966
692 18143255371700621
693 18301365782646871
694 18460622747723773
695 18621032908790236
696 18782602936520121
697 18945339530485461
698 19109249419239801
699 19274339360401658
700 19440616140738101
701 19608086576248451
702 19776757512248101
703 19946635823452456
704 20117728414060993
705 20290042217841441
706 20463584198214081
707 20638361348336166
708 20814380691186461
709 20991649279649903
710 21170174196602381
711 21349962554995636
712 21531021497942281
713 21713358198800941
714 21896979861261513
715 22081893719430546
716 22268107037916741
717 22455627111916571
718 22644461267300021
719 22834616860696448
720 23026101279580561
721 23218921942358521
722 23413086298454161
723 23608601828395326
724 23805476043900333
725 24003716487964551
726 24203330734947101
727 24404326390657676
728 24606711092443481
729 24810492509276293
730 25015678341839641
731 25222276322616106
732 25430294215974741
733 25639739818258611
734 25850620957872453
735 26062945495370456
736 26276721323544161
737 26491956367510481
738 26708658584799841
739 26926835965444438
740 27146496532066621
741 27367648339967391
742 27590299477215021
743 27814458064733796
744 28040132256392873
745 28267330239095261
746 28496060232866921
747 28726330490945986
748 28958149299872101
749 29191524979575883
750 29426465883468501
751 29662980398531376
752 29901076945406001
753 30140763978483881
754 30382049985996593
755 30624943490105966
756 30869453046994381
757 31115587246955191
758 31363354714483261
759 31612764108365628
760 31863824121772281
761 32116543482347061
762 32370930952298681
763 32626995328491866
764 32884745442538613
765 33144190160889571
766 33405338384925541
767 33668199051049096
768 33932781130776321
769 34199093630828673
770 34467145593224961
771 34736946095373446
772 35008504250164061
773 35281829206060751
774 35556930147193933
775 35833816293453076
776 36112496900579401
777 36392981260258701
778 36675278700214281
779 36959398584300018
780 37245350312593541
781 37533143321489531
782 37822787083793141
783 38114291108813536
784 38407664942457553
785 38702918167323481
786 39000060402794961
787 39299101305135006
788 39600050567580141
789 39902917920434663
790 40207713131165021
791 40514446004494316
792 40823126382496921
793 41133764144693221
794 41446369208144473
795 41760951527547786
796 42077521095331221
797 42396087941749011
798 42716662134976901
799 43039253781207608
800 43363873024746401
801 43690530048106801
802 44019235072106401
803 44349998355962806
804 44682830197389693
805 45017740932692991
806 45354740936867181
807 45693840623691716
808 46035050445827561
809 46378380894913853
810 46723842501664681
811 47071445835965986
812 47421201506972581
813 47773120163205291
814 48127212492648213
815 48483489222846096
816 48841961121001841
817 49202638994074121
818 49565533688875121
819 49930656092168398
820 50298017130766861
821 50667627771630871
822 51039499021966461
823 51413641929323676
824 51790067581695033
825 52168787107614101
826 52549811676254201
827 52933152497527226
828 53318820822182581
829 53706827941906243
830 54097185189419941
831 54489903938580456
832 54884995604479041
833 55282471643540961
834 55682343553625153
835 56084622874124006
836 56489321186063261
837 56896450112202031
838 57306021317132941
839 57718046507382388
840 58132537431510921
841 58549505880213741
842 58968963686421321
843 59390922725400146
844 59815394914853573
845 60242392215022811
846 60671926628788021
847 61104010201769536
848 61538655022429201
849 61975873222171833
850 62415676975446801
851 62858078499849726
852 63303090056224301
853 63750723948764231
854 64200992525115293
855 64653908176477516
856 65109483337707481
857 65567730487420741
858 66028662148094361
859 66492290886169578
860 66958629312154581
861 67427690080727411
862 67899485890838981
863 68374029485816216
864 68851333653465313
865 69331411226175121
866 69814275081020641
867 70299938139866646
868 70788413369471421
869 71279713781590623
870 71773852433081261
871 72270842426005796
872 72770696907736361
873 73273429071059101
874 73779052154278633
875 74287579441322626
876 74799024261846501
877 75313399991338251
878 75830720051223381
879 76350997908969968
880 76874247078193841
881 77400481118763881
882 77929713636907441
883 78461958285315886
884 78997228763250253
885 79535538816647031
886 80076902238224061
887 80621332867586556
888 81168844591333241
889 81719451343162613
890 82273167103979321
891 82830005902000666
892 83389981812863221
893 83953108959729571
894 84519401513395173
895 85088873692395336
896 85661539763112321
897 86237414039882561
898 86816510885104001
899 87398844709343558
900 87984429971444701
901 88573281178635151
902 89165412886634701
903 89760839699763156
904 90359576271048393
905 90961637302334541
906 91567037544390281
907 92175791797017266
908 92787914909158661
909 93403421779007803
910 94022327354116981
911 94644646631506336
912 95270394657772881
913 95899586529199641
914 96532237391864913
915 97168362441751646
916 97807976924856941
917 98451096137301671
918 99097735425440221
919 99747910185970348
920 100401635866043161
921 101058927963373221
922 101719802026348761
923 102384273654142026
924 103052358496819733
925 103724072255453651
926 104399430682231301
927 105078449580566776
928 105761144805211681
929 106447532262366193
930 107137627909790241
931 107831447756914806
932 108529007864953341
933 109230324347013311
934 109935413368207853
935 110644291145767556
936 111356973949152361
937 112073478100163581
938 112793819973056041
939 113518015994650338
940 114246082644445221
941 114978036454730091
942 115713894010697621
943 116453671950556496
944 117197386965644273
945 117945055800540361
946 118696695253179121
947 119452322174963086
948 120211953470876301
949 120975606099597783
950 121743297073615101
951 122515043459338076
952 123290862377212601
953 124070771001834581
954 124854786562063993
955 125642926341139066
956 126435207676790581
957 127231647961356291
958 128032264641895461
959 128837075220303528
960 129646097253426881
961 130459348353177761
962 131276846186649281
963 132098608476230566
964 132924652999722013
965 133754997590450671
966 134589660137385741
967 135428658585254196
968 136272010934656521
969 137119735242182573
970 137971849620527561
971 138828372238608146
972 139689321321678661
973 140554715151447451
974 141424572066193333
975 142298910460882176
976 143177748787283601
977 144061105554087801
978 144948999327022481
979 145841448728969918
980 146738472440084141
981 147640089197908231
982 148546317797491741
983 149457177091508236
984 150372685990372953
985 151292863462360581
986 152217728533723161
987 153147300288808106
988 154081597870176341
989 155020640478720563
990 155964447373783621
991 156913037873277016
992 157866431353799521
993 158824647250755921
994 159787705058475873
995 160755624330332886
996 161728424678863421
997 162706125775886111
998 163688747352621101
999 164676309199809508
1000 165668831167833001