0 1
1 0
2 0
3 0
4 0
5 0
6 0
7 0
8 0
9 1
10 1
11 1
12 1
13 1
14 1
15 1
16 1
17 1
18 2
19 2
20 3
21 3
22 4
23 4
24 5
25 5
26 6
27 7
28 8
29 9
30 11
31 12
32 14
33 16
34 18
35 20
36 24
37 26
38 30
39 34
40 39
41 43
42 50
43 55
44 63
45 71
46 80
47 89
48 102
49 113
50 128
51 143
52 161
53 179
54 203
55 225
56 253
57 282
58 316
59 351
60 395
61 437
62 489
63 544
64 607
65 673
66 752
67 832
68 927
69 1028
70 1143
71 1264
72 1407
73 1554
74 1725
75 1908
76 2114
77 2334
78 2587
79 2853
80 3157
81 3483
82 3848
83 4240
84 4685
85 5157
86 5689
87 6263
88 6902
89 7590
90 8363
91 9188
92 10111
93 11108
94 12212
95 13404
96 14731
97 16156
98 17738
99 19450
100 21337
101 23376
102 25633
103 28064
104 30748
105 33653
106 36843
107 40295
108 44097
109 48198
110 52706
111 57585
112 62929
113 68711
114 75053
115 81902
116 89402
117 97521
118 106387
119 115981
120 126469
121 137798
122 150168
123 163553
124 178137
125 193911
126 211107
127 229684
128 249917
129 271797
130 295588
131 321305
132 349277
133 379486
134 412315
135 447795
136 486300
137 527899
138 573051
139 621794
140 674663
141 731755
142 793616
143 860399
144 932758
145 1010822
146 1095350
147 1186563
148 1285246
149 1391697
150 1506852
151 1631002
152 1765232
153 1909958
154 2066320
155 2234856
156 2416910
157 2613044
158 2824808
159 3052944
160 3299111
161 3564224
162 3850231
163 4158122
164 4490132
165 4847512
166 5232681
167 5647160
168 6093767
169 6574171
170 7091606
171 7648120
172 8247253
173 8891449
174 9584807
175 10330053
176 11131875
177 11993554
178 12920264
179 13915875
180 14986356
181 16136043
182 17371764
183 18698670
184 20124332
185 21654776
186 23298702
187 25062913
188 26957336
189 28989956
190 31171842
191 33512273
192 36023943
193 38717341
194 41606929
195 44704936
196 48027539
197 51588877
198 55407453
199 59499275
200 63885401
201 68584367
202 73619802
203 79013053
204 84791073
205 90978053
206 97604627
207 104698689
208 112294667
209 120424555
210 129127566
211 138439960
212 148406266
213 159068111
214 170475599
215 182676353
216 195727333
217 209682503
218 224606471
219 240560987
220 257618809
221 275850381
222 295338308
223 316162387
224 338416198
225 362190792
226 387591592
227 414722266
228 443702327
229 474649105
230 507697870
231 542982178
232 580654447
233 620866420
234 663790657
235 709598789
236 758485916
237 810646998
238 866301838
239 925671552
240 989004695
241 1056551132
242 1128591627
243 1205409484
244 1287320903
245 1374646682
246 1467743967
247 1566974976
248 1672742728
249 1785457193
250 1905572093
251 2033550969
252 2169905752
253 2315159324
254 2469888813
255 2634685166
256 2810197755
257 2997093838
258 3196105324
259 3407984200
260 3633554818
261 3873665827
262 4129244246
263 4401247104
264 4690718171
265 4998734985
266 5326472061
267 5675143911
268 6046070449
269 6440619614
270 6860276129
271 7306578756
272 7781196703
273 8285862206
274 8822449801
275 9392908389
276 9999344551
277 10643948550
278 11329086612
279 12057221585
280 12831008863
281 13653216322
282 14526825367
283 15454943854
284 16440917703
285 17488237786
286 18600656146
287 19782092041
288 21036754376
289 22369039844
290 23783667936
291 25285572155
292 26880040894
293 28572607605
294 30369199442
295 32276018558
296 34299705524
297 36447212941
298 38725976247
299 41143786192
300 43708969254
301 46430250134
302 49316949888
303 52378839747
304 55626348588
305 59070415634
306 62722709848
307 66595471640
308 70701753228
309 75055250860
310 79670557106
311 84562991958
312 89748869981
313 95245319328
314 101070574058
315 107243782926
316 113785316635
317 120716575944
318 128060317394
319 135840448409
320 144082383242
321 152812827166
322 162060151560
323 171854177879
324 182226575832
325 193210633711
326 204841692994
327 217156907524
328 230195702185
329 243999533048
330 258612375112
331 274080468377
332 290452849732
333 307781087960
334 326119846362
335 345526620577
336 366062337533
337 387791079619
338 410780737330
339 435102723276
340 460832663955
341 488050119298
342 516839320482
343 547288876879
344 579492579490
345 613549099842
346 649562843317
347 687643657905
348 727907745494
349 770477360707
350 815481803008
351 863057110929
352 913347118027
353 966503163071
354 1022685219686
355 1082061601229
356 1144810190013
357 1211118143630
358 1281183205925
359 1355213438251
360 1433428624157
361 1516060002604
362 1603351796595
363 1695560956676
364 1792958794470
365 1895830764007
366 2004478214804
367 2119218186566
368 2240385316560
369 2368331658217
370 2503428723693
371 2646067358056
372 2796659934849
373 2955640260247
374 3123465962282
375 3300618438528
376 3487605419296
377 3684960996109
378 3893248381123
379 4113059989766
380 4345020444032
381 4589786726470
382 4848051408503
383 5120542919522
384 5408029027471
385 5711317196636
386 6031258376655
387 6368747471089
388 6724727417106
389 7100189816722
390 7496179341912
391 7913794502431
392 8354192442708
393 8818589874868
394 9308268252532
395 9824574931236
396 10368928762126
397 10942821455966
398 11547823676167
399 12185586643204
400 12857848716524
401 13566437314087
402 14313276037966
403 15100386888854
404 15929898030163
405 16804046345946
406 17725185839973
407 18695790627592
408 19718464038812
409 20795942030323
410 21931103107972
411 23126972221513
412 24386731512751
413 25713724803690
414 27111469258470
415 28583660461240
416 30134185131394
417 31767126873131
418 33486779965013
419 35297655916988
420 37204498446777
421 39212290855031
422 41326272359908
423 43551946397176
424 45895098353509
425 48361804960331
426 50958453570016
427 53691752674830
428 56568752936465
429 59596858969757
430 62783852194817
431 66137904095082
432 69667601076766
433 73381959261883
434 77290451615979
435 81403024459081
436 85730126967933
437 90282729667807
438 95072356547317
439 100111105631590
440 105411684034496
441 110987430852158
442 116852355310730
443 123021162310908
444 129509293977090
445 136332958009040
446 143509173039057
447 151055800103131
448 158991592032187
449 167336228460868
450 176110369648662
451 185335695256016
452 195034963105856
453 205232052135419
454 215952026415996
455 227221182811569
456 239067120766503
457 251518795000735
458 264606591710154
459 278362386831134
460 292819629092557
461 308013404525685
462 323980527027389
463 340759609577472
464 358391163128332
465 376917675226149
466 396383717826071
467 416836034180265
468 438323656430174
469 460898001399671
470 484612999001106
471 509525197840722
472 535693905247333
473 563181303794555
474 592052604053669
475 622376172903742
476 654223700326722
477 687670340688023
478 722794894659203
479 759679964884210
480 798412154453659
481 839082238133281
482 881785379072342
483 926621317133132
484 973694605278075
485 1023114816818072
486 1074996803319537
487 1129460922348712
488 1186633319047267
489 1246646176373866
490 1309638022264566
491 1375754004706111
492 1445146226860064
493 1517974049068970
494 1594404454693972
495 1674612381654228
496 1758781121504013
497 1847102683507804
498 1939778230031491
499 2037018475936157
500 2139044163804930
501 2246086502029762
502 2358387683195155
503 2476201364719439
504 2599793234364364
505 2729441537103105
506 2865437692269682
507 3008086871027963
508 3157708669509582
509 3314637741852517
510 3479224534452823
511 3651835979395857
512 3832856295609268
513 4022687748352125
514 4221751522949661
515 4430488556733639
516 4649360491967956
517 4878850586556290
518 5119464753583624
519 5371732558119088
520 5636208350772804
521 5913472358818346
522 6204131922286733
523 6508822687653118
524 6828209955991345
525 7162989988696513
526 7513891477317294
527 7881676971891736
528 8267144483433425
529 8671129045615325
530 9094504462129647
531 9538185013945029
532 10003127364011940
533 10490332423692128
534 11000847428939826
535 11535767979847845
536 12096240303974917
537 12683463484774855
538 13298691928216498
539 13943237797569155
540 14618473701489815
541 15325835353238537
542 16066824500328363
543 16843011828480060
544 17656040153697560
545 18507627593404635
546 19399571044305195
547 20333749644082073
548 21312128560797135
549 22336762771288112
550 23409801189028750
551 24533490788025735
552 25710181099134781
553 26942328709649219
554 28232502161069549
555 29583386857983435
556 30997790401964831
557 32478647946687977
558 34029028006445975
559 35652138296419210
560 37351332058064964
561 39130114427689892
562 40992149323321765
563 42941266388932979
564 44981468492135993
565 47116939294157886
566 49352051412430379
567 51691374671673708
568 54139684988690993
569 56701973365199215
570 59383455558034835
571 62189581878123006
572 65126047715243871
573 68198804214091933
574 71414069727138751
575 74778341445381585
576 78298407860191349
577 81981361431401498
578 85834612146519479
579 89865901317001719
580 94083316329067129
581 98495305667382124
582 103110694960912964
583 107938703339968502
584 112988960889959124
585 118271526458007494
586 123796906635247200
587 129576075139773091
588 135620493459627074
589 141942131947733855
590 148553492269622123
591 155467630358852322
592 162698180823717711
593 170259381924999526
594 178166102110335575
595 186433867187766717
596 195078889171465751
597 204118095840680031
598 213569162093836200
599 223450542099300573
600 233781503373000785
601 244582161742576530
602 255873518382598103
603 267677497833953064
604 280016988248038652
605 292915882724461893
606 306399123038359031
607 320492744579123759
608 335223923858901006
609 350621027360541044
610 366713663147693905
611 383532733956982221
612 401110493258743007
613 419480602953769326
614 438678194263904785
615 458739930425749860
616 479704072819135459
617 501610549084009497
618 524501024930817294
619 548418978139398877
620 573409776533351411
621 599520758360081520
622 626801316948239920
623 655302988010747091
624 685079541549664449
625 716187076665845121
626 748684121323609897
627 782631735301390379
628 818093618475964074
629 855136222602292738
630 893828868834039174
631 934243869074301238
632 976456653509659898
633 1020545902337326259
634 1066593684150497026
635 1114685598915322013
636 1164910928116999005
637 1217362789928227651
638 1272138302101791629
639 1329338750352448452
640 1389069765058868238
641 1451441503966490927
642 1516568843851834452
643 1584571578740751656
644 1655574627784275708
645 1729708250287707971
646 1807108271145254312
647 1887916314083200392
648 1972280046113952619
649 2060353430506983463
650 2152296991844017588
651 2248278090358441492
652 2348471209297871882
653 2453058252408521748
654 2562228855453926556
655 2676180708760829596
656 2795119894895315274
657 2919261238346461602
658 3048828671518919538
659 3184055613801499692
660 3325185368214384231
661 3472471532287209221
662 3626178427890952959
663 3786581546550758636
664 3953968015192191037
665 4128637078729066545
666 4310900604678863640
667 4501083606090148704
668 4699524788223179373
669 4906577115133621731
670 5122608401866680816
671 5348001928284132134
672 5583157080502982754
673 5828490015836135974
674 6084434357509800672
675 6351441914904664759
676 6629983435904641238
677 6920549386965090383
678 7223650767800333282
679 7539819956162764794
680 7869611589957397925
681 8213603482012999647
682 8572397575113226253
683 8946620932467427457
684 9336926771593108942
685 9743995536644180996
686 10168536017557534077
687 10611286510894843223
688 11073016031171258343
689 11554525567402113507
690 12056649394089987281
691 12580256431234085818
692 13126251663051595454
693 13695577609832265380
694 14289215863105365025
695 14908188678393232255
696 15553560636234763754
697 16226440365603709024
698 16927982340951410601
699 17659388746838403120
700 18421911421957377158
701 19216853876367902715
702 20045573394336900109
703 20909483216460432942
704 21810054814100808712
705 22748820249659607110
706 23727374636392457797
707 24747378691151106280
708 25810561394453861632
709 26918722751136250625
710 28073736666734347448
711 29277553932710263962
712 30532205336461909740
713 31839804889108351813
714 33202553187811895144
715 34622740905514361985
716 36102752425732785205
717 37645069615171888529
718 39252275752728675722
719 40927059607555933739
720 42672219685726791877
721 44490668638084843192
722 46385437849864559618
723 48359682204581291784
724 50416685043873621020
725 52559863315748416609
726 54792772934055110879
727 57119114341604128307
728 59542738300988221721
729 62067651905488027506
730 64698024835419735241
731 67438195852317175055
732 70292679557662204563
733 73266173408587121319
734 76363565018722662397
735 79589939736654892514
736 82950588531705048342
737 86451016179590334807
738 90096949779290744625
739 93894347593803966716
740 97849408247846387423
741 101968580275322993657
742 106258572051454918226
743 110726362102596320504
744 115379209830547408106
745 120224666644645162858
746 125270587540500411558
747 130525143118940572447
748 135996832086207037142
749 141694494229328738082
750 147627323910009198290
751 153804884071366617429
752 160237120803322747356
753 166934378461440680384
754 173907415387609459383
755 181167420227940932242
756 188726028899012359017
757 196595342198460274042
758 204787944113996541181
759 213316920827553674176
760 222195880471742300473
761 231438973636159421722
762 241060914684007009599
763 251077003877489980214
764 261503150375969921317
765 272355896106359882625
766 283652440573465510909
767 295410666610935561536
768 307649167144459122466
769 320387272969179604123
770 333645081617181438200
771 347443487318443463853
772 361804212135591599411
773 376749838277469283000
774 392303841676585281342
775 408490626837249549832
776 425335563044526475280
777 442865021942764840044
778 461106416579217747847
779 480088241923709631690
780 499840116965555858574
781 520392828401105835731
782 541778376019218322643
783 564030019800660009438
784 587182328845222114577
785 611271232145475691972
786 636334071327825988276
787 662409655382992729510
788 689538317513935985240
789 717761974126830069047
790 747124186100931278022
791 777670222366801688234
792 809447125937027982128
793 842503782423109640571
794 876890991191543026213
795 912661539197336299700
796 949870277657438829690
797 988574201607357540584
798 1028832532513475304672
799 1070706803989828232240
800 1114260950802605326341
801 1159561401217059401191
802 1206677172881536410484
803 1255679972309835656156
804 1306644298168757735432
805 1359647548439141086925
806 1414770131670259745783
807 1472095582403543061920
808 1531710680999354913538
809 1593705577951186498321
810 1658173922935732761683
811 1725212998692311179345
812 1794923859995873341219
813 1867411477826898686675
814 1942784889019238650154
815 2021157351499939927422
816 2102646505419998686109
817 2187374540301707171141
818 2275468368520697511844
819 2367059805260895076764
820 2462285755280907026331
821 2561288406643734541717
822 2664215431770063961940
823 2771220195981820386594
824 2882461973919508256703
825 2998106174015974508482
826 3118324571434937826142
827 3243295549674263965804
828 3373204351268756256449
829 3508243337811183994194
830 3648612259754612819604
831 3794518536234955427487
832 3946177545406996438641
833 4103812925554727122232
834 4267656887501405027550
835 4437950538603835323768
836 4614944218890721851389
837 4798897849655065291921
838 4990081295097206153022
839 5188774737356097936670
840 5395269065564576466144
841 5609866279295989124172
842 5832879907079881014623
843 6064635440386152747465
844 6305470783800150914795
845 6555736721822783764761
846 6815797403065853153891
847 7086030842314069816491
848 7366829441275035141810
849 7658600528528863200203
850 7961766919553282693745
851 8276767497379340347761
852 8604057814811738082634
853 8944110718815718655469
854 9297416998066818403672
855 9664486054315717162480
856 10045846598631026610334
857 10442047373226558806907
858 10853657900006895007423
859 11281269256596252097962
860 11725494881060432177518
861 12186971406149680575239
862 12666359524353383293791
863 13164344884662180860041
864 13681639022415034467373
865 14218980323199699297415
866 14777135022276822152703
867 15356898240574414731255
868 15959095058821934216953
869 16584581630955081321086
870 17234246338466248142477
871 17909010986922417924399
872 18609832046438556186085
873 19337701937425692076703
874 20093650363522578803178
875 20878745693134987634069
876 21694096391620559346734
877 22540852505655938646668
878 23420207201962179619240
879 24333398362046103380719
880 25281710235281123425575
881 26266475152115346370378
882 27289075299888008941201
883 28350944563181819033881
884 29453570431360816028846
885 30598495975371301885358
886 31787321896635576889448
887 33021708650277283394152
888 34303378645700465995569
889 35634118526934266123806
890 37015781535971157750574
891 38450289961696357619116
892 39939637677856244093457
893 41485892772862969266407
894 43091200275118014067375
895 44757784976866015703652
896 46487954360512900975839
897 48284101630649313234589
898 50148708855981908689224
899 52084350224660145503842
900 54093695417488006649785
901 56179513102772851843098
902 58344674557607662511485
903 60592157419622526701175
904 62925049574329526115311
905 65346553182401342532699
906 67859988852358035279499
907 70468799963328802611112
908 73176557143737800543177
909 75986962910930770120541
910 78903856477991897549774
911 81931218733143109227645
912 85073177398402929373680
913 88334012373299577462711
914 91718161270772798649585
915 95230225151490355563144
916 98874974464202441161429
917 102657355198822438653091
918 106582495260379454259609
919 110655711071026677311969
920 114882514408809313367195
921 119268619490907065465257
922 123819950310651540587823
923 128542648236602721656619
924 133443079883622281391503
925 138527845264837630506432
926 143803786235115933278192
927 149277995235594982731369
928 154957824350618352603836
929 160850894687321500371473
930 166965106089994164510670
931 173308647200215196389868
932 179890005875716773419316
933 186717979979776554563236
934 193801688554983301021167
935 201150583394034135623499
936 208774461022358206909051
937 216683475106145321791154
938 224888149301588937625004
939 233399390559907258889277
940 242228502905035894431969
941 251387201699610878712899
942 260887628417293539950432
943 270742365938185374619511
944 280964454386622055192496
945 291567407529303302436677
946 302565229754369998639874
947 313972433650679171639802
948 325804058209300608987468
949 338075687667870396516474
950 350803471021334447607233
951 364004142221198766086455
952 377695041088431861174586
953 391894134963721640130558
954 406620041121954345150927
955 421892049976314255875066
956 437730149100711829625018
957 454155048097753566739423
958 471188204342926835092127
959 488851849634154523313231
960 507169017779492011881956
961 526163573154198118246442
962 545860240262195270031145
963 566284634335371537006086
964 587463293008135224654374
965 609423709103050476929505
966 632194364567522763603666
967 655804765599903382183641
968 680285479007714562119444
969 705668169839080807705748
970 731985640332986528292396
971 759271870232350761474439
972 787562058508655475347462
973 816892666545224340746671
974 847301462831217103421023
975 878827569216756803098618
976 911511508784809498513834
977 945395255393783850999955
978 980522284950265520845770
979 1016937628469648543897575
980 1054687926988131848956937
981 1093821488387898869059219
982 1134388346203276199803288
983 1176440320474024681269914
984 1220031080718179331209693
985 1265216211095224811742665
986 1312053277836956678369392
987 1360601899021766065258328
988 1410923816774965531029242
989 1463082971976184875591893
990 1517145581562077771245214
991 1573180218511021585792226
992 1631257894604054917720145
993 1691452146054775250441638
994 1753839122108850188606095
995 1818497676712318344294852
996 1885509463356174248011338
997 1954959033203307695595458
998 2026933936612594830256649
999 2101524828173575613683897
1000 2178825575374309959384688