0 1
1 1
2 2
3 3
4 4
5 5
6 8
7 8
8 12
9 14
10 18
11 21
12 29
13 29
14 40
15 47
16 56
17 62
18 83
19 86
20 111
21 124
22 146
23 166
24 207
25 217
26 267
27 300
28 352
29 389
30 471
31 505
32 604
33 668
34 772
35 860
36 1015
37 1085
38 1279
39 1419
40 1622
41 1780
42 2072
43 2242
44 2595
45 2858
46 3231
47 3563
48 4092
49 4421
50 5057
51 5557
52 6250
53 6857
54 7786
55 8453
56 9565
57 10465
58 11709
59 12830
60 14450
61 15654
62 17579
63 19237
64 21398
65 23363
66 26115
67 28334
68 31617
69 34471
70 38187
71 41639
72 46260
73 50137
74 55626
75 60588
76 66805
77 72673
78 80350
79 87075
80 96141
81 104428
82 114737
83 124680
84 137254
85 148504
86 163246
87 177149
88 194008
89 210326
90 230669
91 249395
92 273177
93 295838
94 323023
95 349758
96 382240
97 412716
98 450656
99 487359
100 530714
101 573553
102 624973
103 674223
104 734030
105 792464
106 860817
107 929101
108 1009703
109 1087780
110 1181214
111 1273572
112 1380339
113 1487512
114 1612595
115 1735537
116 1880084
117 2024084
118 2189279
119 2356287
120 2548823
121 2739531
122 2961433
123 3184423
124 3437638
125 3694714
126 3988544
127 4282485
128 4620345
129 4961513
130 5346604
131 5739490
132 6184475
133 6632559
134 7142900
135 7661495
136 8242316
137 8836969
138 9506061
139 10184059
140 10949398
141 11729968
142 12599925
143 13494184
144 14492766
145 15509331
146 16648954
147 17816854
148 19110606
149 20443454
150 21924129
151 23438488
152 25124515
153 26857441
154 28768635
155 30743375
156 32924382
157 35162820
158 37641579
159 40197315
160 43002929
161 45906801
162 49100310
163 52389227
164 56011276
165 59754017
166 63847503
167 68093859
168 72742678
169 77541551
170 82804011
171 88254265
172 94193082
173 100362016
174 107091182
175 114055204
176 121658455
177 129546193
178 138115263
179 147029279
180 156717947
181 166761773
182 177690226
183 189046866
184 201345102
185 214151703
186 228029718
187 242442598
188 258070865
189 274329732
190 291892218
191 310200264
192 329981946
193 350552019
194 372792363
195 395958502
196 420916728
197 446954062
198 475017946
199 504236361
200 535739077
201 568579746
202 603885308
203 640746091
204 680377595
205 721677008
206 766099144
207 812448425
208 862168436
209 914103583
210 969827753
211 1027946982
212 1090317148
213 1155431144
214 1225150245
215 1298014600
216 1376034084
217 1457458711
218 1544665477
219 1635759764
220 1733119150
221 1834903103
222 1943697385
223 2057308233
224 2178750688
225 2305655866
226 2441071886
227 2582692680
228 2733806279
229 2891672220
230 3060137815
231 3236246612
232 3423874137
233 3620136617
234 3829236156
235 4047765276
236 4280585525
237 4524027607
238 4783034994
239 5054013676
240 5342292774
241 5643645753
242 5964245997
243 6299547701
244 6655805453
245 7028565128
246 7424601657
247 7838697468
248 8278629579
249 8738785843
250 9227115201
251 9738107059
252 10280321848
253 10847334252
254 11448971561
255 12078337238
256 12745450149
257 13443532613
258 14183424197
259 14957239377
260 15777325293
261 16635227572
262 17543626485
263 18494203016
264 19500594795
265 20553168315
266 21667469528
267 22833181132
268 24066240777
269 25356479289
270 26721108631
271 28148389189
272 29657800185
273 31236789113
274 32905432154
275 34651356120
276 36496153617
277 38425585917
278 40464099892
279 42596477074
280 44847889947
281 47203329660
282 49689954266
283 52290545542
284 55035640090
285 57906872866
286 60935850273
287 64104457990
288 67446673133
289 70941755559
290 74627937471
291 78483119896
292 82546829290
293 86797281683
294 91277056135
295 95961287970
296 100897621353
297 106059606840
298 111496728553
299 117182898053
300 123171278618
301 129432166629
302 136025049775
303 142918380440
304 150173869061
305 157760441580
306 165744537304
307 174090856443
308 182873388681
309 192054677394
310 201711800546
311 211807899580
312 222425738994
313 233523548250
314 245193460427
315 257391244392
316 270212813203
317 283614713456
318 297700133375
319 312419885252
320 327888375990
321 344053620152
322 361035130581
323 378781929834
324 397422269794
325 416898594737
326 437353064587
327 458724962957
328 481162733173
329 504606951351
330 529217193066
331 554926468514
332 581911010971
333 610100312698
334 639678901774
335 670578011798
336 702995621862
337 736854340960
338 772372759576
339 809469566969
340 848373609909
341 889005880968
342 931612230749
343 976103876719
344 1022751321495
345 1071461585316
346 1122518602204
347 1175832442710
348 1231707647936
349 1290043245694
350 1351174249058
351 1414995217252
352 1481857727418
353 1551660428376
354 1624780752405
355 1701105052320
356 1781047344258
357 1864489400627
358 1951866699871
359 2043066365243
360 2138555315520
361 2238207089078
362 2342533666769
363 2451404066739
364 2565356671381
365 2684267683669
366 2808714864643
367 2938559595872
368 3074433817770
369 3216194650989
370 3364508025134
371 3519240555304
372 3681106021919
373 3849955131886
374 4026568202924
375 4210792449872
376 4403450099947
377 4604400963036
378 4814527031538
379 5033671212559
380 5262795685255
381 5501741158571
382 5751523222296
383 6011999203862
384 6284257298739
385 6568137530904
386 6864826519760
387 7174164121499
388 7497402864795
389 7834404371780
390 8186511640889
391 8553569067222
392 8937038305860
393 9336766695715
394 9754299242324
395 10189511947669
396 10644059935686
397 11117802993570
398 11612541760621
399 12128143262979
400 12666511000625
401 13227549510573
402 13813299036744
403 14423650086518
404 15060818342381
405 15724707995733
406 16417664305100
407 17139640369456
408 17893148049062
409 18678130196207
410 19497313684675
411 20350663697879
412 21241066758735
413 22168551727297
414 23136211264321
415 24144070289237
416 25195481191201
417 26290503113419
418 27432688690171
419 28622179412347
420 29862779325583
421 31154635278353
422 32501869108930
423 33904677871292
424 35367429660678
425 36890428235800
426 38478352366587
427 40131524551502
428 41855007831984
429 43649195940952
430 45519459774069
431 47466330551275
432 49495557893054
433 51607710677049
434 53809008003719
435 56100118119041
436 58487638703694
437 60972414906074
438 63561511535968
439 66255836889789
440 69063024092714
441 71984117487276
442 75027221480447
443 78193607255878
444 81491948446573
445 84923614550312
446 88497973276911
447 92216577899467
448 96089375246698
449 100118208446412
450 104313725404181
451 108677914100007
452 113222262777743
453 117949005024477
454 122870347358640
455 127988893470774
456 133317704468856
457 138859590584889
458 144628638617535
459 150627983353183
460 156872593617945
461 163366075332809
462 170124447691143
463 177151603808625
464 184464804789473
465 192068370507865
466 199980653458926
467 208206571704984
468 216765758055156
469 225663522294132
470 234921012164833
471 244544093907041
472 254555253593822
473 264961115531299
474 275785736382316
475 287036267964074
476 298738602380880
477 310900613087711
478 323549844196539
479 336695126914510
480 350365919448310
481 364571754550040
482 379344327246161
483 394694101016116
484 410654793708979
485 427238077725362
486 444480016230049
487 462393205568839
488 481016419598144
489 500363448928063
490 520475559054557
491 541368062346087
492 563085080698202
493 585643133850463
494 609089643735958
495 633442657157024
496 658752644448244
497 685039564763545
498 712357383548797
499 740727625234329
500 770208255235272
501 800822742460032
502 832632798328732
503 865664290129554
504 899983182789700
505 935617362798395
506 972637662020409
507 1011074434197302
508 1051003089142315
509 1092456982154071
510 1135516721294656
511 1180218251182460
512 1226648077374987
513 1274845265318669
514 1324901934047291
515 1376860900335279
516 1430820606574780
517 1486827175036393
518 1544986218589531
519 1605347793456445
520 1668024365391273
521 1733070670313004
522 1800606890305416
523 1870691962538038
524 1943454754838689
525 2018959152513349
526 2097342411818833
527 2178674245794731
528 2263101291080370
529 2350698579023688
530 2441623299122299
531 2535956688352573
532 2633866163367789
533 2735440207408252
534 2840857667549872
535 2950213738389394
536 3063700046945485
537 3181419552580317
538 3303576379676071
539 3430282481113287
540 3561755866792477
541 3698116930557215
542 3839599195109133
543 3986332747168121
544 4138566325899229
545 4296441167246856
546 4460222910900115
547 4630063377613421
548 4806246986145149
549 4988937629910679
550 5178438291631764
551 5374926662885676
552 5578726238085170
553 5790027946919899
554 6009178056457912
555 6236382505397551
556 6472010138882763
557 6716283948899883
558 6969597715168892
559 7232190941305205
560 7504484961325765
561 7786737900941665
562 8079398592929466
563 8382746209316772
564 8697259815689675
565 9023239135452749
566 9361196620678534
567 9711455057191178
568 10074560301681265
569 10450861076908597
570 10840939947788647
571 11245171156207006
572 11664177636513292
573 12098362143738943
574 12548388231199337
575 13014690579762230
576 13497977212189644
577 13998714433761507
578 14517659136596941
579 15055312814448179
580 15612481643831309
581 16189706363710169
582 16787847074964465
583 17407483628840381
584 18049535173030675
585 18714624923689792
586 19403731870450107
587 20117527411183162
588 20857055798594560
589 21623036711758007
590 22416585816603528
591 23238476147028315
592 24089895884635590
593 24971677145540842
594 25885087150048948
595 26831017515133259
596 27810821685018891
597 28825456828689113
598 29876364313719659
599 30964573665546498
600 32091621816093462
601 33258611493802817
602 34467183806587382
603 35718521905196035
604 37014373307062488
605 38356009683485646
606 39745294151104818
607 41183588297694933
608 42672880920984461
609 44214632137417798
610 45810959583630780
611 47463431541293517
612 49174305267577034
613 50945259324830700
614 52778702660575550
615 54676434398116071
616 56641019226923337
617 58674388297159275
618 60779274987830123
619 62957745501684727
620 65212716067051576
621 67546400215594915
622 69961902480256828
623 72461597368805209
624 75048792935017649
625 77726028858479930
626 80496833663405603
627 83363926847900020
628 86331064285071622
629 89401161534298968
630 92578220071023295
631 95865357183153748
632 99266839857840002
633 102786004599140953
634 106427392898456328
635 110194579815736555
636 114092402846735432
637 118124683115188262
638 122296577925969209
639 126612175329301894
640 131076963654367179
641 135695320913907342
642 140473092211597791
643 145414955328053767
644 150527140142754480
645 155814649112028278
646 161284111277950527
647 166940881194446444
648 172792017429079719
649 178843239285043836
650 185102068311360380
651 191574618288890876
652 198268891525131970
653 205191428937535287
654 212350749917535907
655 219753838698984333
656 227409771176150135
657 235326010370416429
658 243512211145057854
659 251976354182373617
660 260728716194072717
661 269777816060180231
662 279134599382735603
663 288808165557040569
664 298810156657027399
665 309150298889630283
666 319840982066846342
667 330892585069831327
668 342318300924365358
669 354129211656546420
670 366339347977997174
671 378960550183766782
672 392007747218255776
673 405493570048705376
674 419433911999372101
675 433842254904929655
676 448735498594499763
677 464128041386593077
678 480037861924144263
679 496480315373808403
680 513474537260306861
681 531036911385909008
682 549187782326709305
683 567944640619217899
684 587329125334697428
685 607359883841016705
686 628059942742731753
687 649449191794139189
688 671552108596366202
689 694389918223489552
690 717988651218175057
691 742370929888360195
692 767564447563921553
693 793593325753195735
694 820486998609766862
695 848271197421447762
696 876977217710819760
697 906632476781683359
698 937270262315912111
699 968919799086566780
700 1001616461518543971
701 1035391413415677133
702 1070282259602778183
703 1106322196493539309
704 1143551213784054086
705 1182004685163305925
706 1221725100865738818
707 1262750168299960304
708 1305125048128731116
709 1348889896002104522
710 1394092726793984381
711 1440776316638900614
712 1488991674328336791
713 1538784382507695702
714 1590208646149614260
715 1643312994211793195
716 1698155044998479919
717 1754786478774119262
718 1813268497165383063
719 1873656152831350647
720 1936014469945821494
721 2000402043833708929
722 2066887979320114441
723 2135534658284205171
724 2206415470936892424
725 2279596848460303634
726 2355156751036585107
727 2433165866008953617
728 2513707028503253724
729 2596855472064468755
730 2682699154842354630
731 2771318168727195422
732 2862805931415673547
733 2957247643982434140
734 3054742545855662806
735 3155381292119796890
736 3259269242011583345
737 3366502875307333725
738 3477194070991932059
739 3591445437055641223
740 3709375800167567656
741 3831094306358897459
742 3956727089804317755
743 4086390274632930975
744 4220217775362419223
745 4358333060924649657
746 4500878334034135248
747 4647984895226972914
748 4799803666735741585
749 4956474302920028028
750 5118157006948473738
751 5285000229270950567
752 5457174053893241075
753 5634836305425508735
754 5818167467706015569
755 6007335359040433076
756 6202531526735776494
757 6403934315328306879
758 6611747046901564398
759 6826159278301602696
760 7047386727209401167
761 7275630897527053333
762 7511120689698970407
763 7754070194974686807
764 8004722336553797036
765 8263304607070558625
766 8530074697473840343
767 8805274372731641477
768 9089177021650357536
769 9382039450289919976
770 9684151740470658101
771 9995786704750428742
772 10317252007317985507
773 10648837499325285403
774 10990869529525122713
775 11343655909487664235
776 11707542847412434680
777 12082857259681972724
778 12469966278434920067
779 12869217147323206381
780 13280999224212036898
781 13705681184056633872
782 14143676001080275357
783 14595375137527378379
784 15061216452442793708
785 15541615642855202205
786 16037036993957075382
787 16547921758110059713
788 17074762287692875047
789 17618026996353694334
790 18178237818460785118
791 18755892042163016550
792 19351543003225911093
793 19965718442151426695
794 20599005036822266172
795 21251962881308462521
796 21925213797755192286
797 22619352260635322070
798 23335037388519947662
799 24072899919377079089
800 24833638557281985947
801 25617922553519801892
802 26426492345191675844
803 27260058093767882819
804 28119404508383953296
805 29005284905952016533
806 29918530972552714865
807 30859941841503722155
808 31830398726635085316
809 32830749410898509117
810 33861927636511475574
811 34924832510406412244
812 36020453491772034030
813 37149744157492156996
814 38313752717541561712
815 39513490566446136534
816 40750068202965523286
817 42024558021600073009
818 43338136574420726402
819 44691940973399051699
820 46087217422094978238
821 47525171703905202951
822 49007123851192736593
823 50534352102133936383
824 52108254752921693718
825 53730186887626729477
826 55401629338406169833
827 57124018702980860736
828 58898923271615114397
829 60727865649549878884
830 62612506816774116396
831 64554460570378445835
832 66555485639616242405
833 68617292521678010366
834 70741743501357883921
835 72930651109300810645
836 75185987345619083540
837 77509672892389500646
838 79903795462286103780
839 82370390385825360791
840 84911667925192241471
841 87529784383890204006
842 90227079833332451156
843 93005838766511165971
844 95868538157087455627
845 98817598347777615233
846 101855641272518527536
847 104985230617416211874
848 108209141818636960890
849 111530090414001725705
850 114951013736616046991
851 118474788203690513060
852 122104522526782001700
853 125843262874804266293
854 129694299396354702719
855 133660858039006896937
856 137746420304472433908
857 141954402553469016324
858 146288488805650587376
859 150752296331247475539
860 155349723494967606670
861 160084600287985005449
862 164961051138669920346
863 169983131280959753592
864 175155204334492435304
865 180481563185080341689
866 185966824559040360541
867 191615532900835935547
868 197432571868693937944
869 203422752203306402907
870 209591239939409158352
871 215943126773809617521
872 222483877467947771637
873 229218881041513400895
874 236153917298685989831
875 243294689920042043496
876 250647311899158592915
877 258217818884359472770
878 266012676279239312520
879 274038270952667576885
880 282301439944693831238
881 290808941733293767573
882 299568006325430777412
883 308585784226275742286
884 317869920976973698708
885 327427981748030171275
886 337268050276123758502
887 347398130361952931811
888 357826768981009736908
889 368562432636969622513
890 379614158050838286154
891 390990901035886297975
892 402702214731555939436
893 414757572417389782559
894 427167073062666522290
895 439940735776953128501
896 453089236458893045254
897 466623171304761061004
898 480553824541856387542
899 494892402519956756309
900 509650832299579869760
901 524840963782991148744
902 540475403361146864117
903 556566681191995126777
904 573128119913968188172
905 590172968757779915831
906 607715307097938445303
907 625769142541390586578
908 644349353987674625720
909 663470750499587657424
910 683149053909251210336
911 703399920282736665857
912 724239961847832098142
913 745685727898719145259
914 767754771232233183137
915 790464584912477669351
916 813833713287298974582
917 837880646612302730566
918 862624976433098672812
919 888086244529409071186
920 914285148423177057014
921 941242340689227965566
922 968979684702965067665
923 997519006464552713658
924 1026883400384802826998
925 1057095929716160544603
926 1088180988770750616704
927 1120162947530000473594
928 1153067570460208625539
929 1186920607666557343074
930 1221749270125909902379
931 1257580763005247017972
932 1294443824407307562469
933 1332367195966085991839
934 1371381225331032789012
935 1411516276576460815104
936 1452804396270347373903
937 1495277658862176802866
938 1538969904210650959880
939 1583915012480163349325
940 1630148713426819198214
941 1677706793595392358055
942 1726626977244574683487
943 1776947060429667001431
944 1828706872301242849815
945 1881946330038094687185
946 1936707480904339762999
947 1993032481019988293856
948 2050965718103575500576
949 2110551708103367403460
950 2171837308314112709364
951 2234869525120154556819
952 2299697817971839369253
953 2366371821525423454054
954 2434943740462368999009
955 2505465979338909409262
956 2577993638990423528457
957 2652582046643501604402
958 2729289354511571497437
959 2808173973678489828371
960 2889297274940538229766
961 2972720919082239496237
962 3058509671873028211877
963 3146728622416748609304
964 3237446113047414570709
965 3330730849605718351510
966 3426654946374956670698
967 3525290920032638414083
968 3626714862826571596929
969 3731003311024080454252
970 3838236547237591192872
971 3948495347481438329420
972 4061864412892000875184
973 4178428986290484667596
974 4298278427923882782249
975 4421502691290806162796
976 4548196044001342292622
977 4678453407369487004844
978 4812374222765295143853
979 4950058644803911614584
980 5091611569396266882068
981 5237138669237652797874
982 5386750584874803819773
983 5540558807291710067388
984 5698680032516095373040
985 5861231880088336658481
986 6028337429158113693193
987 6200120760233952477540
988 6376711674344724602076
989 6558241063318544921620
990 6744845812714883053283
991 6936663988112858025431
992 7133839941692280754043
993 7336519300638794330383
994 7544854279242535432711
995 7758998475001568261736
996 7979112387156023043299
997 8205358006684054679811
998 8437904563283949490708
999 8676922893775966827861
1000 8922591419744217428159