0 1
1 1
2 0
3 1
4 1
5 1
6 1
7 1
8 2
9 2
10 2
11 2
12 3
13 3
14 3
15 4
16 5
17 5
18 5
19 6
20 7
21 8
22 8
23 9
24 11
25 12
26 12
27 14
28 16
29 17
30 18
31 20
32 23
33 25
34 26
35 29
36 33
37 35
38 37
39 41
40 46
41 49
42 52
43 57
44 63
45 68
46 72
47 78
48 87
49 93
50 98
51 107
52 117
53 125
54 133
55 144
56 157
57 168
58 178
59 192
60 209
61 223
62 236
63 255
64 276
65 294
66 312
67 335
68 361
69 385
70 408
71 437
72 471
73 501
74 530
75 568
76 609
77 647
78 686
79 732
80 784
81 833
82 881
83 939
84 1004
85 1065
86 1126
87 1199
88 1279
89 1355
90 1433
91 1523
92 1621
93 1717
94 1814
95 1925
96 2048
97 2166
98 2286
99 2425
100 2574
101 2720
102 2871
103 3040
104 3223
105 3405
106 3590
107 3797
108 4022
109 4244
110 4472
111 4727
112 5000
113 5272
114 5553
115 5863
116 6194
117 6528
118 6871
119 7247
120 7652
121 8057
122 8474
123 8933
124 9420
125 9912
126 10422
127 10975
128 11564
129 12162
130 12778
131 13446
132 14157
133 14878
134 15623
135 16430
136 17284
137 18152
138 19053
139 20021
140 21045
141 22092
142 23174
143 24335
144 25565
145 26819
146 28117
147 29510
148 30977
149 32478
150 34037
151 35698
152 37449
153 39246
154 41106
155 43087
156 45175
157 47315
158 49534
159 51895
160 54376
161 56923
162 59567
163 62370
164 65313
165 68343
166 71483
167 74806
168 78299
169 81889
170 85612
171 89552
172 93679
173 97929
174 102342
175 106996
176 111872
177 116899
178 122111
179 127604
180 133358
181 139287
182 145437
183 151915
184 158688
185 165673
186 172923
187 180542
188 188505
189 196727
190 205253
191 214204
192 223561
193 233215
194 243227
195 253737
196 264703
197 276026
198 287776
199 300085
200 312928
201 326197
202 339953
203 354357
204 369381
205 384898
206 400988
207 417826
208 435371
209 453497
210 472297
211 491945
212 512409
213 533564
214 555491
215 578393
216 602245
217 626890
218 652435
219 679107
220 706857
221 735539
222 765273
223 796283
224 828540
225 861889
226 896441
227 932460
228 969918
229 1008633
230 1048746
231 1090544
232 1133981
233 1178881
234 1225403
235 1273839
236 1324158
237 1376183
238 1430065
239 1486137
240 1544381
241 1604580
242 1666921
243 1731778
244 1799101
245 1868692
246 1940760
247 2015678
248 2093430
249 2173805
250 2257009
251 2343473
252 2433185
253 2525904
254 2621877
255 2721578
256 2824974
257 2931833
258 3042436
259 3157269
260 3276326
261 3399377
262 3526698
263 3658841
264 3795820
265 3937360
266 4083793
267 4235730
268 4393156
269 4555821
270 4724097
271 4898608
272 5079385
273 5266173
274 5459346
275 5659619
276 5867037
277 6081309
278 6302880
279 6532529
280 6770288
281 7015885
282 7269818
283 7532903
284 7805213
285 8086491
286 8377243
287 8678385
288 8990032
289 9311875
290 9644512
291 9988954
292 10345290
293 10713259
294 11093525
295 11487140
296 11894267
297 12314650
298 12748980
299 13198445
300 13663248
301 14143101
302 14638805
303 15151662
304 15681873
305 16229196
306 16794525
307 17379234
308 17983605
309 18607429
310 19251642
311 19917779
312 20606195
313 21316645
314 22050208
315 22808578
316 23592107
317 24400630
318 25235352
319 26098054
320 26989217
321 27908711
322 28857810
323 29838518
324 30851395
325 31896309
326 32974715
327 34088806
328 35239186
329 36425812
330 37650309
331 38915013
332 40220673
333 41567333
334 42956720
335 44391437
336 45872374
337 47399572
338 48975003
339 50601532
340 52280104
341 54010914
342 55796152
343 57638873
344 59540240
345 61500555
346 63522169
347 65608490
348 67760860
349 69979635
350 72267480
351 74628130
352 77063052
353 79572796
354 82160323
355 84829651
356 87582514
357 90419649
358 93344250
359 96360772
360 99471227
361 102676439
362 105980015
363 109386863
364 112899166
365 116518046
366 120247505
367 124092817
368 128056561
369 132140103
370 136347784
371 140685466
372 145156078
373 149761187
374 154505670
375 159395962
376 164435295
377 169625615
378 174972341
379 180482430
380 186159616
381 192006235
382 198028173
383 204233138
384 210625380
385 217207527
386 223986180
387 230969820
388 238163120
389 245569265
390 253195577
391 261051230
392 269141605
393 277470416
394 286045645
395 294877465
396 303971937
397 313333260
398 322970361
399 332894409
400 343112116
401 353628419
402 364453213
403 375598641
404 387072332
405 398880008
406 411032475
407 423543151
408 436420646
409 449671366
410 463307374
411 477343432
412 491789036
413 506651654
414 521944636
415 537684036
416 553880630
417 570542939
418 587685583
419 605326312
420 623477199
421 642147809
422 661354414
423 681116521
424 701447494
425 722358311
426 743866979
427 765994768
428 788756733
429 812165355
430 836240368
431 861005242
432 886476837
433 912669091
434 939603935
435 967307190
436 995797473
437 1025090691
438 1055211091
439 1086186834
440 1118038855
441 1150785092
442 1184452143
443 1219071097
444 1254665288
445 1291254754
446 1328869001
447 1367542186
448 1407300132
449 1448165500
450 1490170896
451 1533353651
452 1577742638
453 1623363363
454 1670251601
455 1718448496
456 1767986218
457 1818893141
458 1871208912
459 1924978759
460 1980238211
461 2037019249
462 2095365633
463 2155326805
464 2216942431
465 2280248312
466 2345292491
467 2412129453
468 2480803255
469 2551353710
470 2623833973
471 2698303890
472 2774812141
473 2853403358
474 2934136175
475 3017076087
476 3102277250
477 3189789519
478 3279677276
479 3372012603
480 3466855603
481 3564261570
482 3664301649
483 3767055044
484 3872588051
485 3980962498
486 4092256795
487 4206557604
488 4323938592
489 4444468569
490 4568233639
491 4695329161
492 4825836684
493 4959832483
494 5097411580
495 5238678673
496 5383723722
497 5532631679
498 5685507211
499 5842464945
500 6003604571
501 6169020486
502 6338827587
503 6513151886
504 6692103643
505 6875787270
506 7064329444
507 7257868501
508 7456525917
509 7660417750
510 7869683410
511 8084474322
512 8304924928
513 8531163858
514 8763344121
515 9001632116
516 9246176265
517 9497118716
518 9754627988
519 10018886621
520 10290058080
521 10568299938
522 10853797513
523 11146750676
524 11447339966
525 11755739779
526 12072153428
527 12396800342
528 12729879673
529 13071583810
530 13422136470
531 13781778316
532 14150728410
533 14529199686
534 14917437957
535 15315706641
536 15724247421
537 16143295475
538 16573120404
539 17014011266
540 17466234249
541 17930048574
542 18405750591
543 18893657129
544 19394060836
545 19907248010
546 20433544049
547 20973295711
548 21526825354
549 22094448790
550 22676522718
551 23273427348
552 23885517404
553 24513140506
554 25156688406
555 25816577685
556 26493197922
557 27186932510
558 27898211277
559 28627489959
560 29375197249
561 30141755384
562 30927635306
563 31733336474
564 32559330014
565 33406080279
566 34274104031
567 35163948137
568 36076129713
569 37011160046
570 37969605724
571 38952064880
572 39959105781
573 40991290907
574 42049240685
575 43133610137
576 44245023261
577 45384097880
578 46551514253
579 47747989252
580 48974207126
581 50230847350
582 51518655195
583 52838414375
584 54190876119
585 55576786929
586 56996962467
587 58452260493
588 59943505026
589 61471515306
590 63037184912
591 64641452004
592 66285219553
593 67969387345
594 69694933675
595 71462883813
596 73274228002
597 75129953790
598 77031131245
599 78978881710
600 80974290498
601 83018440243
602 85112502330
603 87257702603
604 89455229320
605 91706270312
606 94012107098
607 96374078634
608 98793486919
609 101271634148
610 103809921251
611 106409811819
612 109072731455
613 111800106581
614 114593469585
615 117454419444
616 120384515940
617 123385322283
618 126458513818
619 129605836303
620 132828997131
621 136129708469
622 139509800633
623 142971180618
624 146515716465
625 150145281903
626 153861877565
627 157667585715
628 161564448580
629 165554517649
630 169639978673
631 173823103836
632 178106126824
633 182491292394
634 186980987067
635 191577691435
636 196283847237
637 201101909114
638 206034483788
639 211084278166
640 216253959875
641 221546213752
642 226963885825
643 232509928492
644 238187256898
645 243998806354
646 249947682416
647 256037106183
648 262270262016
649 268650356930
650 275180780693
651 281865046350
652 288706630207
653 295709037077
654 302875965450
655 310211244847
656 317718671287
657 325402073140
658 333265483787
659 341313078842
660 349549001599
661 357977431713
662 366602768652
663 375429563770
664 384462337245
665 393705652807
666 403164307543
667 412843260273
668 422747442985
669 432881836856
670 443251670176
671 453862346570
672 464719245463
673 475827800859
674 487193711848
675 498822865018
676 510721124972
677 522894420414
678 535348961557
679 548091158434
680 561127405420
681 574464168347
682 588108211654
683 602066516353
684 616346051826
685 630953866749
686 645897329901
687 661184041750
688 676821595440
689 692817675207
690 709180305729
691 725917759009
692 743038308030
693 760550327187
694 778462552132
695 796783986303
696 815523640671
697 834690637882
698 854294488098
699 874344988240
700 894851949209
701 915825309050
702 937275418042
703 959212932868
704 981648535705
705 1004593049228
706 1028057734236
707 1052054183134
708 1076594023099
709 1101689035975
710 1127351473344
711 1153593942058
712 1180429093663
713 1207869753760
714 1235929248265
715 1264621283164
716 1293959624213
717 1323958229221
718 1354631588054
719 1385994601545
720 1418062243799
721 1450849699400
722 1484372723611
723 1518647512423
724 1553690348875
725 1589517751631
726 1626146847413
727 1663595234700
728 1701880619429
729 1741020966255
730 1781034887327
731 1821941504755
732 1863760066363
733 1906510103462
734 1950211841598
735 1994886053393
736 2040553656795
737 2087235884757
738 2134954710798
739 2183732694539
740 2233592567391
741 2284557406313
742 2336651077221
743 2389898079238
744 2444323108458
745 2499951238424
746 2556808388945
747 2614921159515
748 2674316373026
749 2735021270305
750 2797063995255
751 2860473420316
752 2925278676300
753 2991509351043
754 3059195995494
755 3128369947461
756 3199062836473
757 3271306790977
758 3345134972332
759 3420581386681
760 3497680367868
761 3576466799534
762 3656976668529
763 3739246867871
764 3823314663270
765 3909217921104
766 3996995684872
767 4086687976214
768 4178335234185
769 4271978552039
770 4367660285888
771 4465423842468
772 4565313093250
773 4667372628934
774 4771648389436
775 4878187442020
776 4987037377352
777 5098246569988
778 5211864835439
779 5327943205727
780 5446533294556
781 5567687568902
782 5691460041404
783 5817906031607
784 5947081503460
785 6079043355830
786 6213850140181
787 6351561810926
788 6492239041987
789 6635943525370
790 6782738718756
791 6932689593065
792 7085861915155
793 7242322558242
794 7402140289972
795 7565385504122
796 7732129471809
797 7902444674110
798 8076405618252
799 8254088557406
800 8435570718907
801 8620930645357
802 8810249045637
803 9003608511382
804 9201092706805
805 9402786724575
806 9608777981392
807 9819155917245
808 10034011150843
809 10253435859211
810 10477524706426
811 10706374529580
812 10940083467591
813 11178751352088
814 11422480674583
815 11671376268922
816 11925544398113
817 12185093161001
818 12450133510619
819 12720778917500
820 12997144417566
821 13279347046645
822 13567506895618
823 13861746759491
824 14162191155930
825 14468966771941
826 14782203563679
827 15102034401270
828 15428594040198
829 15762019587247
830 16102451656859
831 16450033995339
832 16804912409576
833 17167235263194
834 17537154675875
835 17914826131857
836 18300407374986
837 18694058920439
838 19095945303740
839 19506234684650
840 19925097690794
841 20352707950277
842 20789243405335
843 21234885893680
844 21689819943886
845 22154233343384
846 22628318500027
847 23112272006548
848 23606293399140
849 24110585742320
850 24625357048083
851 25150819835063
852 25687189829395
853 26234686575135
854 26793534924805
855 27363964574454
856 27946208711863
857 28540504665399
858 29147095450562
859 29766229286390
860 30398158201813
861 31043138705817
862 31701433398031
863 32373310479811
864 33059042297543
865 33758906040882
866 34473185434919
867 35202170224914
868 35946154660631
869 36705438239285
870 37480327460397
871 38271135290732
872 39078179602809
873 39901783941540
874 40742279352900
875 41600003843005
876 42475300746281
877 43368519525932
878 44280017693243
879 45210160238500
880 46159317935016
881 47127868188592
882 48116197029615
883 49124698522639
884 50153773018465
885 51203828033146
886 52275280322481
887 53368555285767
888 54484085141528
889 55622309843819
890 56783679260221
891 57968652545205
892 59177696244199
893 60411285267093
894 61669905147739
895 62954051395012
896 64264227540340
897 65600946144147
898 66964731150481
899 68356117231754
900 69775647751540
901 71223875815871
902 72701366742889
903 74208697375775
904 75746453967616
905 77315233295900
906 78915645226675
907 80548312003598
908 82213866069550
909 83912951221455
910 85646225281023
911 87414359377983
912 89218035679845
913 91057948596927
914 92934807584145
915 94849336390445
916 96802270702101
917 98794359421240
918 100826367574041
919 102899075535484
920 105013276604200
921 107169778326530
922 109369405527330
923 111612999529214
924 113901415625823
925 116235524465990
926 118616215230745
927 121044394817484
928 123520985219982
929 126046924994054
930 128623172557783
931 131250705349963
932 133930517133892
933 136663619518727
934 139451045397186
935 142293848099875
936 145193098589570
937 148149887050123
938 151165326491070
939 154240551865135
940 157376717159847
941 160574997081324
942 163836590797740
943 167162721031353
944 170554631067935
945 174013586504025
946 177540879148545
947 181137826111786
948 184805766694864
949 188546064217310
950 192360110105500
951 196249322944433
952 200215145256866
953 204259045437196
954 208382522000237
955 212587102607501
956 216874340755837
957 221245817788085
958 225703147320088
959 230247974266432
960 234881971400581
961 239606841456661
962 244424321769509
963 249336183262824
964 254344226888560
965 259450285852588
966 264656230436100
967 269963966959637
968 275375434126180
969 280892605334600
970 286517493706135
971 292252151050689
972 298098664069985
973 304059156779582
974 310135795774220
975 316330789157784
976 322646382617856
977 329084861987131
978 335648558718488
979 342339848792245
980 349161148685992
981 356114918041857
982 363203665373090
983 370429946978654
984 377796362764096
985 385305559032880
986 392960234465724
987 400763139000160
988 408717069512491
989 416824872771428
990 425089451655415
991 433513764013277
992 442100818235816
993 450853676331711
994 459775460410970
995 468869351558546
996 478138585245493
997 487586454552085
998 497216316958533
999 507031593187160
1000 517035762467311