0 1
1 0
2 0
3 1
4 1
5 1
6 1
7 1
8 1
9 2
10 2
11 3
12 3
13 4
14 4
15 5
16 5
17 6
18 7
19 8
20 9
21 11
22 12
23 14
24 16
25 18
26 20
27 23
28 25
29 28
30 32
31 35
32 39
33 44
34 49
35 54
36 61
37 67
38 75
39 83
40 92
41 101
42 113
43 123
44 136
45 150
46 165
47 180
48 199
49 217
50 239
51 261
52 286
53 312
54 343
55 373
56 408
57 445
58 486
59 528
60 577
61 626
62 682
63 741
64 805
65 873
66 949
67 1027
68 1114
69 1207
70 1307
71 1413
72 1530
73 1653
74 1787
75 1931
76 2084
77 2249
78 2428
79 2617
80 2821
81 3041
82 3274
83 3525
84 3795
85 4082
86 4389
87 4720
88 5070
89 5447
90 5850
91 6279
92 6736
93 7229
94 7749
95 8308
96 8903
97 9538
98 10213
99 10938
100 11703
101 12524
102 13396
103 14326
104 15312
105 16370
106 17485
107 18679
108 19946
109 21295
110 22724
111 24252
112 25864
113 27586
114 29410
115 31350
116 33403
117 35593
118 37904
119 40366
120 42972
121 45739
122 48666
123 51781
124 55068
125 58562
126 62258
127 66176
128 70319
129 74718
130 79360
131 84284
132 89490
133 95001
134 100824
135 106996
136 113507
137 120402
138 127687
139 135388
140 143521
141 152125
142 161200
143 170796
144 180927
145 191623
146 202911
147 214837
148 227410
149 240685
150 254691
151 269462
152 285040
153 301477
154 318796
155 337061
156 356317
157 376604
158 397985
159 420519
160 444249
161 469247
162 495582
163 523303
164 552497
165 583234
166 615581
167 649626
168 685465
169 723157
170 762823
171 804548
172 848431
173 894576
174 943116
175 994129
176 1047772
177 1104153
178 1163411
179 1225675
180 1291122
181 1359852
182 1432075
183 1507928
184 1587597
185 1671246
186 1759106
187 1851315
188 1948141
189 2049760
190 2156421
191 2268335
192 2385801
193 2509003
194 2638283
195 2773876
196 2916103
197 3065238
198 3221666
199 3385635
200 3557579
201 3737804
202 3926729
203 4124712
204 4332238
205 4549644
206 4777476
207 5016143
208 5266177
209 5528045
210 5802363
211 6089583
212 6390392
213 6705326
214 7035064
215 7380219
216 7741563
217 8119701
218 8515494
219 8929648
220 9363023
221 9816414
222 10290797
223 10786975
224 11306021
225 11848860
226 12416578
227 13010215
228 13630991
229 14279960
230 14958469
231 15667722
232 16409089
233 17183914
234 17993728
235 18839913
236 19724148
237 20647995
238 21613182
239 22621440
240 23674688
241 24774719
242 25923637
243 27123456
244 28376347
245 29684533
246 31050418
247 32476323
248 33964875
249 35518655
250 37140398
251 38832944
252 40599307
253 42442463
254 44365700
255 46372318
256 48465749
257 50649609
258 52927676
259 55303752
260 57781949
261 60366459
262 63061600
263 65871956
264 68802254
265 71857331
266 75042329
267 78362562
268 81823447
269 85430770
270 89190456
271 93108627
272 97191715
273 101446423
274 105879543
275 110498366
276 115310299
277 120323069
278 125544714
279 130983664
280 136648429
281 142548156
282 148692113
283 155090014
284 161751892
285 168688320
286 175909947
287 183428227
288 191254733
289 199401637
290 207881462
291 216707428
292 225892845
293 235452013
294 245399370
295 255750134
296 266519907
297 277725185
298 289382577
299 301509896
300 314125134
301 327247260
302 340895701
303 355090987
304 369853811
305 385206318
306 401170894
307 417771139
308 435031202
309 452976575
310 471633010
311 491027976
312 511189292
313 532146249
314 553928823
315 576568619
316 600097616
317 624549836
318 649959792
319 676363766
320 703798917
321 732304346
322 761919717
323 792687083
324 824649193
325 857850914
326 892338234
327 928159453
328 965363675
329 1004002796
330 1044129689
331 1085799734
332 1129069766
333 1173999345
334 1220649158
335 1269083158
336 1319366626
337 1371567816
338 1425756851
339 1482007061
340 1540393334
341 1600994352
342 1663890600
343 1729166059
344 1796907109
345 1867203912
346 1940148716
347 2015838197
348 2094371418
349 2175851558
350 2260384868
351 2348082032
352 2439056513
353 2533426925
354 2631315003
355 2732847338
356 2838154412
357 2947371931
358 3060639218
359 3178101603
360 3299908464
361 3426214891
362 3557180892
363 3692972615
364 3833760873
365 3979723506
366 4131043521
367 4287910678
368 4450520892
369 4619077317
370 4793789061
371 4974873455
372 5162554387
373 5357063725
374 5558640996
375 5767534289
376 5983999205
377 6208301016
378 6440713215
379 6681518747
380 6931010059
381 7189489725
382 7457269734
383 7734673455
384 8022034508
385 8319697750
386 8628019719
387 8947368995
388 9278125852
389 9620684003
390 9975449857
391 10342843186
392 10723298103
393 11117263033
394 11525200839
395 11947590309
396 12384925849
397 12837717818
398 13306494061
399 13791799485
400 14294196742
401 14814267380
402 15352612075
403 15909850558
404 16486623818
405 17083593239
406 17701441865
407 18340875237
408 19002622208
409 19687434433
410 20396089321
411 21129388667
412 21888160646
413 22673260233
414 23485570693
415 24326002631
416 25195497744
417 26095026954
418 27025593136
419 27988231158
420 28984010134
421 30014031953
422 31079435955
423 32181396507
424 33321126582
425 34499877404
426 35718941473
427 36979650648
428 38283381767
429 39631553689
430 41025631778
431 42467127138
432 43957600551
433 45498660037
434 47091967520
435 48739235359
436 50442231790
437 52202779805
438 54022761987
439 55904117635
440 57848850563
441 59859025089
442 61936772528
443 64084289733
444 66303844931
445 68597774444
446 70968491619
447 73418482418
448 75950312969
449 78566627844
450 81270156947
451 84063711873
452 86950196115
453 89932600229
454 93014010525
455 96197607209
456 99486672330
457 102884585927
458 106394837468
459 110021020770
460 113766843896
461 117636127214
462 121632812493
463 125760958909
464 130024755849
465 134428517686
466 138976694860
467 143673872102
468 148524778671
469 153534284395
470 158707413866
471 164049341227
472 169565402565
473 175261094384
474 181142085047
475 187214211090
476 193483492821
477 199956129360
478 206638512299
479 213537224728
480 220659053947
481 228010988199
482 235600233788
483 243434210566
484 251520566969
485 259867179852
486 268482168433
487 277373891833
488 286550967710
489 296022268502
490 305796937879
491 315884391673
492 326294333216
493 337036751891
494 348121943379
495 359560507039
496 371363363802
497 383541758618
498 396107277130
499 409071845717
500 422447753460
501 436247650954
502 450484569790
503 465171926884
504 480323542659
505 495953642968
506 512076882819
507 528708347179
508 545863572081
509 563558551343
510 581809756350
511 600634140333
512 620049164082
513 640072799144
514 660723550714
515 682020467348
516 703983162435
517 726631821461
518 749987229761
519 774070778782
520 798904490983
521 824511033044
522 850913739301
523 878136622558
524 906204404198
525 935142524136
526 964977167855
527 995735283971
528 1027444609775
529 1060133686353
530 1093831891315
531 1128569453159
532 1164377480855
533 1201287986409
534 1239333912881
535 1278549154666
536 1318968593147
537 1360628116371
538 1403564651435
539 1447816193039
540 1493421834404
541 1540421793527
542 1588857452285
543 1638771382295
544 1690207380658
545 1743210505486
546 1797827110119
547 1854104876518
548 1912092858300
549 1971841513874
550 2033402746117
551 2096829945962
552 2162178030667
553 2229503485355
554 2298864410712
555 2370320564657
556 2443933406607
557 2519766150468
558 2597883807588
559 2678353237861
560 2761243202968
561 2846624417793
562 2934569600284
563 3025153535175
564 3118453122665
565 3214547440526
566 3313517803817
567 3415447827722
568 3520423483973
569 3628533176967
570 3739867799303
571 3854520806494
572 3972588284547
573 4094169025771
574 4219364593145
575 4348279410667
576 4481020827085
577 4617699205161
578 4758427998473
579 4903323842242
580 5052506627257
581 5206099606377
582 5364229468222
583 5527026443017
584 5694624390502
585 5867160907955
586 6044777415446
587 6227619280977
588 6415835906003
589 6609580850286
590 6809011933078
591 7014291360740
592 7225585825735
593 7443066652839
594 7666909898955
595 7897296499729
596 8134412386450
597 8378448636209
598 8629601587130
599 8888073008754
600 9154070218971
601 9427806255364
602 9709500010950
603 9999376409962
604 10297666542582
605 10604607862867
606 10920444325988
607 11245426587992
608 11579812163777
609 11923865632223
610 12277858794127
611 12642070901457
612 13016788818944
613 13402307256093
614 13798928951613
615 14206964912130
616 14626734597548
617 15058566186166
618 15502796765026
619 15959772598874
620 16429849345899
621 16913392334684
622 17410776782206
623 17922388099731
624 18448622117315
625 18989885394997
626 19546595475343
627 20119181204304
628 20708082987591
629 21313753143220
630 21936656166372
631 22577269088730
632 23236081774565
633 23913597291596
634 24610332212706
635 25326817021802
636 26063596426108
637 26821229770731
638 27600291385679
639 28401371014122
640 29225074167387
641 30072022591638
642 30942854636092
643 31838225730619
644 32758808792595
645 33705294720881
646 34678392813190
647 35678831302531
648 36707357790804
649 37764739798693
650 38851765242547
651 39969243003532
652 41118003418164
653 42298898894435
654 43512804422022
655 44760618205059
656 46043262220610
657 47361682874232
658 48716851575740
659 50109765446750
660 51541447920367
661 53012949468833
662 54525348257303
663 56079750898335
664 57677293127133
665 59319140613909
666 61006489667694
667 62740568073069
668 64522635854568
669 66353986144879
670 68235945975849
671 70169877210946
672 72157177370383
673 74199280592853
674 76297658528588
675 78453821338171
676 80669318617823
677 82945740469943
678 85284718468902
679 87687926766491
680 90157083134161
681 92693950111788
682 95300336088923
683 97978096533639
684 100729135121566
685 103555405006509
686 106458910035297
687 109441706069114
688 112505902245116
689 115653662387310
690 118887206324628
691 122208811351210
692 125620813641087
693 129125609767715
694 132725658174343
695 136423480794109
696 140221664586476
697 144122863215850
698 148129798696859
699 152245263141972
700 156472120472994
701 160813308281460
702 165271839617573
703 169850804919581
704 174553373925260
705 179382797681918
706 184342410535960
707 189435632269758
708 194665970181554
709 200037021303457
710 205552474619778
711 211216113378649
712 217031817402294
713 223003565541551
714 229135438091295
715 235431619340324
716 241896400142851
717 248534180577337
718 255349472625824
719 262346902993790
720 269531215911865
721 276907276067241
722 284480071581772
723 292254717069848
724 300236456742461
725 308430667647137
726 316842862913849
727 325478695125388
728 334343959762548
729 343444598721127
730 352786703904335
731 362376520945338
732 372220452963980
733 382325064441579
734 392697085202919
735 403343414461111
736 414271124970687
737 425487467305180
738 436999874200287
739 448815965008605
740 460943550297832
741 473390636502247
742 486165430719784
743 499276345626968
744 512732004495370
745 526541246312853
746 540713131088544
747 555256945201649
748 570182206936936
749 585498672132089
750 601216339966534
751 617345458848111
752 633896532528637
753 650880326253557
754 668307873144300
755 686190480686654
756 704539737404779
757 723367519627260
758 742685998531320
759 762507647212242
760 782845248036120
761 803711900093541
762 825121026888232
763 847086384112202
764 869622067753723
765 892742522222718
766 916462548814732
767 940797314272581
768 965762359636548
769 991373609177805
770 1017647379724304
771 1044600389997467
772 1072249770348570
773 1100613072591000
774 1129708280180367
775 1159553818476435
776 1190168565462368
777 1221571862471170
778 1253783525377718
779 1286823855888055
780 1320713653241072
781 1355474225993487
782 1391127404333245
783 1427695552398777
784 1465201581136117
785 1503668961258198
786 1543121736686564
787 1583584538082044
788 1625082596980390
789 1667641759937114
790 1711288503288430
791 1756049948023286
792 1801953875214576
793 1849028741549266
794 1897303695547007
795 1946808593795875
796 1997574017888766
797 2049631291486129
798 2103012498020391
799 2157750498515532
800 2213878950185429
801 2271432325063201
802 2330445929423376
803 2390955923351416
804 2452999341045112
805 2516614111254441
806 2581839078597518
807 2648714024929262
808 2717279691601837
809 2787577801902335
810 2859651084319838
811 2933543295982189
812 3009299247074904
813 3086964825342630
814 3166587021590196
815 3248213955399829
816 3331894901783190
817 3417680318045253
818 3505621871744213
819 3595772468774587
820 3688186282566395
821 3782918783550564
822 3880026769674113
823 3979568397180044
824 4081603212607348
825 4186192184966955
826 4293397739159650
827 4403283789723680
828 4515915775756272
829 4631360696167148
830 4749687146286470
831 4870965354714956
832 4995267221553387
833 5122666357039680
834 5253238121495529
835 5387059665687662
836 5524209972689038
837 5664769900065692
838 5808822223591376
839 5956451681465482
840 6107745019988080
841 6262791039750136
842 6421680643482814
843 6584506884333358
844 6751365015831318
845 6922352542473553
846 7097569271927093
847 7277117367868907
848 7461101404657413
849 7649628422553909
850 7842807984811445
851 8040752235519987
852 8243575959246252
853 8451396641455063
854 8664334530951987
855 8882512703023029
856 9106057124635379
857 9335096720558669
858 9569763441473925
859 9810192333035929
860 10056521607164497
861 10308892714207386
862 10567450417377592
863 10832342868303315
864 11103721684778959
865 11381742029671721
866 11666562692284956
867 11958346170799577
868 12257258757223778
869 12563470623681522
870 12877155911137307
871 13198492819512175
872 13527663700508772
873 13864855151755406
874 14210258113717608
875 14564067968211112
876 14926484639611218
877 15297712697728786
878 15677961463673157
879 16067445117315418
880 16466382807806003
881 16874998765997975
882 17293522419856441
883 17722188511851948
884 18161237219650235
885 18610914278728295
886 19071471108362983
887 19543164939877098
888 20026258948193261
889 20521022385738998
890 21027730719992014
891 21546665773327386
892 22078115866592772
893 22622375965344731
894 23179747829752994
895 23750540167277217
896 24335068789367193
897 24933656770898131
898 25546634613729894
899 26174340413390519
900 26817120029830789
901 27475327261433511
902 28149324023476000
903 28839480529822484
904 29546175479184952
905 30269796245037540
906 31010739070053797
907 31769409264350126
908 32546221408663111
909 33341599561323650
910 34155977470297956
911 34989798789484482
912 35843517300043161
913 36717597136157941
914 37612513016274387
915 38528750478779472
916 39466806123308477
917 40427187856994101
918 41410415146320626
919 42417019274124980
920 43447543602681788
921 44502543841964302
922 45582588324164743
923 46688258283933982
924 47820148144874012
925 48978865811986591
926 50165032970892043
927 51379285393057331
928 52622273247995839
929 53894661422068206
930 55197129844267682
931 56530373818877158
932 57895104365672447
933 59292048567077889
934 60721949923099596
935 62185568713856173
936 63683682369921655
937 65217085850576600
938 66786592030481419
939 68393032094369462
940 70037255940429246
941 71720132592409064
942 73442550620472587
943 75205418571131073
944 77009665406590478
945 78856240953323830
946 80746116360364043
947 82680284567588981
948 84659760783820242
949 86685582975317743
950 88758812364812909
951 90880533941126218
952 93051856979674963
953 95273915574402765
954 97547869180729482
955 99874903170382155
956 102256229398037468
957 104693086780081666
958 107186741885585066
959 109738489540308493
960 112349653443098764
961 115021586795836664
962 117755672946640486
963 120553326046911384
964 123415991722096345
965 126345147757294032
966 129342304796802136
967 132409007059098024
968 135546833066710843
969 138757396391876898
970 142042346417616626
971 145403369115689038
972 148842187840251044
973 152360564139062503
974 155960298581438957
975 159643231604169740
976 163411244374789435
977 167266259674014128
978 171210242795881783
979 175245202467812402
980 179373191789520133
981 183596309192342238
982 187916699418113351
983 192336554519770772
984 196858114881933739
985 201483670264067722
986 206215560864885552
987 211056178409919854
988 216007967261124197
989 221073425551087312
990 226255106339795270
991 231555618796969057
992 236977629408343636
993 242523863208209123
994 248197105036796861
995 254000200825511395
996 259936058907628504
997 266007651357925391
998 272218015359315034
999 278570254599212784
1000 285067540693938237