0 1
1 0
2 0
3 0
4 1
5 0
6 0
7 0
8 1
9 1
10 0
11 1
12 1
13 1
14 1
15 1
16 5
17 1
18 2
19 2
20 6
21 11
22 3
23 3
24 7
25 16
26 23
27 8
28 9
29 18
30 38
31 44
32 24
33 21
34 44
35 79
36 86
37 59
38 52
39 96
40 157
41 163
42 141
43 118
44 199
45 295
46 318
47 304
48 259
49 387
50 549
51 613
52 632
53 534
54 736
55 1006
56 1179
57 1240
58 1070
59 1364
60 1842
61 2217
62 2366
63 2074
64 2508
65 3333
66 4104
67 4374
68 3935
69 4547
70 5997
71 7436
72 7942
73 7298
74 8189
75 10658
76 13255
77 14133
78 13312
79 14587
80 18762
81 23217
82 24830
83 23858
84 25765
85 32608
86 40119
87 43019
88 42152
89 44994
90 56082
91 68411
92 73749
93 73385
94 77805
95 95346
96 115403
97 125018
98 126146
99 133050
100 160523
101 192649
102 209925
103 214127
104 225244
105 267566
106 318748
107 349051
108 359428
109 377356
110 442118
111 522840
112 575304
113 596789
114 626195
115 724277
116 850994
117 939849
118 981208
119 1029321
120 1177356
121 1374652
122 1522946
123 1598092
124 1677282
125 1899384
126 2205043
127 2448108
128 2580399
129 2710001
130 3042813
131 3512867
132 3906053
133 4132227
134 4344165
135 4841324
136 5560313
137 6187253
138 6566866
139 6910910
140 7653388
141 8745659
142 9734386
143 10359991
144 10916045
145 12022925
146 13673341
147 15215077
148 16232758
149 17124306
150 18774248
151 21252652
152 23635106
153 25268977
154 26689825
155 29145775
156 32848723
157 36497333
158 39093563
159 41340052
160 44993815
161 50496350
162 56042657
163 60125349
164 63653841
165 69081018
166 77220589
167 85590173
168 91954455
169 97454857
170 105507075
171 117491424
172 130042980
173 139877302
174 148395315
175 160319267
176 177894510
177 196603145
178 211683068
179 224782077
180 242409441
181 268081651
182 295818810
183 318766977
184 338784315
185 364783949
186 402154573
187 443062891
188 477745879
189 508139457
190 546405681
191 600620890
192 660671716
193 712739261
194 758617129
195 814794535
196 893210500
197 980957677
198 1058644046
199 1127489270
200 1209758896
201 1322842685
202 1450521716
203 1565741395
204 1668490846
205 1788644434
206 1951284559
207 2136306856
208 2306250660
209 2458780258
210 2633796648
211 2867089171
212 3134187188
213 3383510938
214 3608802730
215 3863013448
216 4196824378
217 4580976357
218 4944939317
219 5276071175
220 5644287949
221 6120756568
222 6671333687
223 7200105019
224 7684544894
225 8216365128
226 8894873722
227 9681299527
228 10446056811
229 11151585342
230 11917529877
231 12881505793
232 14001201280
233 15102490140
234 16125601281
235 17225563427
236 18592037185
237 20181258930
238 21760712110
239 23238177243
240 24813339367
241 26746021716
242 28994950883
243 31251320686
244 33376421620
245 35625632688
246 38353143604
247 41526443253
248 44737885163
249 47782697796
250 50985366134
251 54826137627
252 59291370658
253 63845850773
254 68192251393
255 72739727349
256 78136476555
257 84402747667
258 90839998773
259 97022085857
260 103461188228
261 111027908736
262 119798955011
263 128867557157
264 137630232566
265 146722732393
266 157309343627
267 169555554617
268 182291195394
269 194670021355
270 207474580414
271 222254819234
272 239311645812
273 257143251786
274 274573996763
275 292557757474
276 313149426462
277 336850522765
278 361744949293
279 386212355724
280 411403718790
281 440031678239
282 472889930533
283 507547532347
284 541788185658
285 576984115580
286 616702150515
287 662153897837
288 710273796288
289 758050581884
290 807098858080
291 862089458738
292 924825049534
293 991462479774
294 1057936853004
295 1126117636406
296 1202098147458
297 1288506552762
298 1380555314249
299 1472789034414
300 1567331743827
301 1672101347869
302 1790869419585
303 1917709623183
304 2045341984552
305 2176121443135
306 2320298977515
307 2483215019913
308 2657583858435
309 2833741062163
310 3014216087345
311 3212230402888
312 3435262963846
313 3674419966633
314 3916937060020
315 4165409934041
316 4436830261136
317 4741570279614
318 5068857526724
319 5401913279631
320 5743220421111
321 6114536164244
322 6530125817886
323 6977049024929
324 7433353572706
325 7901126024107
326 8408128242366
327 8973831544032
328 9582836101292
329 10206547621503
330 10846233003968
331 11537189913056
332 12305818618654
333 13133980647480
334 13984592949629
335 14857481708821
336 15797371903747
337 16839837351745
338 17963769939653
339 19121278031480
340 20309865149014
341 21586003912154
342 22997362780332
343 24519719173564
344 26091479040306
345 27706583207851
346 29436096235906
347 31343559102265
348 33401647867974
349 35531461429233
350 37721670861165
351 40061395835883
352 42634929486112
353 45412099409464
354 48292237214291
355 51256410108021
356 54416004748221
357 57882335113892
358 61623009118839
359 65510082583496
360 69513875177162
361 73773129390914
362 78434221500733
363 83463705548307
364 88699602279291
365 94097271833557
366 99828951363002
367 106086345951311
368 112836906682376
369 119876344616975
370 127139481630572
371 134839406687485
372 143226240556423
373 152271367358661
374 161718123884858
375 171473436912296
376 181800046863449
377 193023101644803
378 205122478304796
379 217776932673632
380 230855883784639
381 244682178805186
382 259677044074500
383 275835470451780
384 292756925773993
385 310260809443220
386 328742466861791
387 348745779198415
388 370290290828967
389 392878524117949
390 416263697668882
391 440928240318041
392 467572184750990
393 496252821436220
394 526354676298149
395 557543985964345
396 590407377105899
397 625843107616735
398 663964442600301
399 704012923999848
400 745541208847852
401 789260056247067
402 836318709638929
403 886911260647545
404 940106838271643
405 995310623974808
406 1053380639838655
407 1115783068838034
408 1182826440578891
409 1253373003597065
410 1326637517431657
411 1403651888485558
412 1486281552636943
413 1574994495773241
414 1668406085659255
415 1765486421761664
416 1867471785034055
417 1976729300112658
418 2093946339451730
419 2217445311716171
420 2345883517839622
421 2480736210021062
422 2624999476786428
423 2779659264638591
424 2942692548738189
425 3112358501422595
426 3290410353600042
427 3480630878587766
428 3684408719669407
429 3899316284481750
430 4123108279888353
431 4357859403120606
432 4608334260432120
433 4876460285112532
434 5159339714658343
435 5454090695874343
436 5763157454870844
437 6092527302177893
438 6444843618642414
439 6816666867276888
440 7204315306250399
441 7610655043094959
442 8043192957909554
443 8505517856140491
444 8993572143429609
445 9502672895377313
446 10036164404622583
447 10603438179753011
448 11209324663724345
449 11849069264861054
450 12516740916031100
451 13216221415620894
452 13959235179848877
453 14752235054853858
454 15589691423229490
455 16464123108849070
456 17380010631806799
457 18351960656354884
458 19388536394745276
459 20483361115970698
460 21627035983040118
461 22824701321175735
462 24094518321349055
463 25447783661304391
464 26877215087785406
465 28371050319991674
466 29935148017840184
467 31592045080724576
468 33356565160844188
469 35220486275501393
470 37169144550436772
471 39209169196084856
472 41368474620461791
473 43666418811708080
474 46093845206417966
475 48632541207603396
476 51289948030912553
477 54100577644089728
478 57089598114793612
479 60246982975602075
480 63550196562832715
481 67007516428951283
482 70661536220316626
483 74544845246579318
484 78646699277611488
485 82939317043264521
486 87431812206579827
487 92176662641492834
488 97215909200421584
489 102538366143104043
490 108109913432440836
491 113940465983980456
492 120094572885984333
493 126626278707469420
494 133524406012252178
495 140747207164090006
496 148305317245342482
497 156278006319435226
498 164734524450711684
499 173664390042437102
500 183016717699941890
501 192802720288575228
502 203119596300136930
503 214055809144308888
504 225602583301597132
505 237698136806905719
506 250354039615236401
507 263689296500466675
508 277816591915695967
509 292730298660301504
510 308355704919576507
511 324704417429036864
512 341921931859940799
513 360151398222242473
514 379392354637460727
515 399554826782607487
516 420650014835350570
517 442855558807582269
518 466352848056066256
519 491149360084656695
520 517137207060450789
521 544326588018685496
522 572934105484536541
523 603189048305436041
524 635110599975881356
525 668569977259243163
526 703575602439082016
527 740391256593031128
528 779306113915174589
529 820356121927600347
530 863388291103331306
531 908408276167171651
532 955736932378784563
533 1005738166483211515
534 1058471422177835514
535 1113755882722206634
536 1171593195678266782
537 1232373201562224046
538 1296552905519203274
539 1364224136812603592
540 1435174369338373441
541 1509399719574360301
542 1587373345770658423
543 1669668036213910833
544 1756419666430385858
545 1847379942780408532
546 1942537612796053050
547 2042466391340903050
548 2147882833178563698
549 2258982063762163409
550 2375475929664562511
551 2497343632736019500
552 2625280176446118337
553 2760180355279860966
554 2902318265968464546
555 3051361981056543144
556 3207278633380292872
557 3370909442840563440
558 3543369862273180707
559 3725038418573929882
560 3915535988491976606
561 4114814777249742320
562 4323892196030983309
563 4544156487976396199
564 4776123339252330592
565 5019363943356727286
566 5273812434677834715
567 5540698459971098664
568 5821747054088571369
569 6117652972871527180
570 6427936793455628353
571 6752511249505567292
572 7092861577616169145
573 7451128091750403981
574 7828238099282244112
575 8223663024531519052
576 8637290862084908495
577 9070914597316313259
578 9527185982894255580
579 10007332901411847426
580 10510782628922865405
581 11037395352003196149
582 11589334585656751344
583 12169881216516585282
584 12780649967962687788
585 13421034034617259891
586 14090863426666777142
587 14792747788137200085
588 15530741069095895199
589 16306953925632325993
590 17120762622778795013
591 17971965950583682670
592 18863710776584328554
593 19800999971447693685
594 20786577732620265684
595 21819830280491598518
596 22900526369700458285
597 24032459926794922465
598 25221797444580218461
599 26472089818571154429
600 27782773309384896042
601 29153591307459779870
602 30589117339009370308
603 32096943441720806698
604 33681644613880707636
605 35342764927653651145
606 37080032319223538076
607 38898959982944208811
608 40808884812910719211
609 42815678286335744477
610 44919073549607836249
611 47118800612128632383
612 49421505835742897868
613 51838659980216381301
614 54377771580076526344
615 57038875054101950569
616 59821730859981162842
617 62734352660157735009
618 65790818716872350243
619 69000699673830285555
620 72364483898247142455
621 75882005827179250090
622 79562930025641853533
623 83424518591482201746
624 87478933827825927495
625 91727323350550485141
626 96169660008218389939
627 100817603148837235483
628 105692299639444571913
629 110809162066912960100
630 116170270672425655016
631 121775829610758334635
632 127639910455877021186
633 133788396882371683496
634 140240769635469521301
635 147000402581348065424
636 154067862483723969362
637 161460140438865567100
638 169208892189280852803
639 177338680727256165183
640 185854646876362779950
641 194757902672330258998
642 204068975935504028315
643 213826551817005485693
644 224061531152919984265
645 234781438480359227921
646 245988181982672447373
647 257706577949868124958
648 269983867436752409694
649 282858841613765167765
650 296342208003336514682
651 310437011782208915051
652 325173274364813581603
653 340608645311984469701
654 356791723253807985530
655 373737429446176744620
656 391450404934611457036
657 409966995189390853684
658 429357505968502586415
659 449682707824075428261
660 470963059243404975608
661 493205410009302011735
662 516453796951894263029
663 540793908266854234165
664 566301599207863785576
665 593004558172188708958
666 620912656579352999397
667 650079295084529807404
668 680608850188085445174
669 712595846044684452119
670 746077358082087067109
671 781067350924033469628
672 817630636771737641079
673 855894288226381021105
674 895975904040909906065
675 937924686634055208522
676 981760098659107926484
677 1027560873256597171347
678 1075481636964738120350
679 1125668473041853486155
680 1178186180732553365738
681 1233061553287309687798
682 1290390322544233642517
683 1350360556087674953953
684 1413153458235136329269
685 1478853806921089554814
686 1547498105834609398489
687 1619202863218621184323
688 1694196721139435036148
689 1772704138645614803957
690 1854835391735017859117
691 1940639772332865282956
692 2030259205196135748325
693 2123971549330063835276
694 2222054478159913915053
695 2324650701151780093013
696 2431826263928936656638
697 2543754210634101837698
698 2660772086823409726874
699 2783222965335359411324
700 2911290684305126427918
701 3045063134296601001285
702 3184751491764004746010
703 3330765670657221797725
704 3483529038722805551723
705 3643277441264462083458
706 3810127129310957531818
707 3984336039528601153992
708 4166401814691051623791
709 4356846311935996764963
710 4555970966859989834670
711 4763928703975892006363
712 4981034839184930791311
713 5207893347650359711917
714 5445146783337942731186
715 5693179100576683309402
716 5952190473931899951833
717 6222566672264682820164
718 6505040533556044725498
719 6800402394403293475061
720 7109139788404396124198
721 7431513560940696471021
722 7767996033719925344632
723 8119476192586803638214
724 8486925169763684610498
725 8870960235518314899694
726 9271919893563192957833
727 9690382848308440693288
728 10127427275625852897223
729 10584245313706186499001
730 11061616405890467881929
731 11559978165799843391074
732 12080040107204288698737
733 12623109609020244888044
734 13190648761044789696372
735 13783639341676019436431
736 14402645103141721689825
737 15048536458708964157146
738 15722898444133895960351
739 16427522642698048517477
740 17163642824320160013483
741 17931982863810503799102
742 18733611139990144504131
743 19570449019685992435898
744 20444689969157464204602
745 21357881061255260998129
746 22310948937149053500921
747 23305205596620299245327
748 24342979787385796590831
749 25426954817875553823410
750 26559066667118944254451
751 27740498150933468974056
752 28972861117786967025699
753 30258977730848376692573
754 31602127960189537947235
755 33004729800991408162522
756 34468289012637884732774
757 35994786527415278091580
758 37587642102561709255991
759 39250862025182573115075
760 40987460840288162053035
761 42799350577864996852998
762 44688966485834652629899
763 46660452062641075968043
764 48718697206111343258547
765 50867453736157097640778
766 53109143772711206463264
767 55446761774383759116172
768 57885327726606489209938
769 60430805868069099885180
770 63087858009493555531899
771 65859545506456077709721
772 68749551081966656347384
773 71763956156925337513199
774 74910030476462951306816
775 78193557596953950613700
776 81618398515664467121822
777 85189082939559735860305
778 88912977659327877485994
779 92798937972224948892092
780 96854128534371102662442
781 101083408926261314232391
782 105492350967711761433736
783 110089877947522145294827
784 114886769827696290142972
785 119891889705782723467274
786 125111342133715304312236
787 130551980833168305223682
788 136224613845853967971190
789 142142356261322600049472
790 148316157547093582575021
791 154753671963985574392844
792 161463329674416164371754
793 168458220870095361555387
794 175754292388996052839668
795 183365053852983164946848
796 191300085645649221854245
797 199569755987955777335201
798 208189918296262425578750
799 217179951780377732890631
800 226556504350576811939366
801 236331546877255018882958
802 246517829393704411466056
803 257134550871350086189441
804 268205249016786596276501
805 279750414896262266091237
806 291784982036013107279732
807 304324626546159047463194
808 317392597795339770936628
809 331017469505825916484174
810 345224434578080368575183
811 360032093368294815567151
812 375459715249285537847699
813 391535453036649131638979
814 408293976557809825116183
815 425766225769111754609317
816 443975333508318406300767
817 462944979830917345976831
818 482709253315517344284911
819 503310200080892448837694
820 524785778453189611014041
821 547164716741023928914605
822 570476106604326610195612
823 594761221496733833915680
824 620071029269743722892454
825 646452051779810336695344
826 673939916732036693842703
827 702570352305937420002222
828 732393328078796923763295
829 763470598656199542175627
830 795859126065179507919532
831 829603035230419424020860
832 864746189014445070544093
833 901349081263753941854885
834 939486503275910519149036
835 979228134883271757551770
836 1020628554237121570425779
837 1063741590167146100460798
838 1108640471954576609690085
839 1155415740998220936759099
840 1204152557369898623390999
841 1254918344608346914343330
842 1307779134650627451513655
843 1362823566215848465488633
844 1420161202109561270718608
845 1479896030853232611032484
846 1542111244186673580192008
847 1606887808451301727989273
848 1674333004970277477963511
849 1744579360622792811131482
850 1817753747976037024496483
851 1893958694880939589190643
852 1973293434670207429986294
853 2055887799808652963202699
854 2141902031589095658684863
855 2231490795988437231252561
856 2324780308479026018349832
857 2421892133156521295404559
858 2522983377694574381528725
859 2628247719520458120722929
860 2737873557273285553866798
861 2852016096657367207557499
862 2970824184886666153438883
863 3094487913425896474089925
864 3223241285499518483498664
865 3357313613344545615225619
866 3496895549042745291821278
867 3642169254467415444769599
868 3793364701654567359366032
869 3950764513166010818467182
870 4114647592038774688801743
871 4285247890898768525639460
872 4462788227678900258648183
873 4647546785382371981243594
874 4839864786451416817566838
875 5040081204061769484273255
876 5248482838659859125001168
877 5465342094489334636668712
878 5690995425144694792732711
879 5925854660146020911712810
880 6170331491616222317532630
881 6424777164137983897203988
882 6689524524602484701289818
883 6964980441991860743322019
884 7251641794113046448043973
885 7550008251259683656424678
886 7860509576562851483116595
887 8183552249367669527464534
888 8519628212461620411649807
889 8869336755571836275868313
890 9233283925892533424755525
891 9611995074496046720302658
892 10005966328301159532057556
893 10415792391471249918551577
894 10842195837153123012829359
895 11285911262256722705811090
896 11747580292498882173683162
897 12227808136260084339012922
898 12727313595905720572762883
899 13246967608904472669240035
900 13787660029576623681836684
901 14350173811134244637802560
902 14935246811731804967586942
903 15543747663621237364509218
904 16176725799324660382245736
905 16835258484874216608035212
906 17520300320534705674928959
907 18232750379483440019107668
908 18973658146589226932587670
909 19744287736500874107052772
910 20545942520049603642559273
911 21379785413218073306071077
912 22246911305322658672956040
913 23148587924395714392957846
914 24086337515716449982206746
915 25061736094599524024511164
916 26076199210779766976132954
917 27131059457413936663153136
918 28227847857335067035722445
919 29368396938796092282523814
920 30554611313298954849666551
921 31788212692847588924304388
922 33070822053588644410180482
923 34404287978589150829561785
924 35790815861241256658752099
925 37232706145993802405453177
926 38732051319444023667625255
927 40290822020968227539576431
928 41911249736588209670526778
929 43595987801505621846223882
930 45347813255197879764534127
931 47169267301775519688120090
932 49062744300169280370760634
933 51030937294969936233008762
934 53077037603509227042127103
935 55204395826163997023321079
936 57416095851430064215272438
937 59715045202894150965605068
938 62104493133243893815404045
939 64588276897857771493853994
940 67170437028889969666841396
941 69854713317087315502206190
942 72644634421414670261668875
943 75544119660007212585659261
944 78557781625933349609555708
945 81690490383572249020980023
946 84946777959384579092296977
947 88330924408217678129661071
948 91847656030079967126693786
949 95502515814593630554257913
950 99301370756039424735521812
951 103249709191511191836402738
952 107352719636667211615614099
953 111616099962048490804468604
954 116046509307213052829323753
955 120651012244395436138171987
956 125436250772169548131823888
957 130408511148322448173753889
958 135574660598496862561335910
959 140942696872774283599247774
960 146521122527790461512299996
961 152317970468793582557641810
962 158340852677829054492752128
963 164598043327404519774195957
964 171099145123584804955612705
965 177854386536429698580138192
966 184873476428467299082037278
967 192165626954452919717746403
968 199740804542705614348744598
969 207610535651328707642824134
970 215787119375023430912664111
971 224282282841463634167218137
972 233107168588075864982389292
973 242273777785179158438083819
974 251795942108709114087449239
975 261688443810651975364907725
976 271965439136689500989682026
977 282640398099146417538359296
978 293727767583280416078011186
979 305244140806331983098313518
980 317207276688060250527988683
981 329634253464258890519125295
982 342541345895205552000016008
983 355945939555965783299111920
984 369867934917873923572628892
985 384328657731070027815967534
986 399348699190202073002567093
987 414947712152670599832990683
988 431146612004916997704686556
989 447969258895097673573562013
990 465441250886235487889805398
991 483587400372431488127638889
992 502431426723758356502840633
993 521998483684686376391244538
994 542317170851437710226879471
995 563418201627789676141867875
996 585331457980141677154664152
997 608085551950505088898328643
998 631710724624441779980903853
999 656241246750425925784017530
1000 681713954098733208823277233