0 1
1 0
2 0
3 1
4 0
5 1
6 1
7 1
8 1
9 2
10 2
11 2
12 3
13 3
14 4
15 4
16 5
17 6
18 7
19 8
20 9
21 10
22 12
23 14
24 15
25 18
26 20
27 23
28 26
29 29
30 33
31 37
32 42
33 46
34 53
35 58
36 66
37 74
38 81
39 91
40 101
41 113
42 124
43 139
44 153
45 169
46 188
47 207
48 228
49 252
50 278
51 304
52 336
53 369
54 405
55 444
56 487
57 533
58 583
59 640
60 697
61 763
62 832
63 908
64 990
65 1078
66 1175
67 1278
68 1391
69 1510
70 1642
71 1783
72 1935
73 2099
74 2275
75 2465
76 2670
77 2891
78 3127
79 3383
80 3656
81 3952
82 4266
83 4606
84 4972
85 5360
86 5782
87 6229
88 6711
89 7227
90 7781
91 8370
92 9003
93 9682
94 10403
95 11180
96 12006
97 12891
98 13835
99 14844
100 15920
101 17069
102 18295
103 19603
104 20997
105 22481
106 24068
107 25754
108 27553
109 29466
110 31503
111 33672
112 35979
113 38435
114 41043
115 43821
116 46769
117 49906
118 53236
119 56773
120 60534
121 64521
122 68756
123 73249
124 78018
125 83076
126 88441
127 94128
128 100156
129 106546
130 113319
131 120492
132 128089
133 136137
134 144656
135 153675
136 163217
137 173319
138 184003
139 195305
140 207259
141 219892
142 233255
143 247375
144 262299
145 278064
146 294719
147 312313
148 330888
149 350505
150 371210
151 393065
152 416128
153 440463
154 466134
155 493211
156 521769
157 551881
158 583622
159 617085
160 652352
161 689513
162 728672
163 769915
164 813360
165 859114
166 907289
167 958012
168 1011403
169 1067598
170 1126733
171 1188959
172 1254419
173 1323281
174 1395709
175 1471868
176 1551953
177 1636144
178 1724647
179 1817668
180 1915423
181 2018139
182 2126054
183 2239419
184 2358495
185 2483546
186 2614863
187 2752741
188 2897483
189 3049421
190 3208887
191 3376238
192 3551838
193 3736077
194 3929348
195 4132074
196 4344702
197 4567673
198 4801476
199 5046600
200 5303566
201 5572920
202 5855221
203 6151065
204 6461059
205 6785850
206 7126105
207 7482516
208 7855818
209 8246767
210 8656151
211 9084795
212 9533551
213 10003326
214 10495044
215 11009683
216 11548251
217 12111798
218 12701436
219 13318296
220 13963584
221 14638534
222 15344438
223 16082653
224 16854568
225 17661654
226 18505427
227 19387476
228 20309445
229 21273043
230 22280065
231 23332359
232 24431871
233 25580608
234 26780656
235 28034199
236 29343502
237 30710921
238 32138911
239 33630013
240 35186892
241 36812291
242 38509084
243 40280258
244 42128896
245 44058245
246 46071639
247 48172561
248 50364632
249 52651614
250 55037424
251 57526114
252 60121918
253 62829204
254 65652547
255 68596679
256 71666508
257 74867164
258 78203929
259 81682337
260 85308102
261 89087162
262 93025708
263 97130142
264 101407117
265 105863549
266 110506600
267 115343727
268 120382661
269 125631425
270 131098341
271 136792047
272 142721526
273 148896068
274 155325350
275 162019373
276 168988540
277 176243644
278 183795845
279 191656780
280 199838467
281 208353399
282 217214526
283 226435265
284 236029550
285 246011813
286 256397047
287 267200754
288 278439034
289 290128577
290 302286668
291 314931247
292 328080900
293 341754878
294 355973158
295 370756412
296 386126093
297 402104412
298 418714384
299 435979885
300 453925597
301 472577138
302 491961022
303 512104732
304 533036730
305 554786481
306 577384536
307 600862490
308 625253105
309 650590295
310 676909166
311 704246094
312 732638709
313 762126010
314 792748332
315 824547460
316 857566659
317 891850678
318 927445863
319 964400177
320 1002763247
321 1042586467
322 1083922998
323 1126827860
324 1171357983
325 1217572265
326 1265531681
327 1315299273
328 1366940300
329 1420522257
330 1476114967
331 1533790652
332 1593624015
333 1655692360
334 1720075586
335 1786856380
336 1856120220
337 1927955488
338 2002453638
339 2079709176
340 2159819878
341 2242886787
342 2329014387
343 2418310728
344 2510887461
345 2606860054
346 2706347854
347 2809474209
348 2916366631
349 3027156904
350 3141981236
351 3260980381
352 3384299841
353 3512089946
354 3644506010
355 3781708582
356 3923863498
357 4071142136
358 4223721554
359 4381784651
360 4545520409
361 4715124014
362 4890797128
363 5072748055
364 5261191924
365 5456350976
366 5658454710
367 5867740167
368 6084452121
369 6308843388
370 6541175036
371 6781716595
372 7030746442
373 7288551948
374 7555429834
375 7831686494
376 8117638185
377 8413611450
378 8719943332
379 9036981787
380 9365085994
381 9704626656
382 10055986460
383 10419560328
384 10795755868
385 11184993731
386 11587708048
387 12004346817
388 12435372320
389 12881261615
390 13342506891
391 13819615991
392 14313112953
393 14823538355
394 15351449971
395 15897423179
396 16462051538
397 17045947377
398 17649742267
399 18274087759
400 18919655819
401 19587139553
402 20277253811
403 20990735817
404 21728345911
405 22490868168
406 23279111194
407 24093908767
408 24936120642
409 25806633346
410 26706360936
411 27636245869
412 28597259800
413 29590404497
414 30616712696
415 31677249012
416 32773110988
417 33905429944
418 35075372023
419 36284139322
420 37532970725
421 38823143218
422 40155972908
423 41532816182
424 42955070929
425 44424177679
426 45941620978
427 47508930522
428 49127682644
429 50799501585
430 52526060897
431 54309084939
432 56150350250
433 58051687215
434 60014981496
435 62042175740
436 64135271227
437 66296329464
438 68527474065
439 70830892454
440 73208837764
441 75663630750
442 78197661691
443 80813392414
444 83513358350
445 86300170650
446 89176518413
447 92145170835
448 95208979611
449 98370881183
450 101633899252
451 105001147246
452 108475830830
453 112061250719
454 115760805131
455 119577992758
456 123516415562
457 127579781617
458 131771908321
459 136096725335
460 140558277842
461 145160729755
462 149908367104
463 154805601521
464 159856973699
465 165067157165
466 170440961869
467 175983338119
468 181699380482
469 187594331825
470 193673587559
471 199942699783
472 206407381794
473 213073512551
474 219947141169
475 227034491917
476 234341968897
477 241876161149
478 249643847816
479 257652003306
480 265907802854
481 274418627954
482 283192072244
483 292235947248
484 301558288439
485 311167361464
486 321071668395
487 331279954374
488 341801214208
489 352644699346
490 363819924868
491 375336676683
492 387205019077
493 399435302208
494 412038170055
495 425024568461
496 438405753271
497 452193298924
498 466399107029
499 481035415347
500 496114807022
501 511650219796
502 527654955894
503 544142691662
504 561127487862
505 578623800089
506 596646489405
507 615210833433
508 634332537446
509 654027746082
510 674313055022
511 695205523266
512 716722685657
513 738882565539
514 761703688046
515 785205093419
516 809406350917
517 834327573014
518 859989429827
519 886413164288
520 913620607183
521 941634192970
522 970476975925
523 1000172646552
524 1030745548642
525 1062220696627
526 1094623793432
527 1127981248647
528 1162320197369
529 1197668519504
530 1234054859297
531 1271508645842
532 1310060113637
533 1349740323825
534 1390581186215
535 1432615481421
536 1475876884022
537 1520399985992
538 1566220320824
539 1613374388348
540 1661899679942
541 1711834704681
542 1763219015991
543 1816093239000
544 1870499098551
545 1926479447921
546 1984078298367
547 2043340849172
548 2104313518897
549 2167043976967
550 2231581176183
551 2297975386259
552 2366278227811
553 2436542707622
554 2508823254525
555 2583175756204
556 2659657597148
557 2738327697084
558 2819246550850
559 2902476269046
560 2988080619659
561 3076125070933
562 3166676835036
563 3259804913013
564 3355580140603
565 3454075235652
566 3555364846307
567 3659525600437
568 3766636156596
569 3876777255752
570 3990031774708
571 4106484780674
572 4226223587236
573 4349337811724
574 4475919433802
575 4606062855834
576 4739864964423
577 4877425193560
578 5018845589561
579 5164230877286
580 5313688528063
581 5467328829374
582 5625264956073
583 5787613043632
584 5954492262827
585 6126024896673
586 6302336418799
587 6483555573893
588 6669814460353
589 6861248614493
590 7057997097342
591 7260202583015
592 7468011449695
593 7681573872472
594 7901043918469
595 8126579644696
596 8358343197676
597 8596500915956
598 8841223434875
599 9092685793787
600 9351067546096
601 9616552871707
602 9889330692587
603 10169594790639
604 10457543928644
605 10753381974168
606 11057318026226
607 11369566545264
608 11690347486067
609 12019886434052
610 12358414744599
611 12706169685660
612 13063394584255
613 13430338975863
614 13807258757789
615 14194416346317
616 14592080836976
617 15000528169257
618 15420041294916
619 15850910350466
620 16293432833714
621 16747913784433
622 17214665969479
623 17694010071981
624 18186274885379
625 18691797511838
626 19210923565561
627 19744007380750
628 20291412224378
629 20853510514422
630 21430684042560
631 22023324202738
632 22631832225136
633 23256619415049
634 23898107397971
635 24556728370205
636 25232925355231
637 25927152466497
638 26639875175985
639 27371570589419
640 28122727727544
641 28893847814208
642 29685444571259
643 30498044520063
644 31332187290524
645 32188425936774
646 33067327260836
647 33969472143085
648 34895455880935
649 35845888535596
650 36821395286149
651 37822616792757
652 38850209567631
653 39904846354753
654 40987216518584
655 42098026441695
656 43237999931742
657 44407878637510
658 45608422475002
659 46840410063067
660 48104639169086
661 49401927165219
662 50733111495057
663 52099050150929
664 53500622162307
665 54938728095276
666 56414290563784
667 57928254752265
668 59481588950760
669 61075285102123
670 62710359361308
671 64387852668240
672 66108831333096
673 67874387635645
674 69685640437833
675 71543735810552
676 73449847674829
677 75405178457112
678 77410959760213
679 79468453049143
680 81578950352656
681 83743774980850
682 85964282258907
683 88241860277664
684 90577930660867
685 92973949350534
686 95431407409671
687 97951831843064
688 100536786437181
689 103187872618358
690 105906730330964
691 108695038935279
692 111554518125604
693 114486928869313
694 117494074366511
695 120577801031947
696 123739999498773
697 126982605644715
698 130307601641896
699 133717017029840
700 137212929812510
701 140797467580104
702 144472808656140
703 148241183270054
704 152104874756195
705 156066220779932
706 160127614590524
707 164291506302457
708 168560404205460
709 172936876103409
710 177423550683788
711 182023118916931
712 186738335486935
713 191572020254240
714 196527059750496
715 201606408707430
716 206813091619103
717 212150204338952
718 217620915712499
719 223228469245919
720 228976184811795
721 234867460392671
722 240905773863507
723 247094684812987
724 253437836405386
725 259938957283716
726 266601863514303
727 273430460575212
728 280428745387737
729 287600808393150
730 294950835674960
731 302483111127498
732 310202018673025
733 318112044526894
734 326217779512836
735 334523921429129
736 343035277466255
737 351756766677789
738 360693422505355
739 369850395359241
740 379232955254943
741 388846494507789
742 398696530486319
743 408788708425311
744 419128804300941
745 429722727768290
746 440576525162935
747 451696382568066
748 463088628947981
749 474759739350144
750 486716338176487
751 498965202526041
752 511513265610533
753 524367620243299
754 537535522404374
755 551024394882632
756 564841830996821
757 578995598397269
758 593493642949897
759 608344092704196
760 623555261946423
761 639135655340858
762 655093972160261
763 671439110607324
764 688180172229893
765 705326466430606
766 722887515073976
767 740873057192179
768 759293053792237
769 778157692766855
770 797477393909890
771 817262814040453
772 837524852235977
773 858274655177523
774 879523622610091
775 901283412919340
776 923565948828072
777 946383423214032
778 969748305052186
779 993673345483711
780 1018171584014555
781 1043256354846381
782 1068941293342337
783 1095240342630655
784 1122167760348281
785 1149738125528460
786 1177966345634661
787 1206867663743566
788 1236457665881479
789 1266752288515841
790 1297767826205115
791 1329520939411793
792 1362028662480075
793 1395308411782972
794 1429377994041769
795 1464255614821230
796 1499959887204270
797 1536509840649572
798 1573924930036674
799 1612225044901620
800 1651430518867400
801 1691562139272986
802 1732641157005124
803 1774689296536823
804 1817728766176870
805 1861782268535555
806 1906873011209620
807 1953024717691224
808 2000261638506852
809 2048608562588310
810 2098090828882823
811 2148734338206671
812 2200565565346274
813 2253611571412814
814 2307900016454707
815 2363459172333927
816 2420317935870847
817 2478505842263858
818 2538053078788901
819 2598990498784206
820 2661349635926604
821 2725162718804464
822 2790462685794777
823 2857283200249090
824 2925658665995065
825 2995624243160763
826 3067215864326172
827 3140470251010397
828 3215424930501056
829 3292118253031960
830 3370589409317003
831 3450878448446836
832 3533026296155595
833 3617074773465155
834 3703066615714816
835 3791045491984343
836 3881056024917580
837 3973143810955025
838 4067355440983422
839 4163738521410770
840 4262341695675227
841 4363214666196950
842 4466408216781954
843 4571974235485539
844 4679965737945634
845 4790436891195961
846 4903443037966659
847 5019040721484527
848 5137287710781357
849 5258243026520487
850 5381966967352175
851 5508521136807965
852 5637968470745998
853 5770373265356322
854 5905801205739219
855 6044319395066917
856 6185996384339548
857 6330902202748453
858 6479108388658373
859 6630688021221214
860 6785715752632759
861 6944267841046556
862 7106422184156643
863 7272258353462268
864 7441857629229859
865 7615303036164290
866 7792679379804244
867 7974073283655428
868 8159573227076484
869 8349269583932418
870 8543254662030307
871 8741622743353539
872 8944470125110219
873 9151895161610134
874 9363998306988358
875 9580882158791386
876 9802651502442514
877 10029413356604437
878 10261277019456595
879 10498354115904499
880 10740758645738879
881 10988607032765061
882 11242018174919748
883 11501113495395789
884 11766016994794304
885 12036855304323494
886 12313757740065505
887 12596856358331067
888 12886286012124399
889 13182184408740128
890 13484692168512506
891 13793952884741333
892 14110113184816516
893 14433322792563637
894 14763734591836275
895 15101504691378803
896 15446792490983309
897 15799760748966192
898 16160575650990828
899 16529406880260843
900 16906427689111584
901 17291814972028072
902 17685749340114576
903 18088415197045615
904 18500000816525983
905 18920698421289475
906 19350704263666671
907 19790218707750504
908 20239446313192862
909 20698595920661379
910 21167880738988540
911 21647518434047248
912 22137731219385221
913 22638745948651972
914 23150794209853210
915 23674112421468276
916 24208941930464184
917 24755529112244946
918 25314125472573224
919 25884987751500993
920 26468378029349024
921 27064563834773380
922 27673818254959296
923 28296420047982828
924 28932653757382515
925 29582809828983297
926 30247184730015758
927 30926081070572975
928 31619807727452072
929 32328679970423945
930 33053019590978204
931 33793155033592018
932 34549421529568913
933 35322161233497433
934 36111723362378468
935 36918464337474117
936 37742747928927579
937 38584945403208619
938 39445435673438097
939 40324605452644793
940 41222849410011320
941 42140570330164954
942 43078179275573144
943 44036095752100283
944 45014747877787171
945 46014572554914079
946 47036015645407563
947 48079532149656489
948 49145586388801385
949 50234652190562647
950 51347213078673909
951 52483762465989492
952 53644803851334109
953 54830851020165956
954 56042428249125450
955 57280070514543346
956 58544323704981596
957 59835744837883204
958 61154902280408589
959 62502375974536815
960 63878757666512160
961 65284651140717996
962 66720672458062048
963 68187450198954261
964 69685625710966599
965 71215853361261707
966 72778800793878787
967 74375149191969925
968 76005593545078138
969 77670842921551076
970 79371620746186581
971 81108665083208540
972 82882728924672476
973 84694580484402499
974 86545003497562512
975 88434797525966991
976 90364778269237912
977 92335777881916445
978 94348645296641983
979 96404246553511153
980 98503465135730371
981 100647202311680483
982 102836377483512454
983 105071928542393115
984 107354812230528934
985 109686004510091180
986 112066500939170143
987 114497317054890136
988 116979488763816413
989 119514072739790440
990 122102146829330436
991 124744810464738685
992 127443185085056931
993 130198414565015011
994 133011665652120307
995 135884128412039030
996 138817016682423006
997 141811568535336307
998 144869046748443292
999 147990739285116864
1000 151177959783630754