0 1
1 1
2 2
3 3
4 5
5 7
6 11
7 15
8 21
9 28
10 38
11 49
12 65
13 82
14 105
15 131
16 164
17 201
18 248
19 300
20 364
21 436
22 522
23 618
24 733
25 860
26 1009
27 1175
28 1367
29 1579
30 1824
31 2093
32 2400
33 2738
34 3120
35 3539
36 4011
37 4526
38 5102
39 5731
40 6430
41 7190
42 8033
43 8946
44 9953
45 11044
46 12241
47 13534
48 14950
49 16475
50 18138
51 19928
52 21873
53 23961
54 26226
55 28652
56 31275
57 34082
58 37108
59 40340
60 43819
61 47527
62 51508
63 55748
64 60289
65 65117
66 70281
67 75762
68 81612
69 87816
70 94425
71 101423
72 108869
73 116742
74 125104
75 133939
76 143307
77 153192
78 163662
79 174696
80 186366
81 198655
82 211634
83 225286
84 239691
85 254826
86 270775
87 287521
88 305146
89 323633
90 343074
91 363446
92 384845
93 407254
94 430768
95 455370
96 481165
97 508130
98 536375
99 565883
100 596763
101 628998
102 662708
103 697870
104 734609
105 772909
106 812893
107 854546
108 898003
109 943242
110 990404
111 1039474
112 1090592
113 1143743
114 1199080
115 1256582
116 1316407
117 1378542
118 1443144
119 1510201
120 1579883
121 1652171
122 1727242
123 1805085
124 1885876
125 1969605
126 2056462
127 2146430
128 2239706
129 2336282
130 2436354
131 2539915
132 2647176
133 2758123
134 2872974
135 2991725
136 3114593
137 3241575
138 3372904
139 3508570
140 3648814
141 3793635
142 3943274
143 4097732
144 4257266
145 4421870
146 4591809
147 4767088
148 4947971
149 5134465
150 5326852
151 5525131
152 5729593
153 5940248
154 6157387
155 6381022
156 6611462
157 6848712
158 7093090
159 7344613
160 7603599
161 7870067
162 8144354
163 8426472
164 8716768
165 9015266
166 9322313
167 9637936
168 9962502
169 10296030
170 10638898
171 10991138
172 11353128
173 11724903
174 12106862
175 12499033
176 12901825
177 13315280
178 13739808
179 14175454
180 14622650
181 15081433
182 15552247
183 16035143
184 16530566
185 17038571
186 17559625
187 18093776
188 18641503
189 19202869
190 19778354
191 20368025
192 20972386
193 21591496
194 22225872
195 22875589
196 23541165
197 24222679
198 24920674
199 25635222
200 26366879
201 27115733
202 27882342
203 28666799
204 29469687
205 30291092
206 31131611
207 31991347
208 32870899
209 33770375
210 34690401
211 35631077
212 36593044
213 37576420
214 38581848
215 39609452
216 40659902
217 41733315
218 42830376
219 43951221
220 45096538
221 46266468
222 47461728
223 48682452
224 49929373
225 51202644
226 52503001
227 53830604
228 55186218
229 56569996
230 57982720
231 59424563
232 60896310
233 62398141
234 63930872
235 65494676
236 67090386
237 68718196
238 70378943
239 72072828
240 73800720
241 75562813
242 77359994
243 79192479
244 81061159
245 82966258
246 84908699
247 86888700
248 88907203
249 90964448
250 93061382
251 95198253
252 97376042
253 99594990
254 101856098
255 104159631
256 106506594
257 108897261
258 111332672
259 113813095
260 116339590
261 118912449
262 121532738
263 124200758
264 126917611
265 129683592
266 132499824
267 135366627
268 138285130
269 141255663
270 144279392
271 147356641
272 150488598
273 153675613
274 156918880
275 160218760
276 163576485
277 166992410
278 170467790
279 174003007
280 177599323
281 181257130
282 184977730
283 188761510
284 192609795
285 196523000
286 200502457
287 204548593
288 208662780
289 212845440
290 217097970
291 221420820
292 225815395
293 230282157
294 234822553
295 239437040
296 244127090
297 248893190
298 253736820
299 258658480
300 263659693
301 268740954
302 273903812
303 279148793
304 284477455
305 289890337
306 295389041
307 300974102
308 306647149
309 312408748
310 318260538
311 324203099
312 330238115
313 336366162
314 342588952
315 348907094
316 355322309
317 361835221
318 368447598
319 375160060
320 381974404
321 388891283
322 395912505
323 403038738
324 410271838
325 417612470
326 425062519
327 432622685
328 440294864
329 448079772
330 455979354
331 463994323
332 472126655
333 480377098
334 488747640
335 497239046
336 505853354
337 514591326
338 523455032
339 532445271
340 541564125
341 550812410
342 560192260
343 569704489
344 579351263
345 589133434
346 599053181
347 609111374
348 619310245
349 629650662
350 640134891
351 650763838
352 661539783
353 672463651
354 683537776
355 694763082
356 706141937
357 717675305
358 729365568
359 741213710
360 753222169
361 765391927
362 777725458
363 790223785
364 802889397
365 815723337
366 828728151
367 841904882
368 855256112
369 868782926
370 882487922
371 896372206
372 910438434
373 924687712
374 939122734
375 953744649
376 968556167
377 983558459
378 998754295
379 1014144846
380 1029732921
381 1045519735
382 1061508114
383 1077699296
384 1094096168
385 1110699969
386 1127513625
387 1144538421
388 1161777301
389 1179231573
390 1196904244
391 1214796623
392 1232911758
393 1251251004
394 1269817428
395 1288612410
396 1307639080
397 1326898820
398 1346394802
399 1366128456
400 1386102973
401 1406319808
402 1426782218
403 1447491660
404 1468451434
405 1489663046
406 1511129816
407 1532853276
408 1554836813
409 1577081962
410 1599592154
411 1622368974
412 1645415874
413 1668734466
414 1692328270
415 1716198902
416 1740349927
417 1764783012
418 1789501744
419 1814507818
420 1839804891
421 1865394661
422 1891280832
423 1917465155
424 1943951356
425 1970741215
426 1997838529
427 2025245083
428 2052964721
429 2080999282
430 2109352634
431 2138026645
432 2167025256
433 2196350340
434 2226005887
435 2255993825
436 2286318168
437 2316980875
438 2347986034
439 2379335610
440 2411033741
441 2443082448
442 2475485894
443 2508246132
444 2541367401
445 2574851760
446 2608703499
447 2642924735
448 2677519784
449 2712490795
450 2747842162
451 2783576041
452 2819696878
453 2856206888
454 2893110544
455 2930410095
456 2968110092
457 3006212792
458 3044722800
459 3083642433
460 3122976324
461 3162726824
462 3202898647
463 3243494152
464 3284518108
465 3325972936
466 3367863433
467 3410192056
468 3452963684
469 3496180783
470 3539848288
471 3583968728
472 3628547068
473 3673585873
474 3719090192
475 3765062600
476 3811508203
477 3858429640
478 3905832048
479 3953718104
480 4002093030
481 4050959513
482 4100322834
483 4150185746
484 4200553561
485 4251429071
486 4302817675
487 4354722176
488 4407148033
489 4460098116
490 4513577917
491 4567590345
492 4622140981
493 4677232746
494 4732871282
495 4789059579
496 4845803312
497 4903105512
498 4960971944
499 5019405652
500 5078412464
501 5137995493
502 5198160602
503 5258910946
504 5320252480
505 5382188372
506 5444724641
507 5507864527
508 5571614084
509 5635976595
510 5700958208
511 5766562220
512 5832794844
513 5899659450
514 5967162288
515 6035306772
516 6104099247
517 6173543142
518 6243644869
519 6314407931
520 6385838778
521 6457940958
522 6530721018
523 6604182522
524 6678332085
525 6753173347
526 6828712961
527 6904954614
528 6981905058
529 7059567996
530 7137950250
531 7217055600
532 7296890908
533 7377460001
534 7458769842
535 7540824276
536 7623630336
537 7707191946
538 7791516180
539 7876607011
540 7962471615
541 8049113983
542 8136541364
543 8224757829
544 8313770669
545 8403584005
546 8494205232
547 8585638490
548 8677891248
549 8770967728
550 8864875442
551 8959618663
552 9055205009
553 9151638773
554 9248927648
555 9347076011
556 9446091599
557 9545978841
558 9646745582
559 9748396272
560 9850938833
561 9954377799
562 10058721138
563 10163973438
564 10270142776
565 10377233762
566 10485254551
567 10594209840
568 10704107830
569 10814953273
570 10926754482
571 11039516231
572 11153246913
573 11267951390
574 11383638103
575 11500311970
576 11617981545
577 11736651770
578 11856331280
579 11977025107
580 12098741935
581 12221486853
582 12345268660
583 12470092470
584 12595967165
585 12722897950
586 12850893757
587 12979959850
588 13110105278
589 13241335330
590 13373659140
591 13507082090
592 13641613365
593 13777258407
594 13914026520
595 14051923173
596 14190957755
597 14331135830
598 14472466840
599 14614956410
600 14758614103
601 14903445571
602 15049460465
603 15196664533
604 15345067480
605 15494675117
606 15645497271
607 15797539782
608 15950812566
609 16105321561
610 16261076738
611 16418084099
612 16576353740
613 16735891692
614 16896708142
615 17058809221
616 17222205172
617 17386902191
618 17552910648
619 17720236770
620 17888891019
621 18058879723
622 18230213402
623 18402898451
624 18576945518
625 18752361030
626 18929155729
627 19107336145
628 19286913079
629 19467893129
630 19650287227
631 19834102003
632 20019348485
633 20206033408
634 20394167860
635 20583758646
636 20774816986
637 20967349719
638 21161368162
639 21356879261
640 21553894395
641 21752420580
642 21952469330
643 22154047696
644 22357167291
645 22561835274
646 22768063321
647 22975858664
648 23185233115
649 23396193942
650 23608753058
651 23822917841
652 24038700268
653 24256107791
654 24475152526
655 24695841962
656 24918188317
657 25142199192
658 25367886871
659 25595259030
660 25824328094
661 26055101777
662 26287592608
663 26521808415
664 26757761794
665 26995460650
666 27234917721
667 27476140952
668 27719143187
669 27963932486
670 28210521762
671 28458919153
672 28709137717
673 28961185632
674 29215076064
675 29470817309
676 29728422602
677 29987900319
678 30249263842
679 30512521589
680 30777687051
681 31044768765
682 31313780294
683 31584730256
684 31857632363
685 32132495276
686 32409332818
687 32688153771
688 32968972031
689 33251796463
690 33536641114
691 33823514893
692 34112431960
693 34403401347
694 34696437288
695 34991548900
696 35288750570
697 35588051460
698 35889466072
699 36193003693
700 36498678901
701 36806501068
702 37116484928
703 37428639900
704 37742980834
705 38059517276
706 38378264153
707 38699231099
708 39022433198
709 39347880132
710 39675587104
711 40005563924
712 40337825874
713 40672382853
714 41009250303
715 41348438172
716 41689962022
717 42033831932
718 42380063544
719 42728667028
720 43079658188
721 43433047244
722 43788850122
723 44147077175
724 44507744411
725 44870862275
726 45236446939
727 45604508900
728 45975064454
729 46348124232
730 46723704614
731 47101816325
732 47482475911
733 47865694150
734 48251487714
735 48639867518
736 49030850318
737 49424447125
738 49820674864
739 50219544600
740 50621073386
741 51025272425
742 51432158857
743 51841743982
744 52254045111
745 52669073600
746 53086846889
747 53507376475
748 53930679886
749 54356768718
750 54785660672
751 55217367401
752 55651906738
753 56089290478
754 56529536544
755 56972656832
756 57418669440
757 57867586322
758 58319425710
759 58774199703
760 59231926624
761 59692618674
762 60156294354
763 60622965925
764 61092652023
765 61565365056
766 62041123753
767 62519940626
768 63001834584
769 63486818200
770 63974910521
771 64466124268
772 64960478583
773 65457986293
774 65958666722
775 66462532760
776 66969603870
777 67479893093
778 67993419988
779 68510197704
780 69030245985
781 69553578043
782 70080213764
783 70610166513
784 71143456274
785 71680096521
786 72220107425
787 72763502526
788 73310302138
789 73860519956
790 74414176394
791 74971285258
792 75531867151
793 76095935946
794 76663512392
795 77234610519
796 77809251177
797 78387448509
798 78969223557
799 79554590532
800 80143570624
801 80736178203
802 81332434562
803 81932354186
804 82535958562
805 83143262245
806 83754286871
807 84369047157
808 84987564844
809 85609854765
810 86235938858
811 86865832027
812 87499556362
813 88137126930
814 88778565928
815 89423888542
816 90073117167
817 90726267062
818 91383360776
819 92044413734
820 92709448593
821 93378480898
822 94051533508
823 94728622042
824 95409769515
825 96094991714
826 96784311764
827 97477745574
828 98175316473
829 98877040446
830 99582940980
831 100293034230
832 101007343795
833 101725885954
834 102448684512
835 103175755826
836 103907123861
837 104642805146
838 105382823760
839 106127196358
840 106875947228
841 107629093103
842 108386658434
843 109148660129
844 109915122754
845 110686063345
846 111461506679
847 112241469873
848 113025977868
849 113815047958
850 114608705202
851 115406967023
852 116209858694
853 117017397720
854 117829609541
855 118646511841
856 119468130179
857 120294482371
858 121125594192
859 121961483542
860 122802176365
861 123647690742
862 124498052738
863 125353280568
864 126213400516
865 127078430882
866 127948398121
867 128823320717
868 129703225248
869 130588130333
870 131478062772
871 132373041271
872 133273092803
873 134178236260
874 135088498740
875 136003899273
876 136924465180
877 137850215580
878 138781177970
879 139717371657
880 140658824265
881 141605555240
882 142557592433
883 143514955380
884 144477672110
885 145445762350
886 146419254257
887 147398167700
888 148382531065
889 149372364313
890 150367696010
891 151368546310
892 152374943910
893 153386909107
894 154404470830
895 155427649470
896 156456474138
897 157490965420
898 158531152560
899 159577056290
900 160628706088
901 161686122781
902 162749336032
903 163818366866
904 164893245080
905 165973991847
906 167060637201
907 168153202412
908 169251717701
909 170356204538
910 171466693281
911 172583205549
912 173705771940
913 174834414172
914 175969163032
915 177110040441
916 178257077324
917 179410295754
918 180569726898
919 181735392930
920 182907325209
921 184085546113
922 185270087142
923 186460970828
924 187658228916
925 188861884040
926 190071968139
927 191288504055
928 192511523869
929 193741050579
930 194977116514
931 196219744776
932 197468967890
933 198724809168
934 199987301280
935 201256467696
936 202532341336
937 203814945776
938 205104314135
939 206400470201
940 207703447240
941 209013269200
942 210329969600
943 211653572496
944 212984111608
945 214321611207
946 215666105161
947 217017617904
948 218376183560
949 219741826672
950 221114581568
951 222494473008
952 223881535471
953 225275793881
954 226677282976
955 228086027792
956 229502063272
957 230925414672
958 232356117088
959 233794195943
960 235239686594
961 236692614577
962 238153015458
963 239620914995
964 241096348909
965 242579343127
966 244069933634
967 245568146472
968 247074017837
969 248587573996
970 250108851302
971 251637876193
972 253174685289
973 254719305145
974 256271772594
975 257832114419
976 259400367612
977 260976559129
978 262560726232
979 264152895996
980 265753105899
981 267361383245
982 268977765674
983 270602280666
984 272234966133
985 273875849676
986 275524969425
987 277182353214
988 278848039336
989 280522055803
990 282204441184
991 283895223613
992 285594441880
993 287302124354
994 289018309991
995 290743027340
996 292476315635
997 294218203550
998 295968730542
999 297727925523
1000 299495828118