0 1
1 0
2 0
3 0
4 0
5 0
6 0
7 1
8 1
9 1
10 1
11 1
12 1
13 1
14 1
15 2
16 2
17 3
18 3
19 4
20 4
21 5
22 5
23 6
24 7
25 8
26 9
27 11
28 12
29 14
30 16
31 18
32 20
33 23
34 26
35 29
36 33
37 37
38 42
39 47
40 53
41 59
42 67
43 74
44 83
45 93
46 104
47 115
48 129
49 143
50 160
51 177
52 197
53 218
54 243
55 268
56 297
57 329
58 364
59 401
60 444
61 489
62 540
63 595
64 655
65 721
66 794
67 872
68 958
69 1053
70 1156
71 1267
72 1390
73 1523
74 1668
75 1827
76 1998
77 2186
78 2390
79 2611
80 2851
81 3114
82 3397
83 3705
84 4040
85 4403
86 4795
87 5223
88 5683
89 6184
90 6726
91 7312
92 7945
93 8633
94 9373
95 10175
96 11041
97 11977
98 12986
99 14079
100 15254
101 16524
102 17894
103 19370
104 20960
105 22678
106 24523
107 26513
108 28656
109 30961
110 33441
111 36112
112 38981
113 42067
114 45386
115 48951
116 52780
117 56897
118 61313
119 66056
120 71149
121 76610
122 82470
123 88758
124 95497
125 102722
126 110469
127 118766
128 127656
129 137181
130 147377
131 158293
132 169983
133 182486
134 195866
135 210182
136 225488
137 241854
138 259356
139 278056
140 298043
141 319398
142 342207
143 366566
144 392583
145 420350
146 449991
147 481628
148 515379
149 551383
150 589794
151 630745
152 674413
153 720966
154 770580
155 823451
156 879791
157 939799
158 1003718
159 1071792
160 1144268
161 1221422
162 1303555
163 1390951
164 1483950
165 1582894
166 1688134
167 1800063
168 1919095
169 2045639
170 2180166
171 2323159
172 2475113
173 2636573
174 2808120
175 2990334
176 3183864
177 3389389
178 3607601
179 3839264
180 4085180
181 4346162
182 4623116
183 4916981
184 5228725
185 5559406
186 5910133
187 6282049
188 6676395
189 7094478
190 7537640
191 8007343
192 8505120
193 9032551
194 9591351
195 10183321
196 10810315
197 11474347
198 12177522
199 12922028
200 13710214
201 14544552
202 15427603
203 16362123
204 17350998
205 18397235
206 19504047
207 20674822
208 21913066
209 23222547
210 24607209
211 26071164
212 27618800
213 29254729
214 30983748
215 32810984
216 34741803
217 36781819
218 38936989
219 41213587
220 43618140
221 46157600
222 48839259
223 51670733
224 54660102
225 57815858
226 61146853
227 64662498
228 68372647
229 72287615
230 76418314
231 80776209
232 85373271
233 90222179
234 95336231
235 100729336
236 106416189
237 112412227
238 118733572
239 125397273
240 132421205
241 139824069
242 147625603
243 155846516
244 164508463
245 173634297
246 183247973
247 193374567
248 204040498
249 215273484
250 227102513
251 239558128
252 252672357
253 266478702
254 281012442
255 296310563
256 312411752
257 329356736
258 347188189
259 365950769
260 385691441
261 406459424
262 428306220
263 451285961
264 475455378
265 500873818
266 527603641
267 555710183
268 585261793
269 616330262
270 648990789
271 683322033
272 719406594
273 757330960
274 797185615
275 839065512
276 883070080
277 929303320
278 977874337
279 1028897353
280 1082491839
281 1138783071
282 1197902202
283 1259986366
284 1325179352
285 1393631627
286 1465500538
287 1540950989
288 1620155531
289 1703294575
290 1790557148
291 1882140988
292 1978252850
293 2079109259
294 2184936727
295 2295972011
296 2412463037
297 2534669085
298 2662861156
299 2797322936
300 2938351070
301 3086255554
302 3241360837
303 3404006092
304 3574545762
305 3753350668
306 3940808440
307 4137324066
308 4343321181
309 4559242519
310 4785550602
311 5022729101
312 5271283452
313 5531741562
314 5804655401
315 6090601628
316 6390182501
317 6704027562
318 7032794423
319 7377169778
320 7737871288
321 8115648470
322 8511283914
323 8925595280
324 9359436440
325 9813698767
326 10289313429
327 10787252648
328 11308531219
329 11854209028
330 12425392509
331 13023236375
332 13648946438
333 14303781235
334 14989054074
335 15706136072
336 16456458114
337 17241513125
338 18062859463
339 18922123165
340 19821000525
341 20761261861
342 21744754103
343 22773403689
344 23849220796
345 24974302244
346 26150834831
347 27381100007
348 28667477193
349 30012447587
350 31418599314
351 32888631246
352 34425357311
353 36031712199
354 37710755741
355 39465677747
356 41299804382
357 43216603150
358 45219688323
359 47312828101
360 49499950194
361 51785148032
362 54172688682
363 56667019201
364 59272773658
365 61994781920
366 64838076868
367 67807902339
368 70909722856
369 74149231878
370 77532360652
371 81065289151
372 84754455327
373 88606565138
374 92628604702
375 96827850764
376 101211881972
377 105788592465
378 110566203612
379 115553276799
380 120758728463
381 126191843438
382 131862289259
383 137780132963
384 143955856107
385 150400370867
386 157125038722
387 164141687449
388 171462629100
389 179100680963
390 187069184533
391 195382025843
392 204053658731
393 213099126231
394 222534083369
395 232374823105
396 242638300356
397 253342157633
398 264504753849
399 276145191447
400 288283344981
401 300939893385
402 314136350309
403 327895096227
404 342239414362
405 357193524742
406 372782620147
407 389032906205
408 405971639485
409 423627167885
410 442028975156
411 461207723746
412 481195299900
413 502024863342
414 523730895229
415 546349248632
416 569917203868
417 594473522252
418 620058502458
419 646714042286
420 674483698681
421 703412750863
422 733548269058
423 764939181667
424 797636345818
425 831692623894
426 867162958644
427 904104452043
428 942576450415
429 982640628515
430 1024361077442
431 1067804399547
432 1113039802289
433 1160139196396
434 1209177301542
435 1260231751102
436 1313383201739
437 1368715451027
438 1426315554333
439 1486273947157
440 1548684575903
441 1613645028416
442 1681256670339
443 1751624790628
444 1824858747187
445 1901072118802
446 1980382867076
447 2062913498799
448 2148791235227
449 2238148192245
450 2331121561267
451 2427853797879
452 2528492822162
453 2633192220206
454 2742111454278
455 2855416085422
456 2973277997994
457 3095875633611
458 3223394238552
459 3356026113822
460 3493970875437
461 3637435729418
462 3786635750137
463 3941794169825
464 4103142684234
465 4270921762190
466 4445380967743
467 4626779299612
468 4815385535530
469 5011478590479
470 5215347893597
471 5427293771135
472 5647627844678
473 5876673449542
474 6114766060625
475 6362253734750
476 6619497575285
477 6886872205268
478 7164766258877
479 7453582897074
480 7753740333181
481 8065672378735
482 8389829015677
483 8726676979959
484 9076700367752
485 9440401270004
486 9818300420589
487 10210937869074
488 10618873684533
489 11042688674967
490 11482985133841
491 11940387620474
492 12415543758425
493 12909125063526
494 13421827809200
495 13954373911902
496 14507511849671
497 15082017621051
498 15678695727105
499 16298380189902
500 16941935615002
501 17610258280257
502 18304277264844
503 19024955626145
504 19773291606804
505 20550319885640
506 21357112881361
507 22194782089954
508 23064479470642
509 23967398889481
510 24904777600915
511 25877897782902
512 26888088135091
513 27936725519565
514 29025236660925
515 30155099914910
516 31327847085312
517 32545065305912
518 33808398997607
519 35119551879650
520 36480289052482
521 37892439162920
522 39357896630006
523 40878623949503
524 42456654088907
525 44094092949870
526 45793121917696
527 47556000509640
528 49385069098652
529 51282751733047
530 53251559064253
531 55294091358912
532 57413041616581
533 59611198805650
534 61891451193663
535 64256789793429
536 66710311939127
537 69255224967212
538 71894850024921
539 74632626021290
540 77472113694561
541 80416999820303
542 83471101575593
543 86638371032495
544 89922899806679
545 93328923876692
546 96860828547298
547 100523153583202
548 104320598529971
549 108258028194916
550 112340478315243
551 116573161431664
552 120961472939279
553 125510997344434
554 130227514747041
555 135117007519047
556 140185667209814
557 145439901698478
558 150886342563573
559 156531852702397
560 162383534220858
561 168448736564138
562 174735064921827
563 181250388929561
564 188002851637303
565 195000878779053
566 202253188368015
567 209768800586402
568 217557048006508
569 225627586168965
570 233990404486118
571 242655837509999
572 251634576591606
573 260937681899362
574 270576594838422
575 280563150898669
576 290909592899630
577 301628584675624
578 312733225230865
579 324237063332857
580 336154112588957
581 348498867038708
582 361286317229207
583 374531966821364
584 388251849761658
585 402462547986228
586 417181209708289
587 432425568325362
588 448213961913026
589 464565353359586
590 481499351179638
591 499036230974342
592 517196957594943
593 536003208050580
594 555477395128366
595 575642691785191
596 596523056355520
597 618143258543248
598 640528906260306
599 663706473360017
600 687703328232628
601 712547763330696
602 738269025674507
603 764897348306113
604 792463982763699
605 821001232629512
606 850542488121319
607 881122261803052
608 912776225471460
609 945541248190514
610 979455435552596
611 1014558170228833
612 1050890153780252
613 1088493449814515
614 1127411528554833
615 1167689312793915
616 1209373225323552
617 1252511237910834
618 1297152921795504
619 1343349499805439
620 1391153900165275
621 1440620811976116
622 1491806742468260
623 1544770076108258
624 1599571135540454
625 1656272244471364
626 1714937792584635
627 1775634302469282
628 1838430498676406
629 1903397378999551
630 1970608287963273
631 2040138992644251
632 2112067760926019
633 2186475442176082
634 2263445550478089
635 2343064350527316
636 2425420946183017
637 2510607371818837
638 2598718686587631
639 2689853071599845
640 2784111930164841
641 2881599991222170
642 2982425415965830
643 3086699907822026
644 3194538825917209
645 3306061302044760
646 3421390361302944
647 3540653046550835
648 3663980546697235
649 3791508329008053
650 3923376275589069
651 4059728824068048
652 4200715112673448
653 4346489129879837
654 4497209868652237
655 4653041485500259
656 4814153464526481
657 4980720786509895
658 5152924103250601
659 5330949917375524
660 5514990767655082
661 5705245420074906
662 5901919064877149
663 6105223519633204
664 6315377438610066
665 6532606528661336
666 6757143771718316
667 6989229654162107
668 7229112403326381
669 7477048231221054
670 7733301585777391
671 7998145409886044
672 8271861408332526
673 8554740322953705
674 8847082216309330
675 9149196763989065
676 9461403555904487
677 9784032406882943
678 10117423676702830
679 10461928599946927
680 10817909626015310
681 11185740769459820
682 11565807971044088
683 11958509469899337
684 12364256186961219
685 12783472120121655
686 13216594751497953
687 13664075467028333
688 14126379988862092
689 14603988820980119
690 15097397708281570
691 15607118109642727
692 16133677685418697
693 16677620799654410
694 17239509037551003
695 17819921738696136
696 18419456546359487
697 19038729973441103
698 19678377985623981
699 20339056602069129
700 21021442514286038
701 21726233723777266
702 22454150198834535
703 23205934551169490
704 23982352733028703
705 24784194755212547
706 25612275426737428
707 26467435116843590
708 27350540539816745
709 28262485563422408
710 29204192041712735
711 30176610672728171
712 31180721881955540
713 32217536732366329
714 33288097861615850
715 34393480447332344
716 35534793201391207
717 36713179393815928
718 37929817907310697
719 39185924323395187
720 40482752040850663
721 41821593427565035
722 43203781006827760
723 44630688678858840
724 46103732978748459
725 47624374371944834
726 49194118588158453
727 50814517994952795
728 52487173012255952
729 54213733568750628
730 55995900601515110
731 57835427600254916
732 59734122197178988
733 61693847804004953
734 63716525297547218
735 65804134755045817
736 67958717240844218
737 70182376645990435
738 72477281582035696
739 74845667330770777
740 77289837851605928
741 79812167847996055
742 82415104894792735
743 85101171628372863
744 87872968001084128
745 90733173602040929
746 93684550046279398
747 96729943433958778
748 99872286881811124
749 103114603129017529
750 106460007219359338
751 109911709262029337
752 113473017273463305
753 117147340102217349
754 120938190439473562
755 124849187917731157
756 128884062299903541
757 133046656761614186
758 137340931269465468
759 141770966057710063
760 146340965206347152
761 151055260323652958
762 155918314335801418
763 160934725386846865
764 166109230852332883
765 171446711469428125
766 176952195587133853
767 182630863540099895
768 188488052149219281
769 194529259352839526
770 200760148972423445
771 207186555616123310
772 213814489724422185
773 220650142761997684
774 227699892559590342
775 234970308810371310
776 242468158725316926
777 250200412851714060
778 258174251059663736
779 266397068701469709
780 274876482948407659
781 283620339310147361
782 292636718342122813
783 301933942545751744
784 311520583467214063
785 321405469000525747
786 331597690900252737
787 342106612510043698
788 352941876713200233
789 364113414111107002
790 375631451436209732
791 387506520206282829
792 399749465626325035
793 412371455745324625
794 425383990875200801
795 438798913278819104
796 452628417134923748
797 466885058787901659
798 481581767289886086
799 496731855243690995
800 512349029955150265
801 528447404903032102
802 545041511535719070
803 562146311403943616
804 579777208638466455
805 597950062782644292
806 616681201989954027
807 635987436596134317
808 655886073076712230
809 676394928400821345
810 697532344791810337
811 719317204906300519
812 741768947443503469
813 764907583196208833
814 788753711556062712
815 813328537485926306
816 838653888971714606
817 864752234967371892
818 891646703846836324
819 919361102376462769
820 947919935222681781
821 977348425009898935
822 1007672532943257685
823 1038918980012260071
824 1071115268791492790
825 1104289705854331870
826 1138471424816937626
827 1173690410030128644
828 1209977520936364791
829 1247364517110573010
830 1285884084003855383
831 1325569859408780244
832 1366456460666523904
833 1408579512636474940
834 1451975676448590869
835 1496682679060433596
836 1542739343641197612
837 1590185620804736990
838 1639062620715313659
839 1689412646090219477
840 1741279226123134323
841 1794707151353887124
842 1849742509510755427
843 1906432722351177739
844 1964826583528644384
845 2024974297514046323
846 2086927519599534703
847 2150739397014921271
848 2216464611187219480
849 2284159421173733296
850 2353881708301169820
851 2425691022043886913
852 2499648627174223038
853 2575817552220033420
854 2654262639265253797
855 2735050595129186252
856 2818250043962494148
857 2903931581298651682
858 2992167829599516059
859 3083033495336099795
860 3176605427646447475
861 3272962678612502444
862 3372186565200373655
863 3474360732909324737
864 3579571221174843872
865 3687906530573805727
866 3799457691880740553
867 3914318337024318769
868 4032584771995954370
869 4154356051763528938
870 4279734057243395338
871 4408823574386770873
872 4541732375437821536
873 4678571302420977640
874 4819454352918128815
875 4964498768197644014
876 5113825123757491141
877 5267557422348000419
878 5425823189541234185
879 5588753571914349742
880 5756483437917783268
881 5929151481500638521
882 6106900328566181002
883 6289876646333975045
884 6478231255686895344
885 6672119246581868487
886 6871700096607046756
887 7077137792769952987
888 7288600956601885528
889 7506262972667936297
890 7730302120573966826
891 7960901710562781155
892 8198250222796018478
893 8442541450420461809
894 8693974646518498166
895 8952754675046991379
896 9219092165871197830
897 9493203674001547543
898 9775311843145904344
899 10065645573692493177
900 10364440195240043347
901 10671937643796776302
902 10988386643772651804
903 11314042894890843534
904 11649169264149792243
905 11994035982970203690
906 12348920849663130189
907 12714109437360962953
908 13089895307556441796
909 13476580229396788079
910 13874474404886088077
911 14283896700152620319
912 14705174882940055822
913 15138645866487850172
914 15584655959970011796
915 16043561125663927953
916 16515727243027716284
917 17001530379868749470
918 17501357070788791977
919 18015604603098390856
920 18544681310397682286
921 19089006874023893158
922 19649012632573452263
923 20225141899711527103
924 20817850290485261460
925 21427606056365092340
926 22054890429243840138
927 22700197974627086188
928 23364036954256967510
929 24046929698417270643
930 24749412988171921751
931 25472038447798138512
932 26215372947681720148
933 26979999017946610022
934 27766515273100612165
935 28575536847985855298
936 29407695845327736572
937 30263641795186435199
938 31144042126622349078
939 32049582651892457830
940 32980968063505630512
941 33938922444472757177
942 34924189792093776035
943 35937534555635399229
944 36979742188261834486
945 38051619713587583857
946 39153996307233902155
947 40287723893779664142
948 41453677759504824620
949 42652757181337972817
950 43885886072429374829
951 45154013644779043432
952 46458115089363551550
953 47799192274215995071
954 49178274460922411942
955 50596419040013066660
956 52054712285738561395
957 53554270130730439943
958 55096238961062058655
959 56681796432237967245
960 58312152306650619955
961 59988549313060427818
962 61712264028668604596
963 63484607784363794754
964 65306927593741807984
965 67180607106512280156
966 69107067586918653823
967 71087768917817422953
968 73124210631078230701
969 75217932964980088767
970 77370517949299846393
971 79583590518805920484
972 81858819655885159975
973 84197919563052992590
974 86602650866115206920
975 89074821848765863896
976 91616289719429627833
977 94228961911176420474
978 96914797415553837308
979 99675808151208179107
980 102514060368186084572
981 105431676088827793670
982 108430834586190205483
983 111513773900960676223
984 114682792397843160303
985 117940250362427278577
986 121288571639575459592
987 124730245314385679564
988 128267827436818304997
989 131903942791102003158
990 135641286711057926537
991 139482626942514500935
992 143430805554013635566
993 147488740897035435728
994 151659429617003907840
995 155945948716366818922
996 160351457671071318324
997 164879200601794770905
998 169532508501323290386
999 174314801519501240477
1000 179229591307215428146