1 0
2 0
3 0
4 1
5 1
6 1
7 4
8 4
9 4
10 10
11 11
12 11
13 22
14 25
15 26
16 44
17 51
18 54
19 84
20 98
21 105
22 152
23 178
24 193
25 266
26 312
27 341
28 452
29 528
30 581
31 749
32 873
33 964
34 1214
35 1409
36 1561
37 1930
38 2234
39 2479
40 3018
41 3478
42 3866
43 4647
44 5339
45 5937
46 7061
47 8081
48 8991
49 10594
50 12089
51 13447
52 15721
53 17878
54 19884
55 23085
56 26181
57 29100
58 33583
59 37973
60 42185
61 48419
62 54613
63 60619
64 69250
65 77902
66 86406
67 98279
68 110309
69 122231
70 138497
71 155087
72 171698
73 193855
74 216633
75 239590
76 269654
77 300711
78 332263
79 372845
80 415017
81 458082
82 512662
83 569586
84 628077
85 701138
86 777676
87 856644
88 954107
89 1056482
90 1162620
91 1292082
92 1428519
93 1570431
94 1741833
95 1922829
96 2111801
97 2337847
98 2577136
99 2827610
100 3124796
101 3439851
102 3770609
103 4159926
104 4573409
105 5008375
106 5516885
107 6057532
108 6627577
109 7289583
110 7994375
111 8738662
112 9598093
113 10513759
114 11482461
115 12594789
116 13781057
117 15037561
118 16473399
119 18005474
120 19630485
121 21478659
122 23452072
123 25547137
124 27920101
125 30454715
126 33148379
127 36187076
128 39434304
129 42887698
130 46769646
131 50918803
132 55334824
133 60281729
134 65570741
135 71202773
136 77492568
137 84217907
138 91383485
139 99362076
140 107894599
141 116988849
142 127087977
143 137888257
144 149404136
145 162159350
146 175801022
147 190349851
148 206426857
149 223620024
150 241961315
151 262183225
152 283808757
153 306881279
154 332267347
155 359412252
156 388377858
157 420184413
158 454192035
159 490482230
160 530259401
161 572782427
162 618162471
163 667815214
164 720888877
165 777527123
166 839397911
167 905518772
168 976080018
169 1053039207
170 1135271507
171 1223019460
172 1318585372
173 1420677306
174 1529610038
175 1648081817
176 1774619457
177 1909619814
178 2056251141
179 2212828889
180 2379860226
181 2561053497
182 2754496023
183 2960821699
184 3184378272
185 3422988879
186 3677453944
187 3952856314
188 4246735744
189 4560085409
190 4898856362
191 5260262602
192 5645546136
193 6061656533
194 6505461064
195 6978491333
196 7488873627
197 8033079927
198 8613010273
199 9238144837
200 9904538926
201 10614523048
202 11379169600
203 12194063452
204 13062076233
205 13996112880
206 14991268656
207 16051049129
208 17190510402
209 18404201334
210 19696416462
211 21084688399
212 22563007164
213 24136593234
214 25825881335
215 27624247168
216 29538053857
217 31591077992
218 33776082413
219 36100772839
220 38592835809
221 41244374581
222 44064739721
223 47086121079
224 50299989070
225 53717628078
226 57376489159
227 61267383932
228 65403951260
229 69829702680
230 74534860342
231 79535831846
232 84883199646
233 90566610089
234 96605823506
235 103059568456
236 109917053145
237 117201980190
238 124982570495
239 133247676125
240 142025750812
241 151395951930
242 161347019373
243 171912991614
244 183185755195
245 195154130621
246 207858858639
247 221406491900
248 235786336956
249 251047008704
250 267312111523
251 284571803954
252 302884115278
253 322392296130
254 343088002808
255 365040317885
256 388415310811
257 413206764674
258 439496932925
259 467478174593
260 497147398033
261 528602308497
262 562065771039
263 597538839625
264 635137575656
265 675119987040
266 717492782815
267 762393541114
268 810121012551
269 860689154258
270 914261034661
271 971182334214
272 1031476499864
273 1095336451928
274 1163162232404
275 1234989198103
276 1311045544562
277 1391793920638
278 1477284874673
279 1567787873503
280 1663838028514
281 1765504680208
282 1873105951082
283 1987260389731
284 2108060875607
285 2235882400426
286 2371440009836
287 2514855392758
288 2666570440741
289 2827411286357
290 2997535223722
291 3177462257731
292 3368146899452
293 3569789661053
294 3783002254074
295 4008886940447
296 4247697093776
297 4500151392451
298 4767522724543
299 5050128199706
300 5348811842301
301 5665042857759
302 5999215669792
303 6352320353412
304 6726052666633
305 7120899735036
306 7538022477549
307 7979377235146
308 8445562820956
309 8937939008498
310 9458762648161
311 10008765837465
312 10589540575846
313 11203689244562
314 11852103607782
315 12536645681227
316 13260316051552
317 14024196243277
318 14830463107042
319 15682574925107
320 16581839436613
321 17530799176949
322 18533439548770
323 19591336172753
324 20707457331704
325 21886394062127
326 23130039978176
327 24441857359180
328 25827134285111
329 27288139724552
330 28828910274161
331 30455534550643
332 32170725438194
333 33979185228405
334 35887923307362
335 37900175031716
336 40021415576224
337 42259711349620
338 44618913573528
339 47105392361575
340 49728429122133
341 52492598017840
342 55405306851106
343 58477231193346
344 61713794848072
345 65123605967927
346 68718941633673
347 72506220603994
348 76495441110119
349 80700717038345
350 85129633336103
351 89793794610470
352 94709423398946
353 99885467251474
354 105335388821283
355 111077827930620
356 117123325329062
357 123487488718603
358 130191731216574
359 137248451261776
360 144675734794109
361 152498172553012
362 160730330166434
363 169393151841369
364 178514871643797
365 188112577305824
366 198210511577046
367 208841080882388
368 220024309145325
369 231788239848333
370 244170060274160
371 257193205230942
372 270890099630181
373 285303402950640
374 300460513241960
375 316398899159084
376 333167486531427
377 350798269583665
378 369334525216043
379 388832347922899
380 409329062803152
381 430874626821498
382 453533338378697
383 477348694907647
384 502378338119552
385 528695946526938
386 556352164483989
387 585413463897360
388 615964251318144
389 648063433610317
390 681787630870487
391 717233509012036
392 754469526866398
393 793583954933810
394 834687471464142
395 877859562385405
396 923201874628430
397 970841089956967
398 1020869423229072
399 1073403864393277
400 1128589375749317
401 1186532846734308
402 1247368866861684
403 1311263264873147
404 1378339845547693
405 1448753367989397
406 1522693481582401
407 1600303466541154
408 1681761196780853
409 1767283496431713
410 1857036064782097
411 1951223243466037
412 2050092859542016
413 2153836392215480
414 2262688488625282
415 2376932323889960
416 2496789015650662
417 2622527883533763
418 2754472405502237
419 2892877739957832
420 3038052871838557
421 3190367203989892
422 3350114982643826
423 3517650536533921
424 3693395598648185
425 3877689257370739
426 4070937670482798
427 4273622166376011
428 4486133263880389
429 4708936321886870
430 4942580534640664
431 5187515357591962
432 5444273761492450
433 5713482183739325
434 5995657599647637
435 6291410147591793
436 6601454174157749
437 6926383946602710
438 7266897662279063
439 7623809665561255
440 7997802676646186
441 8389675319161098
442 8800355674428401
443 9230627613370023
444 9681404268394845
445 10153743022766893
446 10648543384302364
447 11166848976164470
448 11709864160304696
449 12278620550498155
450 12874310442600130
451 13498305194289470
452 14151787293711822
453 14836118332067761
454 15552859378761864
455 16303365118652852
456 17089189879149019
457 17912110153155339
458 18773677096604025
459 19675664345417962
460 20620092973574971
461 21608738166184760
462 22643623045719143
463 23727046254711836
464 24861038350111414
465 26047906130702996
466 27290263189683532
467 28590431013584513
468 29951038874912306
469 31375057589742966
470 32865139977032045
471 34424281712509725
472 36055858706105243
473 37762900913900472
474 39548820225137844
475 41417451750603342
476 43372254582504104
477 45417113190029017
478 47556383117070371
479 49794011502943255
480 52134419259871800
481 54582551539773742
482 57142910348547035
483 59820525268422533
484 62621009292566206
485 65549494943822194
486 68611702246489210
487 71814000372413662
488 75162238095394488
489 78662918309662068
490 82323266206774735
491 86149943811432892
492 90150341454536511
493 94332653027166088
494 98704463645120623
495 103274169200716567
496 108051059557967005
497 113043767115851585
498 118261826872272485
499 123715768231990023
500 129415411398689744
501 135371581248597076
502 141596208789202219
503 148100460808105260
504 154896622396462598
505 161998208882863790
506 169417913158592156
507 177169672731742572
508 185268793383169432
509 193729696822531024
510 202568189970724312
511 211801601348470389
512 221446310509066582
513 231520238498126374
514 242042998472627077
515 253033186283062569
516 264511113198109932
517 276498971991404837
518 289017866599918013
519 302090809703568460
520 315742906078926083
521 329998096827291294
522 344882446915541992
523 360424347309826716
524 376650947539604180
525 393591760107249748
526 411278883562954902
527 429743094316845547
528 449017797784059199
529 469139274249185645
530 490142398778411640
531 512064971123336845
532 534947986971061240
533 558830951462760821
534 583756623357985057
535 609771313926024449
536 636919757123662634
537 665250306100256709
538 694815262848958249
539 725665264177393929
540 757854972720858033
541 791443440103520954
542 826487964917659219
543 863050323491573372
544 901197170307077736
545 940993319615167187
546 982508566005161991
547 1025818125428642745
548 1070995288613743236
549 1118118885154823657
550 1167273769643409668
551 1218542789676219822
552 1272014952819291702
553 1327785961923780657
554 1385949436412401354
555 1446605845847575394
556 1509863099839038655
557 1575826955018677322
558 1644610785553924284
559 1716336232607149155
560 1791122724540175010
561 1869098159921365067
562 1950399623033058575
563 2035161937516113548
564 2123529345173926882
565 2215656293556724872
566 2311694937497057501
567 2411807903204213690
568 2516169155730935977
569 2624950354291459358
570 2738334800231599802
571 2856518391701265263
572 2979694731842104255
573 3108070366569779201
574 3241865835831750558
575 3381299423764713342
576 3526603802880543911
577 3678027190800133754
578 3835815623451376828
579 4000231130971718057
580 4171553011189704661
581 4350058495289569941
582 4536042593225176261
583 4729819494737177574
584 4931701487446870903
585 5142020619913552794
586 5361130243734107851
587 5589382030460193428
588 5827149615047286626
589 6074830292120067637
590 6332819966966795280
591 6601538954369518579
592 6881433845317987234
593 7172950211535453456
594 7476560751788554849
595 7792767344909859452
596 8122071314210390895
597 8465004127850849924
598 8822129657745941210
599 9194011791834061407
600 9581247915110909531
601 9984471393633720547
602 10404316307234128315
603 10841453954936502729
604 11296595587593017835
605 11770454012247314562
606 12263783389076107392
607 12777382235933239119
608 13312051637523492682
609 13868638621229502132
610 14448039461856783822
611 15051154203935020689
612 15678933931171848490
613 16332384399584747313
614 17012516560097311758
615 17720398060230648463
616 18457157239642127719
617 19223929311337614403
618 20021912466213660019
619 20852372265120215148
620 21716583112252771814
621 22615889361309372519
622 23551710144989411675
623 24525475740656827452
624 25538694114269130691
625 26592956228596147078
626 27689866872297570231
627 28831117110957758750
628 30018490123230189402
629 31253786025659528503
630 32538900743833400598
631 33875832426394539077
632 35266599764126085831
633 36713327833303833248
634 38218255146762945500
635 39783644920792424485
636 41411878493772714664
637 43105463074697010357
638 44866935371971055903
639 46698963236406004769
640 48604354178394121963
641 50585950720638467514
642 52646740974105725905
643 54789867996886322470
644 57018516186899451631
645 59336031553496464583
646 61745932003664683319
647 64251784030507237147
648 66857333512662593642
649 69566517016132704940
650 72383327980805103184
651 75311958943428750170
652 78356813958131167402
653 81522363413599411044
654 84813298656403472268
655 88234545636895085818
656 91791107427404833910
657 95488232297387981860
658 99331428708722228876
659 103326294524816279777
660 107478699683582268637
661 111794802671050502019
662 116280865338952287427
663 120943451409207104634
664 125789444575095379541
665 130825847751999979279
666 136059998757315089785
667 141499590194919341819
668 147152451879814288186
669 153026785140253196004
670 159131184665122035549
671 165474402736087786737
672 172065603727224125202
673 178914388103412242634
674 186030536996291593959
675 193424288597332326900
676 201106364523421668675
677 209087693149451941004
678 217379709740515961748
679 225994385411846146552
680 234943927518170613702
681 244241105512164505849
682 253899282758920046005
683 263932092140039297814
684 274353789799920384710
685 285179290089039493448
686 296423814410370287142
687 308103275180825105373
688 320234314216513113824
689 332833922685514353623
690 345919857814996360890
691 359510685049555267817
692 373625366823711952085
693 388283714739330402178
694 403506435873993201430
695 419314687898567044851
696 435730569686192088053
697 452777172170326541005
698 470478097158823063306
699 488857989562984497874
700 507942593259015997255
701 527758230734109776156
702 548332380399595243414
703 569693737938058573978
704 591871653716419686586
705 614896758913092493965
706 638801032896941092757
707 663617195094543645590
708 689379383982029425054
709 716123231077735556952
710 743885203719921699425
711 772703341284955552413
712 802617336451092829088
713 833667825058841911884
714 865897184290491441408
715 899349621906926362329
716 934070409097185823811
717 970106745717968700473
718 1007507858294805978216
719 1046324171442017825705
720 1086608245695267758802
721 1128414885123665839344
722 1171800242596086684840
723 1216822836164881177375
724 1263543667241364705716
725 1312025254612221097033
726 1362332735837952074385
727 1414533997012609551992
728 1468698630083698987210
729 1524899126225580938469
730 1583211018329789533369
731 1643711755756388187278
732 1706481997230574092598
733 1771605767294370299222
734 1839169242215847509835
735 1909262150537289970213
736 1981977944867872184115
737 2057412492191381814593
738 2135665590878300637325
739 2216841159303059314078
740 2301045823331217907304
741 2388390559285226500938
742 2478990901046476773411
743 2572965416948858469505
744 2670437488983478619478
745 2771535540173474344474
746 2876391392575310013639
747 2985142193798550077185
748 3097930666651151175906
749 3214903339318697323466
750 3336212631200433512923
751 3462017126979367978909
752 3592479669449577494304
753 3727769617592676198977
754 3868063147476301014318
755 4013541197481440472240
756 4164391912619228390620
757 4320810974853023788733
758 4482999389793523860686
759 4651166132332714679193
760 4825528509281082325207
761 5006309775782099812964
762 5193741998590892173296
763 5388066454152204675743
764 5589531062206858980674
765 5798393484299014178369
766 6014921560772995817865
767 6239390548117987249621
768 6472086471741865069292
769 6713306605650478090109
770 6963356499191233466075
771 7222553604596767644259
772 7491227803529724521177
773 7769718207835971412616
774 8058377084051794703580
775 8357570431344877542970
776 8667674539882642547168
777 8989080236205334170668
778 9322193517593270176311
779 9667431850467501263395
780 10025228762496207552511
781 10396034538841070623897
782 10780312241868274515425
783 11178542677847790912181
784 11591225161126446480554
785 12018873235084391726973
786 12462020043571076527530
787 12921219169566056937455
788 13397040036027339231944
789 13890073714530134597045
790 14400933845684965379847
791 14930251697009113839884
792 15478682443889390690122
793 16046906179649979638673
794 16635622606122954992848
795 17245557824763056079409
796 17877465445102017526617
797 18532120881987456052618
798 19210328697763879116770
799 19912923818605003851713
800 20640765410750130612257
801 21394744817820097613549
802 22175786895525457345725
803 22984843437310570969129
804 23822901754460510085670
805 24690986140596549472317
806 25590150815293389120331
807 26521489198308866337867
808 27486135516477990079075
809 28485257231715361446044
810 29520065064869258300089
811 30591814758730188520687
812 31701798954760092324012
813 32851358026355365856300
814 34041882013116474627900
815 35274801908234079829908
816 36551601365792294428477
817 37873818822780555294426
818 39243038156748491783196
819 40660901336770727649958
820 42129110751388183014032
821 43649419193449029407029
822 45223643529990163428115
823 46853667255906077778620
824 48541429760303954432696
825 50288941096370284627293
826 52098284782600034830524
827 53971606301990451969070
828 55911129059510235723854
829 57919157454664556453156
830 59998064561968100553384
831 62150309370406350647030
832 64378440153538653014805
833 66685081276351876617921
834 69072951818716373493976
835 71544869271570452661560
836 74103735412053219625214
837 76752556420846540128775
838 79494446935878596665840
839 82332614933932748297746
840 85270383460617271390477
841 88311195075844641060440
842 91458595676568040548728
843 94716257967309831657934
844 98087986335125327120294
845 101577699544027816131699
846 105189456084296352072046
847 108927459518024545049897
848 112796039971884862090156
849 116799681514140095326361
850 120943028015995010036722
851 125230863364845722399617
852 129668141029882872904512
853 134259990488541995173703
854 139011696078088456200165
855 143928728923168275401573
856 149016753981563464154881
857 154281607447021157474186
858 159729331226019111378573
859 165366180661932034701271
860 171198600397316218416391
861 177233261601679592923639
862 183477070439020826527522
863 189937142292383226002166
864 196620841960596104326268
865 203535792940031599811688
866 210689849909130728406456
867 218091142128999494184086
868 225748083617210784126581
869 233669343784139291884261
870 241863894291109181666973
871 250341020201127826835195
872 259110288653337699317497
873 268181599452117919485995
874 277565197287961377662031
875 287271638330012169317244
876 297311844841405057913464
877 307697118571963042490460
878 318439105142848541062430
879 329549853006379612131054
880 341041828122148796452586
881 352927876001009907308458
882 365221285353062884258089
883 377935804168940289559521
884 391085599284018984490283
885 404685325085006414983021
886 418750141129969083265164
887 433295669086406767960999
888 448338066896483462299893
889 463894048081523960331396
890 479980835900900885793967
891 496616243407106432469345
892 513818694594538124530010
893 531607175618493298699543
894 550001321205728522875300
895 569021437821902045345360
896 588688451782988681145211
897 609024002523268561252092
898 630050467972586847466046
899 651790909384509176499719
900 674269172003768308761042
901 697509912861904896833153
902 721538542139297800961067
903 746381331816384980899781
904 772065446116252530268788
905 798618879209443734039771
906 826070572479921329949803
907 854450447863981608971253
908 883789341699483905732064
909 914119131286794852335449
910 945472771397226437582894
911 977884224060000570108686
912 1011388595152712035596659
913 1046022174377358763852078
914 1081822360771192849038294
915 1118827810118656103974940
916 1157078478721433703635464
917 1196615544411112694654097
918 1237481565637746286204881
919 1279720529390067569428557
920 1323377767481046906987594
921 1368500128235152813450782
922 1415136028948623211595532
923 1463335367211138144088007
924 1513149706187423717092137
925 1564632332042942226759938
926 1617838160058709291341065
927 1672823934580869578183337
928 1729648291877342424805076
929 1788371660795633012854730
930 1849056478539678148940138
931 1911767259465301027461319
932 1976570490025721384354476
933 2043534861625861237904545
934 2112731345912257932249966
935 2184233083744935009675806
936 2258115636479118023773852
937 2334457068355724377876478
938 2413337829234668092485871
939 2494841025759882564530554
940 2579052511513350667561702
941 2666060763240574661363889
942 2755957173470986215222718
943 2848836149158643049226955
944 2944794981129215239587795
945 3043934159851368741661186
946 3146357483354842957286616
947 3252171919626381530625208
948 3361487947363003406881166
949 3474419674029859172065216
950 3591084690934185666625914
951 3711604440935366063286659
952 3836104347585300390911340
953 3964713662610863058842582
954 4097565862713300264046425
955 4234798790819219760883494
956 4376554495707743304430983
957 4522979660199669515840114
958 4674225755642650727495069
959 4830448873425086933247356
960 4991810187039152237196878
961 5158476121025347866469662
962 5330618174126242249274674
963 5508413417903212567071931
964 5692044681478963160123728
965 5881700366095934721676341
966 6077574983180627903913649
967 6279869356343587090634934
968 6488790427125295466627599
969 6704551835630221801559745
970 6927374141378434577032175
971 7157484620041127089968633
972 7395117890015933296648391
973 7640516153868133347587141
974 7893928985884845142144297
975 8155614008229374947470929
976 8425837154869841130875484
977 8704872449810157403992095
978 8993002736751864394002657
979 9290519967578934251428603
980 9597724971161874147237803
981 9914928240765983422185703
982 10242450249350821859895848
983 10580621208885256529921169
984 10929781920079915269635604
985 11290284116962908888448173
986 11662490216696114081829743
987 12046774236571764358971242
988 12443522170551091254760123
989 12853131729629273679763523
990 13276013331431097475072605
991 13712590511640408374420882
992 14163299655031502767467465
993 14628591063421260730039200
994 15108929405184231601716106
995 15604793437144973133777258
996 16116677157104575738330867
997 16645090294922579050137634
998 17190558025557380153606517
999 17753622212877920801208607
1000 18334841946110089997324745