1 1
2 6
3 15
4 19
5 24
6 42
7 73
8 127
9 208
10 337
11 528
12 827
13 1263
14 1902
15 2819
16 4133
17 5986
18 8578
19 12146
20 17057
21 23711
22 32708
23 44726
24 60713
25 81800
26 109468
27 145526
28 192288
29 252521
30 329792
31 428316
32 553478
33 711596
34 910563
35 1159790
36 1470798
37 1857286
38 2335838
39 2926061
40 3651688
41 4540502
42 5625896
43 6946852
44 8549811
45 10489000
46 12828386
47 15642512
48 19018801
49 23058592
50 27880409
51 33620962
52 40439466
53 48518887
54 58071136
55 69339435
56 82603981
57 98185407
58 116451566
59 137822002
60 162776820
61 191861488
62 225698134
63 264991658
64 310543169
65 363258495
66 424163289
67 494414528
68 575318409
69 668344278
70 775147106
71 897583523
72 1037739424
73 1197949303
74 1380828864
75 1589300106
76 1826628340
77 2096453541
78 2402833860
79 2750283376
80 3143824951
81 3589033421
82 4092099110
83 4659879456
84 5299973135
85 6020783302
86 6831602040
87 7742687246
88 8765360835
89 9912099026
90 11196649017
91 12634132852
92 14241184898
93 16036073167
94 18038858328
95 20271538787
96 22758231298
97 25525342322
98 28601776143
99 32019134092
100 35811957459
101 40017954538
102 44678282676
103 49837810973
104 55545443326
105 61854425127
106 68822708806
107 76513310728
108 84994728396
109 94341349533
110 104633932530
111 115960070658
112 128414743011
113 142100844543
114 157129811796
115 173622233538
116 191708554947
117 211529777216
118 233238254852
119 256998490896
120 282988044596
121 311398426537
122 342436129020
123 376323639842
124 413300603355
125 453624972989
126 497574310830
127 545447095132
128 597564180575
129 654270270172
130 715935562392
131 782957399012
132 855762118360
133 934806904877
134 1020581862990
135 1113612100940
136 1214460039361
137 1323727752085
138 1442059542846
139 1570144562670
140 1708719692923
141 1858572456156
142 2020544235824
143 2195533522226
144 2384499492514
145 2588465636011
146 2808523718934
147 3045837827426
148 3301648765779
149 3577278545421
150 3874135272230
151 4193718113642
152 4537622720557
153 4907546729262
154 5305295756062
155 5732789501816
156 6192068358052
157 6685300167357
158 7214787511922
159 7782975178402
160 8392458207812
161 9045990111168
162 9746491748255
163 10497060380008
164 11300979434320
165 12161728486392
166 13082993972166
167 14068680179641
168 15122921010051
169 16250092048721
170 17454823485533
171 18742013341186
172 20116841644246
173 21584784928836
174 23151631755356
175 24823498612719
176 26606846873052
177 28508500211654
178 30535663136402
179 32695940032654
180 34997355421369
181 37448374735100
182 40057926443690
183 42835424728690
184 45790793602810
185 48934491660125
186 52277538321370
187 55831540826220
188 59608722798115
189 63621953625885
190 67884779559776
191 72411455642806
192 77216979531128
193 82317126197631
194 87728484656953
195 93468495690056
196 99555491661649
197 106008737488899
198 112848473815484
199 120095961440199
200 127773528133613
201 135904616744740
202 144513835926782
203 153627012231500
204 163271244994927
205 173474962746157
206 184267982516252
207 195681570874850
208 207748508017252
209 220503153718975
210 233981516584245
211 248221325230236
212 263262103057885
213 279145245070791
214 295914098513780
215 313614045771203
216 332292591233801
217 351999450689384
218 372786644891226
219 394708595846564
220 417822227593447
221 442187069801925
222 467865366243284
223 494922186250710
224 523425541347584
225 553446505142915
226 585059338607385
227 618341618964788
228 653374374237825
229 690242221669363
230 729033512203688
231 769840479006423
232 812759392521185
233 857890719793148
234 905339290724590
235 955214468965312
236 1007630330018391
237 1062705844423921
238 1120565068526996
239 1181337340675986
240 1245157485516385
241 1312166023945248
242 1382509391770012
243 1456340164347058
244 1533817290426882
245 1615106332450843
246 1700379716441622
247 1789816988918888
248 1883605083883312
249 1981938597282528
250 2085020072201983
251 2193060291867844
252 2306278584131270
253 2424903134187644
254 2549171309426490
255 2679329993130989
256 2815635930811981
257 2958356086112577
258 3107768009969531
259 3264160219947342
260 3427832593647950
261 3599096772737138
262 3778276581999504
263 3965708459578253
264 4161741903057954
265 4366739927509456
266 4581079540044170
267 4805152227247386
268 5039364459909815
269 5284138211405186
270 5539911494400392
271 5807138911816502
272 6086292227295498
273 6377860950651667
274 6682352943863988
275 7000295043046278
276 7332233701808179
277 7678735651733725
278 8040388585262954
279 8417801856678620
280 8811607206773389
281 9222459506410486
282 9651037525223162
283 10098044720165336
284 10564210050484702
285 11050288813785545
286 11557063509610998
287 12085344725542934
288 12635972052085713
289 13209815021306959
290 13807774075853606
291 14430781562760550
292 15079802759414571
293 15755836925523770
294 16459918388848396
295 17193117658494062
296 17956542573342462
297 18751339479799603
298 19578694446275652
299 20439834508548118
300 21336028953802079
301 22268590636872985
302 23238877337353738
303 24248293150450340
304 25298289920672693
305 26390368711192258
306 27526081317774538
307 28707031820548940
308 29934878182319798
309 31211333886652365
310 32538169624894482
311 33917215024661306
312 35350360429901721
313 36839558724354631
314 38386827209019946
315 39994249525395170
316 41663977634878943
317 43398233846581362
318 45199312903741408
319 47069584120961022
320 49011493582946619
321 51027566396176828
322 53120409005295871
323 55292711564843708
324 57547250378666616
325 59886890397560573
326 62314587787270612
327 64833392557949741
328 67446451266950532
329 70157009786022406
330 72968416145370851
331 75884123444767792
332 78907692845385705
333 82042796631644272
334 85293221357385980
335 88662871065605705
336 92155770595777086
337 95776068968623785
338 99528042862132616
339 103416100168624560
340 107444783647306564
341 111618774661136617
342 115942897013820632
343 120422120874771212
344 125061566808536247
345 129866509896462307
346 134842383966833688
347 139994785921949580
348 145329480178076743
349 150852403206710650
350 156569668193818682
351 162487569804405336
352 168612589070599091
353 174951398389489486
354 181510866649721381
355 188298064473007314
356 195320269589235892
357 202584972332119739
358 210099881273765752
359 217872928985080599
360 225912277941181385
361 234226326557517381
362 242823715377610418
363 251713333396889166
364 260904324544389178
365 270406094306725466
366 280228316515788714
367 290380940285445494
368 300874197118331579
369 311718608167991619
370 322924991678374413
371 334504470584602680
372 346468480298917677
373 358828776664362900
374 371597444101110282
375 384786903927922599
376 398409922883266074
377 412479621829540821
378 427009484664591544
379 442013367423941626
380 457505507598893730
381 473500533652473337
382 490013474760500252
383 507059770758271872
384 524655282321213442
385 542816301359911662
386 561559561657508143
387 580902249730949910
388 600862015943648228
389 621456985851023440
390 642705771807623438
391 664627484815683057
392 687241746646133374
393 710568702210292442
394 734629032214482004
395 759443966075733264
396 785035295130368915
397 811425386114826030
398 838637194950095150
399 866694280809124740
400 895620820499777452
401 925441623140924927
402 956182145166880416
403 987868505635965212
404 1020527501879722661
405 1054186625468512051
406 1088874078529555882
407 1124618790394499400
408 1161450434612060172
409 1199399446302821545
410 1238497039893140115
411 1278775227203294166
412 1320266835929667985
413 1363005528494144641
414 1407025821302008520
415 1452363104381470529
416 1499053661445588012
417 1547134690351159197
418 1596644323994888987
419 1647621651621407202
420 1700106740584915998
421 1754140658536950959
422 1809765496085194238
423 1867024389893693329
424 1925961546271026163
425 1986622265216713677
426 2049052964971912504
427 2113301207046304952
428 2179415721766649274
429 2247446434318922062
430 2317444491331209216
431 2389462287966994168
432 2463553495579406092
433 2539773089893763958
434 2618177379770803162
435 2698824036517874720
436 2781772123799899654
437 2867082128119147114
438 2954815989915074504
439 3045037135253325974
440 3137810508156923314
441 3233202603546270276
442 3331281500844801640
443 3432116898214385816
444 3535780147479247730
445 3642344289702489358
446 3751884091473397016
447 3864476081871563624
448 3980198590165369276
449 4099131784210893534
450 4221357709610844218
451 4346960329596894696
452 4476025565699092862
453 4608641339163016466
454 4744897613180532312
455 4884886435894812710
456 5028701984244782018
457 5176440608611789044
458 5328200878333063688
459 5484083628044816104
460 5644192004921701442
461 5808631516772611166
462 5977510081064039144
463 6150938074828046696
464 6329028385528398284
465 6511896462841889678
466 6699660371427792746
467 6892440844644779512
468 7090361339287522726
469 7293548091302424842
470 7502130172557118880
471 7716239548620064998
472 7936011137629737354
473 8161582870206558788
474 8393095750489697304
475 8630693918251898752
476 8874524712173704066
477 9124738734232785814
478 9381489915289068616
479 9644935581821480184
480 9915236523899586213
481 10192557064342591471
482 10477065129154319637
483 10768932319183243086
484 11068333983098948347
485 11375449291634150050
486 11690461313182918578
487 12013557090707026839
488 12344927720040274113
489 12684768429542837604
490 13033278661198424337
491 13390662153102653016
492 13757127023441168709
493 14132885855902258461
494 14518155786625580934
495 14913158592631845123
496 15318120781834206321
497 15733273684579257912
498 16158853546817631996
499 16595101624852267002
500 17042264281767434271
501 17500593085482698409
502 17970344908541214252
503 18451782029572602444
504 18945172236543093267
505 19450788931733284596
506 19968911238555413508
507 20499824110153795902
508 21043818439899449058
509 21601191173722772367
510 22172245424398750320
511 22757290587724391124
512 23356642460709596514
513 23970623361716966394
514 24599562252675408309
515 25243794863303192334
516 25903663817464395996
517 26579518761597979320
518 27271716495342612966
519 27980621104296763275
520 28706604095040800514
521 29450044532356183002
522 30211329178775869632
523 30990852636396510252
524 31789017491090443197
525 32606234459048232318
526 33442922535788919114
527 34299509147572623288
528 35176430305351705629
529 36074130761195446758
530 36993064167328518027
531 37933693237713440634
532 38896489912325176272
533 39881935524043237809
534 40890520968313777992
535 41922746875507275657
536 42979123786123278039
537 44060172328772049555
538 45166423401083705334
539 46298418353475053370
540 47456709175929007966
541 48641858687711729398
542 49854440730190955358
543 51095040362675549778
544 52364254061444286253
545 53662689921884179605
546 54990967863905468859
547 56349719840558143816
548 57739590050016088039
549 59161235150854172296
550 60615324480789134386
551 62102540278804175553
552 63623577910837253330
553 65179146098947545003
554 66769967154145106520
555 68396777212798548698
556 70060326476804691902
557 71761379457439972819
558 73500715223076630652
559 75279127650683960024
560 77097425681302674395
561 78956433579406923491
562 80856991196351982848
563 82799954237816352296
564 84786194535441595973
565 86816600322579084632
566 88892076514346010880
567 91013544991905182612
568 93181944891169878045
569 95398232895848863862
570 97663383535038414329
571 99978389485270331244
572 102344261877233384036
573 104762030607071007749
574 107232744652478553216
575 109757472393503424851
576 112337301938270279598
577 114973341453540394240
578 117666719500326401873
579 120418585374472187780
580 123230109452424994873
581 126102483542103058412
582 129036921239097328364
583 132034658288104063387
584 135096952949833035744
585 138225086373288720835
586 141420362973668217086
587 144684110815779484208
588 148017682003222510966
589 151422453073237789483
590 154899825397471159682
591 158451225588552542890
592 162078105912749822607
593 165781944708588471205
594 169564246811704988782
595 173426543985825439794
596 177370395360135993289
597 181397387872943446746
598 185509136721891646844
599 189707285820632680726
600 193993508262225537702
601 198369506789153865709
602 202837014270248748388
603 207397794184400803514
604 212053641111354690413
605 216806381229471124587
606 221657872820748475974
607 226610006782996247972
608 231664707149451352059
609 236823931615730494362
610 242089672074417057122
611 247463955157168124924
612 252948842784654029830
613 258546432724208335039
614 264258859155508493430
615 270088293244166014866
616 276036943723545201043
617 282107057484697018953
618 288300920174726176278
619 294620856803479121638
620 301069232358878879101
621 307648452430786352810
622 314360963843729154824
623 321209255298369428730
624 328195858022059983134
625 335323346428361261641
626 342594338785867460496
627 350011497896222622746
628 357577531781673857241
629 365295194382043811831
630 373167286261478154630
631 381196655324841666208
632 389386197544134691847
633 397738857694794957538
634 406257630102265547862
635 414945559398695243240
636 423805741290150840214
637 432841323334216564499
638 442055505728359231434
639 451451542108935720874
640 461032740361230461160
641 470802463440390513022
642 480764130203663218833
643 490921216253794954112
644 501277254794005444798
645 511835837494397546034
646 522600615370215983230
647 533575299671824495063
648 544763662786813738725
649 556169539154111037573
650 567796826190514216125
651 579649485229511157450
652 591731542472825552256
653 604047089954540956050
654 616600286518253996916
655 629395358807110383663
656 642436602267173419368
657 655728382163988894236
658 669275134612795156028
659 683081367622244057286
660 697151662152091950695
661 711490673184716516614
662 726103130810938227042
663 740993841329992227464
664 756167688364140327252
665 771629633987770607657
666 787384719871473445554
667 803438068440952399300
668 819794884051257674789
669 836460454176202657075
670 853440150613462544640
671 870739430705205158702
672 888363838574773653220
673 906319006379260711037
674 924610655578505808315
675 943244598220357065512
676 962226738242728207423
677 981563072792303845141
678 1001259693560422792068
679 1021322788135994891541
680 1041758641375992935479
681 1062573636793364240568
682 1083774257962925710934
683 1105367089945075954628
684 1127358820727900714089
685 1149756242687507347267
686 1172566254067163842836
687 1195795860475090593914
688 1219452176401479439536
689 1243542426754590711669
690 1268073948416515711079
691 1293054191818443922052
692 1318490722536045805315
693 1344391222904798968257
694 1370763493655882065420
695 1397615455572466638161
696 1424955151167030304147
697 1452790746379534844028
698 1481130532297091932322
699 1509982926894962835628
700 1539356476799528362865
701 1569259859073063437931
702 1599701883020977711196
703 1630691492021344539166
704 1662237765377393905036
705 1694349920192794293945
706 1727037313270398488523
707 1760309443034292517612
708 1794175951475821899663
709 1828646626123437487397
710 1863731402037049749320
711 1899440363826721298389
712 1935783747696412931299
713 1972771943512600409904
714 2010415496898492598934
715 2048725111353671166240
716 2087711650399881691617
717 2127386139752811552143
718 2167759769520583972412
719 2208843896428806985498
720 2250650046072922083445
721 2293189915197678266246
722 2336475374004504578246
723 2380518468486593706106
724 2425331422792485805336
725 2470926641617968422285
726 2517316712627081293918
727 2564514408902058040062
728 2612532691422992918938
729 2661384711577068381492
730 2711083813698148271135
731 2761643537636558798764
732 2813077621359891875864
733 2865400003584639248754
734 2918624826439509410674
735 2972766438160239363245
736 3027839395816752676537
737 3083858468072493109983
738 3140838637976785050077
739 3198795105790054109718
740 3257743291842776597300
741 3317698839427977030436
742 3378677617728174210296
743 3440695724776580764571
744 3503769490453474878436
745 3567915479517553127500
746 3633150494673183042338
747 3699491579673382599362
748 3766956022459444941313
749 3835561358337039998512
750 3905325373189730180376
751 3976266106729717056990
752 4048401855786789574582
753 4121751177635275883385
754 4196332893359988983102
755 4272166091260972657574
756 4349270130298037683049
757 4427664643574914225271
758 4507369541864010559794
759 4588405017171608922146
760 4670791546344508363567
761 4754549894717930081754
762 4839701119805730740498
763 4926266575032723815424
764 5014267913510175040688
765 5103727091854276819559
766 5194666374048667962366
767 5287108335350824261598
768 5381075866243386298941
769 5476592176430255347453
770 5573680798878545058272
771 5672365593906203855550
772 5772670753316433096377
773 5874620804578699892780
774 5978240615057491813492
775 6083555396288617644580
776 6190590708304201600320
777 6299372464006197091639
778 6409926933589568027420
779 6522280749014969584254
780 6636460908532098685777
781 6752494781253529594407
782 6870410111780244693874
783 6990235024878659228572
784 7111998030210373248849
785 7235728027114455304720
786 7361454309443491887876
787 7489206570453230430548
788 7619014907747050345276
789 7750909828275096268263
790 7884922253389331971618
791 8021083523954331954016
792 8159425405515110904755
793 8299980093521790814331
794 8442780218612430850530
795 8587858851953826070610
796 8735249510641600757233
797 8884986163159427124840
798 9037103234898696293048
799 9191635613738479181670
800 9348618655687129281599
801 9508088190585347193818
802 9670080527872103323137
803 9834632462413220756228
804 10001781280394040752022
805 10171564765275979747255
806 10344021203818401626204
807 10519189392165640304619
808 10697108642000597422454
809 10877818786764757700474
810 11061360187946073690515
811 11247773741434544089352
812 11437100883946983846483
813 11629383599520791759662
814 11824664426078241761028
815 12022986462061111054185
816 12224393373137172570106
817 12428929398978392611471
818 12636639360112362903746
819 12847568664846816055976
820 13061763316268781788626
821 13279269919318213924819
822 13500135687937694941520
823 13724408452298028974834
824 13952136666101359283425
825 14183369413961629183391
826 14418156418864024472208
827 14656548049703245679828
828 14898595328902249881273
829 15144349940111319231568
830 15393864235989126148586
831 15647191246065632664160
832 15904384684688545578399
833 16165498959053145212060
834 16430589177317240708359
835 16699711156801078485122
836 16972921432273958778402
837 17250277264327417916029
838 17531836647836733785712
839 17817658320510621670069
840 18107801771530909433267
841 18402327250282038974713
842 18701295775172237834794
843 19004769142546187508038
844 19312809935691065041364
845 19625481533935794016912
846 19942848121845384327586
847 20264974698510229667534
848 20591927086932244671431
849 20923771943507720935929
850 21260576767608817630959
851 21602409911263545036752
852 21949340588936214087555
853 22301438887408189282702
854 22658775775760953039090
855 23021423115461329165877
856 23389453670550876394388
857 23762941117939334342601
858 24141960057804136277488
859 24526586024095882182546
860 24916895495151821732460
861 25312965904417219164559
862 25714875651276710496532
863 26122704111995503466504
864 26536531650772567153182
865 26956439630905672819028
866 27382510426070436735505
867 27814827431713263185678
868 28253475076560341892690
869 28698538834242610071778
870 29150105235038871048686
871 29608261877736957496351
872 30073097441615194770864
873 30544701698544030169246
874 31023165525210122618684
875 31508580915462770661344
876 32001040992784977119757
877 32500640022889067025420
878 33007473426439161697382
879 33521637791900438473980
880 34043230888517518305952
881 34572351679421887949653
882 35109100334870766268106
883 35653578245617298527028
884 36205888036414528888251
885 36766133579653047980245
886 37334420009134770692514
887 37910853733982781927822
888 38495542452689710070134
889 39088595167304579819197
890 39690122197760646143603
891 40300235196344137614270
892 40919047162306481108483
893 41546672456619912684055
894 42183226816879090049408
895 42828827372348625420321
896 43483592659159159260856
897 44147642635651936809179
898 44821098697874513642701
899 45504083695227567130074
900 46196721946265483805620
901 46899139254650675528673
902 47611462925264368769078
903 48333821780473795803903
904 49066346176558577447173
905 49809168020296241154761
906 50562420785709670389600
907 51326239530976474546544
908 52100760915503081246660
909 52886123217163556361324
910 53682466349706000277632
911 54489931880326501165632
912 55308663047413571252904
913 56138804778463022205612
914 56980503708166253879604
915 57833908196671928716032
916 58699168348024012513308
917 59576436028776201766884
918 60465864886785725508688
919 61367610370186559067244
920 62281829746545086342628
921 63208682122198222835032
922 64148328461777117924192
923 65100931607916423375792
924 66066656301152296851892
925 67045669200009144785004
926 68038138901278281187120
927 69044235960488557228416
928 70064132912572145608040
929 71098004292725553024796
930 72146026657469096602004
931 73208378605904891810064
932 74285240801176673099404
933 75376795992131468958644
934 76483229035186506137584
935 77604726916401383383020
936 78741478773758897496932
937 79893675919654615235928
938 81061511863598582729792
939 82245182335129285714128
940 83444885306943306251476
941 84660821018240762910092
942 85893191998290070188624
943 87142203090212077763552
944 88408061474987181087464
945 89690976695685483894556
946 90991160681923613701012
947 92308827774548326812336
948 93644194750550513121372
949 94997480848209758387236
950 96368907792473131711488
951 97758699820568329017804
952 99167083707854934122836
953 100594288793913901271704
954 102040547008879079983616
955 103506092900010907471232
956 104991163658516099395284
957 106495999146613523105148
958 108020841924850094912144
959 109565937279666908174688
960 111131533251219493541625
961 112717880661452390733437
962 114325233142432032202631
963 115953847164938090585302
964 117603982067317351979641
965 119275900084600289851068
966 120969866377884413165434
967 122686149063984625482821
968 124425019245354679813539
969 126186751040279990153896
970 127971621613345948041537
971 129779911206181977122464
972 131611903168485577126303
973 133467883989326562285339
974 135348143328735811095838
975 137252974049578756912595
976 139182672249717948306637
977 141137537294464973794126
978 143117871849326092824182
979 145123981913041893447746
980 147156176850925384678573
981 149214769428498815564739
982 151300075845433737571156
983 153412415769794573837474
984 155552112372590280072701
985 157719492362634386786992
986 159914886021718021477244
987 162138627240096268890758
988 164391053552292481472884
989 166672506173220925662213
990 168983330034632446305440
991 171323873821883505985212
992 173694490011033394508846
993 176095534906269936451112
994 178527368677668564294951
995 180990355399285112938478
996 183484863087587217535994
997 186011263740224742339066
998 188569933375144137935534
999 191161252070047183895881
1000 193785604002199087229948