0 1
1 1
2 2
3 3
4 5
5 7
6 11
7 15
8 22
9 29
10 40
11 51
12 69
13 86
14 112
15 139
16 176
17 214
18 268
19 321
20 394
21 470
22 567
23 668
24 800
25 933
26 1103
27 1281
28 1498
29 1725
30 2006
31 2293
32 2643
33 3010
34 3443
35 3897
36 4438
37 4995
38 5652
39 6341
40 7135
41 7967
42 8932
43 9930
44 11079
45 12283
46 13645
47 15071
48 16692
49 18372
50 20271
51 22258
52 24474
53 26791
54 29384
55 32074
56 35071
57 38202
58 41654
59 45258
60 49242
61 53375
62 57927
63 62675
64 67861
65 73267
66 79183
67 85318
68 92012
69 98983
70 106538
71 114401
72 122935
73 131779
74 141354
75 151310
76 162029
77 173168
78 185174
79 197606
80 210978
81 224861
82 239724
83 255147
84 271673
85 288770
86 307057
87 326016
88 346215
89 367146
90 389461
91 412525
92 437076
93 462495
94 489462
95 517370
96 546993
97 577581
98 610005
99 643533
100 678971
101 715600
102 754331
103 794286
104 836484
105 880067
106 925981
107 973383
108 1023336
109 1074820
110 1129018
111 1184932
112 1243664
113 1304233
114 1367870
115 1433399
116 1502183
117 1573070
118 1647334
119 1723842
120 1804010
121 1886490
122 1972843
123 2061748
124 2154668
125 2250303
126 2350271
127 2453037
128 2560378
129 2670788
130 2785937
131 2904342
132 3027842
133 3154698
134 3286922
135 3422807
136 3564248
137 3709563
138 3860831
139 4016092
140 4177613
141 4343468
142 4515797
143 4692702
144 4876522
145 5065058
146 5260852
147 5461742
148 5670133
149 5883893
150 6105642
151 6332923
152 6568575
153 6810181
154 7060432
155 7316944
156 7582639
157 7854783
158 8136534
159 8425201
160 8723783
161 9029624
162 9345971
163 9669793
164 10004590
165 10347377
166 10701483
167 11063961
168 11438406
169 11821469
170 12217016
171 12621747
172 13039345
173 13466551
174 13907332
175 14358000
176 14822811
177 15298129
178 15788015
179 16288877
180 16805079
181 17332571
182 17876025
183 18431447
184 19003301
185 19587640
186 20189250
187 20803697
188 21436095
189 22082069
190 22746512
191 23425099
192 24123065
193 24835568
194 25568191
195 26316155
196 27084808
197 27869424
198 28675714
199 29498404
200 30343574
201 31206016
202 32091561
203 32995058
204 33922722
205 34868822
206 35839963
207 36830484
208 37846727
209 38883091
210 39946324
211 41030212
212 42141915
213 43275293
214 44437228
215 45621644
216 46835851
217 48073126
218 49341214
219 50633470
220 51957346
221 53306264
222 54688127
223 56095676
224 57537272
225 59005738
226 60509126
227 62040330
228 63607877
229 65203944
230 66837540
231 68500928
232 70202792
233 71935470
234 73708145
235 75512402
236 77357930
237 79236404
238 81157172
239 83111988
240 85110724
241 87144343
242 89223248
243 91338497
244 93500135
245 95699303
246 97946595
247 100232323
248 102567638
249 104942951
250 107369038
251 109836397
252 112356379
253 114918614
254 117535036
255 120195379
256 122911184
257 125672276
258 128490798
259 131355667
260 134279636
261 137251730
262 140284291
263 143366440
264 146511148
265 149706587
266 152966365
267 156278767
268 159656972
269 163089365
270 166589782
271 170145617
272 173771371
273 177454556
274 181209225
275 185022995
276 188910604
277 192858635
278 196882520
279 200968965
280 205132935
281 209361245
282 213669574
283 218043660
284 222499905
285 227024175
286 231632385
287 236310515
288 241075224
289 245911370
290 250836365
291 255835200
292 260924780
293 266090215
294 271349184
295 276685630
296 282118015
297 287630420
298 293240780
299 298933300
300 304726720
301 310604031
302 316584787
303 322652123
304 328825045
305 335086817
306 341457281
307 347918440
308 354490982
309 361157059
310 367936790
311 374812461
312 381805059
313 388895561
314 396105832
315 403417004
316 410850351
317 418387144
318 426049558
319 433817506
320 441714074
321 449719335
322 457855762
323 466103573
324 474486175
325 482982378
326 491616533
327 500367616
328 509259343
329 518270840
330 527426791
331 536704863
332 546130718
333 555682195
334 565384298
335 575215022
336 585200373
337 595316835
338 605591427
339 616000811
340 626571325
341 637279792
342 648153587
343 659167970
344 670351364
345 681679213
346 693179235
347 704827041
348 716651422
349 728626372
350 740781766
351 753091788
352 765585584
353 778237511
354 791077824
355 804079209
356 817273041
357 830632202
358 844187314
359 857911438
360 871836342
361 885933360
362 900235417
363 914714050
364 929401406
365 944269207
366 959350783
367 974616073
368 990099602
369 1005771518
370 1021665543
371 1037752016
372 1054065880
373 1070575634
374 1087317454
375 1104260055
376 1121438784
377 1138822553
378 1156447969
379 1174282046
380 1192362663
381 1210657056
382 1229202249
383 1247965682
384 1266985678
385 1286227720
386 1305731442
387 1325462556
388 1345459815
389 1365689141
390 1386190626
391 1406928175
392 1427943231
393 1449199935
394 1470738822
395 1492524250
396 1514598133
397 1536922751
398 1559541410
399 1582416633
400 1605590791
401 1629026630
402 1652767941
403 1676775331
404 1701094024
405 1725684877
406 1750592151
407 1775776933
408 1801284946
409 1827075075
410 1853194518
411 1879602417
412 1906344979
413 1933381583
414 1960759940
415 1988437164
416 2016462483
417 2044793275
418 2073477749
419 2102473527
420 2131830365
421 2161503555
422 2191544413
423 2221908503
424 2252646093
425 2283712998
426 2315161076
427 2346943747
428 2379114473
429 2411626953
430 2444533572
431 2477788287
432 2511445117
433 2545455558
434 2579875277
435 2614656057
436 2649852458
437 2685416528
438 2721404506
439 2757765912
440 2794558678
441 2831732618
442 2869344527
443 2907344492
444 2945791032
445 2984631638
446 3023926567
447 3063623612
448 3103781863
449 3144349393
450 3185387062
451 3226840278
452 3268771685
453 3311127001
454 3353967672
455 3397239704
456 3441006359
457 3485210908
458 3529918444
459 3575072556
460 3620737108
461 3666855984
462 3713494911
463 3760594968
464 3808223760
465 3856322692
466 3904958108
467 3954071716
468 4003731771
469 4053877104
470 4104577896
471 4155773312
472 4207532240
473 4259794156
474 4312629907
475 4365976020
476 4419905316
477 4474354664
478 4529395560
479 4584965192
480 4641137064
481 4697845341
482 4755165550
483 4813032207
484 4871519481
485 4930562215
486 4990236635
487 5050474487
488 5111354070
489 5172807489
490 5234911652
491 5297598999
492 5360948545
493 5424889558
494 5489503176
495 5554719035
496 5620616848
497 5687126594
498 5754330144
499 5822154229
500 5890682894
501 5959843246
502 6029717871
503 6100234228
504 6171477112
505 6243370657
506 6316001883
507 6389295309
508 6463336462
509 6538050221
510 6613524374
511 6689680397
512 6766608355
513 6844230118
514 6922634223
515 7001742909
516 7081647026
517 7162265331
518 7243691004
519 7325843205
520 7408813551
521 7492521579
522 7577061272
523 7662348606
524 7748479947
525 7835371683
526 7923118581
527 8011637415
528 8101025372
529 8191195584
530 8282247675
531 8374095198
532 8466836142
533 8560384455
534 8654840600
535 8750114802
536 8846310015
537 8943336894
538 9041296722
539 9140100558
540 9239852214
541 9340458943
542 9442027103
543 9544464387
544 9647875445
545 9752168383
546 9857450435
547 9963625818
548 10070804368
549 10178890751
550 10287993058
551 10398016377
552 10509071439
553 10621059359
554 10734093526
555 10848075514
556 10963116929
557 11079119776
558 11196198358
559 11314250622
560 11433393586
561 11553525665
562 11674762056
563 11797001615
564 11920362293
565 12044738802
566 12170251865
567 12296796672
568 12424492087
569 12553233750
570 12683143337
571 12814112257
572 12946265016
573 13079493511
574 13213920350
575 13349437890
576 13486171609
577 13624009545
578 13763080065
579 13903271705
580 14044710895
581 14187286640
582 14331128299
583 14476120470
584 14622395460
585 14769838375
586 14918579545
587 15068504555
588 15219746724
589 15372187140
590 15525962130
591 15680953300
592 15837294960
593 15994869205
594 16153813394
595 16314005035
596 16475584555
597 16638429990
598 16802679710
599 16968212250
600 17135169090
601 17303424086
602 17473121847
603 17644136768
604 17816611360
605 17990420527
606 18165709951
607 18342349765
608 18520488842
609 18699997864
610 18881023565
611 19063437146
612 19247388574
613 19432744186
614 19619657202
615 19807994519
616 19997907176
617 20189262599
618 20382215123
619 20576627216
620 20772656529
621 20970166100
622 21169311357
623 21369955878
624 21572258450
625 21776077598
626 21981575488
627 22188611226
628 22397344713
629 22607635605
630 22819647226
631 23033234083
632 23248562943
633 23465488905
634 23684176428
635 23904481172
636 24126571083
637 24350296575
638 24575829102
639 24803019681
640 25032037415
641 25262733892
642 25495281767
643 25729527285
644 25965646674
645 26203486793
646 26443221475
647 26684698161
648 26928094302
649 27173251897
650 27420352036
651 27669237343
652 27920086469
653 28172742631
654 28427388164
655 28683860744
656 28942346411
657 29202683477
658 29465055499
659 29729301393
660 29995608467
661 30263809995
662 30534097057
663 30806303575
664 31080618101
665 31356875172
666 31635267158
667 31915622853
668 32198138467
669 32482643453
670 32769331448
671 33058032531
672 33348944225
673 33641890764
674 33937073579
675 34234317575
676 34533821564
677 34835411088
678 35139288914
679 35445274636
680 35753574998
681 36064010276
682 36376784549
683 36691718742
684 37009020958
685 37328506070
686 37650386227
687 37974476996
688 38300987815
689 38629734911
690 38960931816
691 39294388600
692 39630322911
693 39968545525
694 40309271332
695 40652311780
696 40997885923
697 41345798946
698 41696274090
699 42049117258
700 42404548886
701 42762375560
702 43122821951
703 43485688276
704 43851203464
705 44219168462
706 44589809346
707 44962927758
708 45338754081
709 45717083480
710 46098150668
711 46481751552
712 46868117944
713 47257046458
714 47648773285
715 48043088454
716 48440232558
717 48839996380
718 49242617564
719 49647887612
720 50056048620
721 50466885395
722 50880644508
723 51297111533
724 51716530043
725 52138686343
726 52563828531
727 52991736107
728 53422661718
729 53856385643
730 54293157482
731 54732758257
732 55175442167
733 55620983318
734 56069640532
735 56521188707
736 56975883568
737 57433500768
738 57894300706
739 58358052007
740 58825019768
741 59294973418
742 59768174907
743 60244394432
744 60723898692
745 61206450743
746 61692322057
747 62181276507
748 62673582368
749 63169004293
750 63667815382
751 64169773033
752 64675155195
753 65183720096
754 65695742437
755 66210981239
756 66729716104
757 67251698683
758 67777213504
759 68306013061
760 68838378583
761 69374063369
762 69913353626
763 70455995168
764 71002279205
765 71551952407
766 72105302633
767 72662077371
768 73222569536
769 73786519014
770 74354223801
771 74925424652
772 75500416160
773 76078939911
774 76661295632
775 77247217190
776 77837009471
777 78430407224
778 79027711880
779 79628659032
780 80233555324
781 80842128511
782 81454690475
783 82070969867
784 82691275061
785 83315335565
786 83943465045
787 84575385052
788 85211414570
789 85851276059
790 86495284942
791 87143164549
792 87795235675
793 88451213573
794 89111424436
795 89775584440
796 90444016163
797 91116436664
798 91793173974
799 92473936954
800 93159059114
801 93848250251
802 94541840206
803 95239539673
804 95941684027
805 96647975642
806 97358755453
807 98073726784
808 98793226847
809 99516959876
810 100245268699
811 100977849107
812 101715049570
813 102456566843
814 103202745618
815 103953283574
816 104708531101
817 105468177311
818 106232578319
819 107001424215
820 107775067281
821 108553198544
822 109336176067
823 110123682186
824 110916080772
825 111713055153
826 112514965311
827 113321495525
828 114133011642
829 114949189124
830 115770399710
831 116596319868
832 117427317392
833 118263069715
834 119103950580
835 119949628477
836 120800483125
837 121656184034
838 122517106922
839 123382922278
840 124254011854
841 125130037068
842 126011385733
843 126897720302
844 127789424530
845 128686161863
846 129588322175
847 130495559713
848 131408270498
849 132326109826
850 133249469603
851 134178006132
852 135112117524
853 136051450754
854 136996410166
855 137946643799
856 138902551824
857 139863783301
858 140830744693
859 141803075602
860 142781188811
861 143764725000
862 144754092721
863 145748933690
864 146749662838
865 147755912292
866 148768103390
867 149785869352
868 150809627227
869 151839011285
870 152874445042
871 153915553047
872 154962765311
873 156015707491
874 157074805250
875 158139685310
876 159210779889
877 160287705855
878 161370902010
879 162459986345
880 163555393255
881 164656741810
882 165764473049
883 166878196055
884 167998358540
885 169124570725
886 170257275855
887 171396085245
888 172541448874
889 173692967935
890 174851099170
891 176015444925
892 177186457415
893 178363740095
894 179547752004
895 180738086340
896 181935208995
897 183138714335
898 184349063665
899 185565852475
900 186789548985
901 188019738291
902 189256895557
903 190500607063
904 191751343325
905 193008691762
906 194273129896
907 195544234615
908 196822490477
909 198107475569
910 199399669740
911 200698652231
912 202004909989
913 203318011586
914 204638451097
915 205965798309
916 207300542526
917 208642254704
918 209991431338
919 211347632576
920 212711362134
921 214082181390
922 215460589227
923 216846148208
924 218239364500
925 219639789718
926 221047937343
927 222463360236
928 223886566983
929 225317111645
930 226755510186
931 228201305578
932 229655021193
933 231116201265
934 232585364208
935 234062055472
936 235546800943
937 237039134840
938 238539590552
939 240047703576
940 241564002280
941 243088023392
942 244620302847
943 246160366000
944 247708756384
945 249265000648
946 250829637240
947 252402194056
948 253983217207
949 255572223072
950 257169765456
951 258775362048
952 260389561504
953 262011882776
954 263642882279
955 265282067304
956 266930002056
957 268586195152
958 270251205584
959 271924543248
960 273606774992
961 275297398905
962 276996989722
963 278705046875
964 280422139821
965 282147769287
966 283882512683
967 285625858783
968 287378392982
969 289139605413
970 290910076128
971 292689296571
972 294477854845
973 296275230294
974 298082019104
975 299897701995
976 301722869744
977 303557004398
978 305400704884
979 307253441001
980 309115819858
981 310987312646
982 312868520999
983 314758917452
984 316659111888
985 318568564445
986 320487893287
987 322416559961
988 324355177090
989 326303207581
990 328261272406
991 330228821925
992 332206485491
993 334193714890
994 336191133867
995 338198195585
996 340215532238
997 342242584291
998 344279992420
999 346327198533
1000 348384837631