0 1
1 0
2 0
3 0
4 0
5 0
6 1
7 1
8 1
9 1
10 1
11 1
12 1
13 2
14 2
15 3
16 3
17 4
18 4
19 5
20 5
21 7
22 7
23 9
24 10
25 12
26 13
27 16
28 17
29 20
30 23
31 26
32 29
33 34
34 38
35 43
36 49
37 55
38 62
39 70
40 79
41 88
42 100
43 111
44 125
45 140
46 157
47 174
48 196
49 217
50 243
51 270
52 301
53 333
54 372
55 411
56 457
57 506
58 561
59 619
60 687
61 757
62 837
63 924
64 1019
65 1122
66 1238
67 1361
68 1498
69 1648
70 1811
71 1988
72 2184
73 2395
74 2626
75 2880
76 3154
77 3453
78 3780
79 4134
80 4519
81 4941
82 5395
83 5891
84 6430
85 7014
86 7646
87 8337
88 9080
89 9889
90 10766
91 11715
92 12740
93 13856
94 15056
95 16359
96 17767
97 19289
98 20931
99 22712
100 24627
101 26699
102 28935
103 31347
104 33946
105 36757
106 39777
107 43037
108 46550
109 50331
110 54401
111 58790
112 63504
113 68580
114 74042
115 79912
116 86221
117 93009
118 100294
119 108123
120 116535
121 125561
122 135250
123 145655
124 156810
125 168778
126 181618
127 195376
128 210126
129 225939
130 242874
131 261015
132 280452
133 301252
134 323522
135 347363
136 372865
137 400147
138 429339
139 460542
140 493909
141 529580
142 567695
143 608420
144 651939
145 698406
146 748034
147 801026
148 857586
149 917949
150 982377
151 1051095
152 1124404
153 1202594
154 1285959
155 1374834
156 1469585
157 1570544
158 1678131
159 1792758
160 1914848
161 2044873
162 2183346
163 2330750
164 2487668
165 2654686
166 2832402
167 3021485
168 3222650
169 3436590
170 3664116
171 3906053
172 4163247
173 4436636
174 4727215
175 5035973
176 5364030
177 5712548
178 6082714
179 6475837
180 6893300
181 7336496
182 7806980
183 8306370
184 8836326
185 9398670
186 9995313
187 10628211
188 11299511
189 12011459
190 12766365
191 13566749
192 14415253
193 15314600
194 16267746
195 17277799
196 18347955
197 19481690
198 20682642
199 21954579
200 23301565
201 24727873
202 26237918
203 27836470
204 29528520
205 31319263
206 33214261
207 35219374
208 37340669
209 39584670
210 41958207
211 44468399
212 47122847
213 49929551
214 52896814
215 56033531
216 59349012
217 62852983
218 66555789
219 70468316
220 74601888
221 78968584
222 83581062
223 88452552
224 93597091
225 99029445
226 104764993
227 110820098
228 117211906
229 123958348
230 131078416
231 138592067
232 146520124
233 154884677
234 163708878
235 173016951
236 182834503
237 193188436
238 204106843
239 215619452
240 227757436
241 240553405
242 254041792
243 268258743
244 283242035
245 299031570
246 315669178
247 333198636
248 351666101
249 371120000
250 391610976
251 413192425
252 435920330
253 459853269
254 485052940
255 511584047
256 539514265
257 568914864
258 599860546
259 632429471
260 666703883
261 702769987
262 740717972
263 780642697
264 822643567
265 866824587
266 913295082
267 962169607
268 1013568013
269 1067616223
270 1124446167
271 1184195851
272 1247010235
273 1313041143
274 1382447408
275 1455395774
276 1532060869
277 1612625353
278 1697280931
279 1786228313
280 1879677454
281 1977848583
282 2080972282
283 2189289686
284 2303053689
285 2422528980
286 2547992377
287 2679734060
288 2818057733
289 2963280941
290 3115736500
291 3275772615
292 3443753388
293 3620060248
294 3805092258
295 3999266586
296 4203020185
297 4416810073
298 4641114006
299 4876432195
300 5123287797
301 5382227565
302 5653823874
303 5938675177
304 6237406918
305 6550673604
306 6879159510
307 7223579620
308 7584682018
309 7963248611
310 8360096364
311 8776079769
312 9212091892
313 9669065628
314 10147976582
315 10649844147
316 11175733103
317 11726756663
318 12304077875
319 12908911340
320 13542526689
321 14206250098
322 14901466415
323 15629622842
324 16392230863
325 17190868545
326 18027184717
327 18902901118
328 19819815133
329 20779804308
330 21784828949
331 22836935142
332 23938259867
333 25091033883
334 26297585293
335 27560345100
336 28881850623
337 30264749500
338 31711805901
339 33225904400
340 34810054599
341 36467397933
342 38201212217
343 40014916814
344 41912080259
345 43896425409
346 45971835356
347 48142361868
348 50412231296
349 52785851276
350 55267820110
351 57862933490
352 60576192142
353 63412812206
354 66378232934
355 69478125334
356 72718403696
357 76105234396
358 79645045634
359 83344540300
360 87210705935
361 91250825779
362 95472493064
363 99883622351
364 104492461981
365 109307610021
366 114338027062
367 119593050371
368 125082411538
369 130816251079
370 136805134310
371 143060071071
372 149592532195
373 156414467477
374 163538327558
375 170977082642
376 178744242624
377 186853881616
378 195320658939
379 204159841937
380 213387333165
381 223019694202
382 233074171231
383 243568725428
384 254522059719
385 265953647666
386 277883767185
387 290333530887
388 303324918359
389 316880813926
390 331025040640
391 345782396710
392 361178697453
393 377240813680
394 393996712469
395 411475504068
396 429707484889
397 448724183476
398 468558412580
399 489244317678
400 510817428350
401 533314716490
402 556774650665
403 581237253860
404 606744168211
405 633338716189
406 661065965128
407 689972799590
408 720107989794
409 751522264112
410 784268389518
411 818401248488
412 853977920047
413 891057769547
414 929702534714
415 969976416517
416 1011946179024
417 1055681245998
418 1101253802358
419 1148738905628
420 1198214593910
421 1249761999495
422 1303465472926
423 1359412703919
424 1417694848276
425 1478406666180
426 1541646657325
427 1607517202906
428 1676124719473
429 1747579810182
430 1821997423260
431 1899497023441
432 1980202760933
433 2064243648439
434 2151753751957
435 2242872379617
436 2337744279181
437 2436519850574
438 2539355356622
439 2646413143553
440 2757861877445
441 2873876779518
442 2994639872078
443 3120340241655
444 3251174301520
445 3387346065959
446 3529067442979
447 3676558527215
448 3830047905566
449 3989772982873
450 4155980308454
451 4328925916681
452 4508875689238
453 4696105719005
454 4890902689505
455 5093564277667
456 5304399559261
457 5523729431490
458 5751887060714
459 5989218334028
460 6236082329715
461 6492851814840
462 6759913748131
463 7037669803436
464 7326536922786
465 7626947876012
466 7939351843180
467 8264215029030
468 8602021285667
469 8953272760304
470 9318490577831
471 9698215533325
472 10093008812421
473 10503452749154
474 10930151596155
475 11373732325229
476 11834845468882
477 12314165976403
478 12812394103555
479 13330256346616
480 13868506393806
481 14427926113485
482 15009326590962
483 15613549185227
484 16241466626629
485 16893984167078
486 17572040753770
487 18276610247809
488 19008702700210
489 19769365654926
490 20559685501593
491 21380788890478
492 22233844179014
493 23120062932600
494 24040701493733
495 24997062586869
496 25990496983512
497 27022405241525
498 28094239485530
499 29207505253428
500 30363763424202
501 31564632192159
502 32811789114515
503 34106973247196
504 35451987333909
505 36848700075542
506 38299048496363
507 39805040370211
508 41368756735486
509 42992354515626
510 44678069207719
511 46428217668542
512 48245201016452
513 50131507609519
514 52089716131567
515 54122498804391
516 56232624686227
517 58422963088814
518 60696487132698
519 63056277399215
520 65505525713407
521 68047539077830
522 70685743715318
523 73423689255415
524 76265053086514
525 79213644829520
526 82273410970178
527 85448439672560
528 88742965728658
529 92161375682550
530 95708213153160
531 99388184308782
532 103206163534277
533 107167199315290
534 111276520292315
535 115539541526476
536 119961871003380
537 124549316326124
538 129307891641502
539 134243824826940
540 139363564888224
541 144673789613732
542 150181413514720
543 155893595999707
544 161817749831600
545 167961549897982
546 174332942241859
547 180940153403505
548 187791700105564
549 194896399227411
550 202263378121922
551 209902085308356
552 217822301486577
553 226034150927636
554 234548113277012
555 243375035713963
556 252526145525057
557 262013063130142
558 271847815502852
559 282042850046831
560 292611048967899
561 303565744083185
562 314920732131641
563 326690290628039
564 338889194200876
565 351532731481450
566 364636722588873
567 378217537150540
568 392292112928335
569 406877975098526
570 421993256123421
571 437656716289052
572 453887764959621
573 470706482485764
574 488133642844930
575 506190737067634
576 524899997385748
577 544284422185623
578 564367801822471
579 585174745232219
580 606730707427379
581 629062017937377
582 652195910128837
583 676160551496988
584 700985074992523
585 726699611319085
586 753335322297246
587 780924435364070
588 809500279142233
589 839097320180950
590 869751200941296
591 901498778960570
592 934378167303232
593 968428776375942
594 1003691357041392
595 1040208045144777
596 1078022407535158
597 1117179489517590
598 1157725863855249
599 1199709681410597
600 1243180723360994
601 1288190455115887
602 1334792082030027
603 1383040606849361
604 1432992889024005
605 1484707705989529
606 1538245816353947
607 1593670025133748
608 1651045251145967
609 1710438596496627
610 1771919418316295
611 1835559402858345
612 1901432641901571
613 1969615711617567
614 2040187754026293
615 2113230560984429
616 2188828660876148
617 2267069408139667
618 2348043075575756
619 2431842949619954
620 2518565428720108
621 2608310124770031
622 2701179967791812
623 2797281314019092
624 2896724057335958
625 2999621744276803
626 3106091692749910
627 3216255114445398
628 3330237241144666
629 3448167455107809
630 3570179423503727
631 3696411237115615
632 3827005553510654
633 3962109744645364
634 4101876049154495
635 4246461729526867
636 4396029234146290
637 4550746364463088
638 4710786447513650
639 4876328513775927
640 5047557480642930
641 5224664341749486
642 5407846362148847
643 5597307279640863
644 5793257512504840
645 5995914373644605
646 6205502291467785
647 6422253037773005
648 6646405962663065
649 6878208236830079
650 7117915101506278
651 7365790126112808
652 7622105473976392
653 7887142176430672
654 8161190415349472
655 8444549814508312
656 8737529740115550
657 9040449610577943
658 9353639215924049
659 9677439047255361
660 10012200636307319
661 10358286905575165
662 10716072529403630
663 11085944306143099
664 11468301541860667
665 11863556446036860
666 12272134539373398
667 12694475074237013
668 13131031468203530
669 13582271750854258
670 14048679024387457
671 14530751938547380
672 15029005180050842
673 15543969977115812
674 16076194619635711
675 16626244995210119
676 17194705141681878
677 17782177816768987
678 18389285085035356
679 19016668922900632
680 19664991842324640
681 20334937533448885
682 21027211526948575
683 21742541876782280
684 22481679863664049
685 23245400720068582
686 24034504377513263
687 24849816236488153
688 25692187959906180
689 26562498290879456
690 27461653895242789
691 28390590229764382
692 29350272436916650
693 30341696266682743
694 31365889026413095
695 32423910559676255
696 33516854254641057
697 34645848083083830
698 35812055671042678
699 37016677401723539
700 38260951551837041
701 39546155462473402
702 40873606745194022
703 42244664524610593
704 43660730718652684
705 45123251357281676
706 46633717941023466
707 48193668840620856
708 49804690738651280
709 51468420114591898
710 53186544774741438
711 54960805427940718
712 56792997308692968
713 58684971849209919
714 60638638401432595
715 62655966010754752
716 64738985243103942
717 66889790066544099
718 69110539789266237
719 71403461055761516
720 73770849902466513
721 76215073874897379
722 78738574208218967
723 81343868072674768
724 84033550886059156
725 86810298695340021
726 89676870629009116
727 92636111422517830
728 95690954019083712
729 98844422247609468
730 102099633580263569
731 105459801972199750
732 108928240785337441
733 112508365798957748
734 116203698309803170
735 120017868323796445
736 123954617842359328
737 128017804246245351
738 132211403779214684
739 136539515134775730
740 141006363149153146
741 145616302603041872
742 150373822135636953
743 155283548274363298
744 160350249583119824
745 165578840932811706
746 170974387897885326
747 176542111281954833
748 182287391776603859
749 188215774757390392
750 194332975220443466
751 200644882864070266
752 207157567319742703
753 213877283536176127
754 220810477321284686
755 227963791046748686
756 235344069519262879
757 242958366023643523
758 250813948542928773
759 258918306159927412
760 267279155645820714
761 275904448241384115
762 284802376635704959
763 293981382148461051
764 303450162121798351
765 313217677527138188
766 323293160793481005
767 333686123863752853
768 344406366485020699
769 355463984739686391
770 366869379824756328
771 378633267085551435
772 390766685311556038
773 403281006302097579
774 416187944708809623
775 429499568163210836
776 443228307697740371
777 457386968467837370
778 471988740784085921
779 487047211463467393
780 502576375507998001
781 518590648120518671
782 535104877067439739
783 552134355397465804
784 569694834526877799
785 587802537701995456
786 606474173848660396
787 625726951820191059
788 645578595055323046
789 666047356656858746
790 687152034903423795
791 708911989206808576
792 731347156526577772
793 754478068255368323
794 778325867588401034
795 802912327389926106
796 828259868571133480
797 854391578994184488
798 881331232916211121
799 909103310989015620
800 937733020830351066
801 967246318181851206
802 997669928670642818
803 1029031370191845275
804 1061358975928352541
805 1094681918026335287
806 1129030231945104292
807 1164434841499166419
808 1200927584612431300
809 1238541239804764961
810 1277309553430276792
811 1317267267688944811
812 1358450149433457496
813 1400895019792343150
814 1444639784632774942
815 1489723465886747651
816 1536186233763524943
817 1584069439873672411
818 1633415651290339793
819 1684268685572671602
820 1736673646778744493
821 1790676962495825241
822 1846326421914972291
823 1903671214979631963
824 1962761972638329114
825 2023650808230794639
826 2086391360039619407
827 2151038835040027579
828 2217650053879622476
829 2286283497122833081
830 2356999352795348173
831 2429859565263112114
832 2504927885483461530
833 2582269922666603584
834 2661953197384955660
835 2744047196171006606
836 2828623427645052995
837 2915755480213517234
838 3005519081381837563
839 3097992158726694417
840 3193254902571725192
841 3291389830414320720
842 3392481853151953039
843 3496618343155914729
844 3603889204243958043
845 3714386943604265800
846 3828206745722669026
847 3945446548368808395
848 4066207120697974907
849 4190592143524911035
850 4318708291829814204
851 4450665319557933236
852 4586576146773757741
853 4726556949234954691
854 4870727250452473277
855 5019210016302919548
856 5172131752263663968
857 5329622603342538595
858 5491816456773739097
859 5658851047556133215
860 5830868066911701272
861 6008013273741688696
862 6190436609162867803
863 6378292314207976419
864 6571739050774359931
865 6770940025909905522
866 6976063119527188028
867 7187281015636821213
868 7404771337196328025
869 7628716784672853675
870 7859305278418239210
871 8096730104960576600
872 8341190067318562089
873 8592889639445296409
874 8852039124914083185
875 9118854819961172952
876 9393559181000886479
877 9676380996734771292
878 9967555564979055721
879 10267324874335327382
880 10575937790835912083
881 10893650249698282535
882 11220725452323672143
883 11557434068681975464
884 11904054445228129529
885 12260872818496218229
886 12628183534524830024
887 13006289274270591508
888 13395501285168066530
889 13796139619001911342
890 14208533376260862170
891 14633020957144649642
892 15069950319403065234
893 15519679243190414796
894 15982575603120383694
895 16459017647714927676
896 16949394286445164656
897 17454105384564328698
898 17973562065941922822
899 18508187024112954986
900 19058414841758541513
901 19624692318843767681
902 20207478809643849634
903 20807246568892391077
904 21424481107295696587
905 22059681556662696867
906 22713361044903173536
907 23386047081157739255
908 24078281951329093600
909 24790623124287631613
910 25523643669035880320
911 26277932683122824009
912 27054095732603186011
913 27852755303848813125
914 28674551267526453592
915 29520141355060716032
916 30390201647913804361
917 31285427080021369789
918 32206531953728847799
919 33154250469586241028
920 34129337270367694082
921 35132567999687821111
922 36164739875601168547
923 37226672279580276573
924 38319207361274053437
925 39443210659463483196
926 40599571739641522424
927 41789204848650979346
928 43013049586830419773
929 44272071598128797746
930 45567263278657183211
931 46899644504163230852
932 48270263376925560286
933 49680196992573696210
934 51130552227357579675
935 52622466546403125941
936 54157108833499658323
937 55735680242984573711
938 57359415074304069226
939 59029581669839067852
940 60747483336606242677
941 62514459292458612475
942 64331885637421512607
943 66201176350821834428
944 68123784314884183564
945 70101202365480041687
946 72134964370739532667
947 74226646338252421319
948 76377867551598600655
949 78590291736973372046
950 80865628260691209315
951 83205633358366627289
952 85612111396597453705
953 88086916167995659213
954 90631952220427236562
955 93249176221351039477
956 95940598358167936224
957 98708283775509483375
958 101554354050425610205
959 104480988706453962316
960 107490426767573031897
961 110584968353073494478
962 113766976314407165991
963 117038877915094234697
964 120403166554803866639
965 123862403538750247401
966 127419219893569273778
967 131076318230877850771
968 134836474659746835297
969 138702540749343883521
970 142677445543041654377
971 146764197625318200640
972 150965887242803813798
973 155285688480870415543
974 159726861497193437621
975 164292754813745952663
976 168986807668729474226
977 173812552429982340958
978 178773617071438997283
979 183873727714261171697
980 189116711234301291492
981 194506497937593657566
982 200047124305619833316
983 205742735812137096697
984 211597589813396997611
985 217616058513635457684
986 223802632007761544164
987 230161921403213473234
988 236698662023008510480
989 243417716692062679381
990 250324079108901086840
991 257422877304941779512
992 264719377193589095158
993 272218986211421115292
994 279927257053822212837
995 287849891507468822080
996 295992744382129244861
997 304361827544309271840
998 312963314055336925952
999 321803542416536676205
1000 330889020924219335986