1 0
2 0
3 0
4 1
5 0
6 1
7 1
8 3
9 2
10 5
11 5
12 10
13 10
14 17
15 19
16 31
17 34
18 51
19 60
20 86
21 100
22 139
23 165
24 223
25 265
26 349
27 418
28 543
29 648
30 827
31 992
32 1251
33 1495
34 1866
35 2230
36 2758
37 3289
38 4033
39 4803
40 5852
41 6949
42 8411
43 9973
44 12005
45 14194
46 17002
47 20060
48 23919
49 28153
50 33426
51 39256
52 46438
53 54405
54 64127
55 74973
56 88084
57 102747
58 120351
59 140094
60 163631
61 190078
62 221417
63 256694
64 298278
65 345116
66 400068
67 462037
68 534409
69 616044
70 711030
71 818206
72 942455
73 1082654
74 1244653
75 1427443
76 1638033
77 1875560
78 2148464
79 2456207
80 2808860
81 3206332
82 3660765
83 4172693
84 4756686
85 5414183
86 6162693
87 7004907
88 7961877
89 9037880
90 10258298
91 11629618
92 13182313
93 14925696
94 16896546
95 19107804
96 21603761
97 24402066
98 27556089
99 31089503
100 35066646
101 39518692
102 44523295
103 50121242
104 56406063
105 63430526
106 71307548
107 80104813
108 89958478
109 100954870
110 113258175
111 126977866
112 142311933
113 159398266
114 178475681
115 199717323
116 223410886
117 249772738
118 279149718
119 311811109
120 348174683
121 388574566
122 433513785
123 483405631
124 538855578
125 600373057
126 668686646
127 744422960
128 828457837
129 921559909
130 1024781986
131 1139064563
132 1265672142
133 1405753179
134 1560825516
135 1732288667
136 1921963527
137 2131551802
138 2363236699
139 2619084048
140 2901709131
141 3213615138
142 3557933514
143 3937692112
144 4356637371
145 4818426211
146 5327537626
147 5888381549
148 6506309059
149 7186629775
150 7935732216
151 8760000928
152 9667056578
153 10664565478
154 11761612329
155 12967390197
156 14292720417
157 15748613381
158 17347949285
159 19103899014
160 21031782079
161 23147334391
162 25468763318
163 28014848767
164 30807212990
165 33868243352
166 37223599528
167 40899940060
168 44927692355
169 49338568312
170 54168621852
171 59455537583
172 65242005004
173 71572760676
174 78498313867
175 86071722501
176 94352702569
177 103404120958
178 113296528722
179 124104345581
180 135910862029
181 148804094863
182 162882303182
183 178249493046
184 195021499845
185 213321115708
186 233284799724
187 255057402250
188 278799562748
189 304682009615
190 332893717760
191 363635752145
192 397130266051
193 433613863669
194 473347522228
195 516609448704
196 563706021762
197 614964112775
198 670743158604
199 731426919832
200 797436796380
201 869223003714
202 947279263772
203 1032133368259
204 1124363393643
205 1224587632973
206 1333482491208
207 1451771770149
208 1580246423165
209 1719753174738
210 1871216339988
211 2035625768599
212 2214060942812
213 2407678250976
214 2617737612968
215 2845589079011
216 3092702262304
217 3360652281995
218 3651152302585
219 3966038852403
220 4307307811498
221 4677099141428
222 5077736711342
223 5511712496877
224 5981730659720
225 6490691305910
226 7041739297604
227 7638247662381
228 8283871675855
229 8982532060317
230 9738474923966
231 10556254922432
232 11440801720647
233 12397403317210
234 13431779785631
235 14550067015224
236 15758898552882
237 17065390084592
238 18477230317577
239 20002666559868
240 21650605701475
241 23430601346951
242 25352966060523
243 27428760594636
244 29669918720623
245 32089239177256
246 34700524584744
247 37518576862265
248 40559351872180
249 43839959208757
250 47378834448352
251 51195744324737
252 55311978699826
253 59750362347710
254 64535468992408
255 69693641128615
256 75253228783846
257 81244619011243
258 87700502382961
259 94655914070630
260 102148531405948
261 110218728795818
262 118909910136960
263 128268580109949
264 138344715718119
265 149191856943581
266 160867522175519
267 173433321672396
268 186955422268674
269 201504687573783
270 217157198047314
271 233994422477043
272 252103800218220
273 271578949202048
274 292520318033806
275 315035436484532
276 339239646123947
277 365256400173930
278 393218082391041
279 423266364162257
280 455553122609943
281 490240863894028
282 527503752925356
283 567528113145748
284 610513581717384
285 656673697549223
286 706237197633343
287 759448706647585
288 816570192099404
289 877881770768665
290 943683342471119
291 1014295530731865
292 1090061517517773
293 1171348137866338
294 1258547940784910
295 1352080460303063
296 1452394530799361
297 1559969760063271
298 1675319130929820
299 1798990705286636
300 1931570547916104
301 2073684694378024
302 2226002437362276
303 2389238595808621
304 2564157209174681
305 2751574150057923
306 2952361277507614
307 3167449441081886
308 3397833150582042
309 3644574025886162
310 3908806047729915
311 4191739514659075
312 4494666947554511
313 4818967623203794
314 5166114214182984
315 5537677977635656
316 5935336222330457
317 6360878241338240
318 6816213709526137
319 7303379460371492
320 7824548929760134
321 8382039890185201
322 8978325071149827
323 9616040978345668
324 10297999837067381
325 11027199640437115
326 11806837580104532
327 12640321485969000
328 13531284928727228
329 14483600234027881
330 15501395464150180
331 16589069212761255
332 17751309698175234
333 18993111570987181
334 20319797379926669
335 21737036653577531
336 23250870031733738
337 24867730915311685
338 26594472591579806
339 28438392783110096
340 30407264135291185
341 32509362036132885
342 34753498879262189
343 37149055572615261
344 39706020039863497
345 42435022887835083
346 45347380665447203
347 48455136217276970
348 51771107281733724
349 55308932123225262
350 59083124121050343
351 63109123345207821
352 67403357865898980
353 71983302018986981
354 76867545253608370
355 82075857924263745
356 87629268591469988
357 93550138279235325
358 99862247253140947
359 106590878795182963
360 113762916605783127
361 121406939275251400
362 129553329592181290
363 138234381032784203
364 147484420410474228
365 157339927862597838
366 167839674446027832
367 179024857278107061
368 190939253872213309
369 203629374287733482
370 217144634211357467
371 231537526191224169
372 246863813705773231
373 263182723803983178
374 280557164666364784
375 299053942248278589
376 318744004131336299
377 339702683073145413
378 362009970274713199
379 385750789082289143
380 411015301160433326
381 437899213973321123
382 466504123759769933
383 496937860845948568
384 529314873771426188
385 563756616959489116
386 600391980846901259
387 639357726966075773
388 680798969492952032
389 724869663382834637
390 771733143376080350
391 821562671484585175
392 874542040190032664
393 930866186307462086
394 990741865885524498
395 1054388342284409938
396 1122038141149198269
397 1193937821443151409
398 1270348819822863899
399 1351548314372978078
400 1437830168777981777
401 1529505899621580734
402 1626905731935334008
403 1730379682169397806
404 1840298738014729378
405 1957056070534481129
406 2081068352621270956
407 2212777115313984118
408 2352650220878918857
409 2501183380044943671
410 2658901797504175083
411 2826361868695909630
412 3004153017530898610
413 3192899593461334457
414 3393262923463047685
415 3605943432470154950
416 3831682934124310252
417 4071267000252436081
418 4325527517641286487
419 4595345335121202724
420 4881653116674950712
421 5185438297894224634
422 5507746269115555589
423 5849683676570905385
424 6212421972999339651
425 6597201102755563336
426 7005333461511906474
427 7438208008963612278
428 7897294683853716062
429 8384148992765816285
430 8900416931827087564
431 9447840105456956023
432 10028261211781667437
433 10643629751171548641
434 11296008138692186277
435 11987578068872714179
436 12720647325492818894
437 13497656876347431365
438 14321188458395276167
439 15193972484400760230
440 16118896490026150883
441 17099013943220891935
442 18137553649318494319
443 19237929563996598373
444 20403751262934901606
445 21638834870193407942
446 22947214710604591860
447 24333155477620744259
448 25801165199474727759
449 27356008784052783726
450 29002722444090862837
451 30746628771577729032
452 32593352782998830359
453 34548838692313995772
454 36619367754682368677
455 38811576925352209421
456 41132478699568739808
457 43589481864950397679
458 46190413556586694057
459 48943542332852436054
460 51857602688262403244
461 54941820707413155274
462 58205941304205074560
463 61660256735950712487
464 65315636866356249760
465 69183560852062163168
466 73276150758585869056
467 77606206764957704303
468 82187244496970900078
469 87033534132478817107
470 92160141855118011061
471 97582973283595148367
472 103318819491928621942
473 109385405231069693790
474 115801440009058949318
475 122586671623038834814
476 129761942844996637671
477 137349250837110207755
478 145371810046461581885
479 153854118137237172364
480 162822025761492890922
481 172302809708595383412
482 182325250289406360534
483 192919712477133603137
484 204118231719857778508
485 215954603928360490001
486 228464480617471777809
487 241685468686238041976
488 255657235882927388269
489 270421621421936202958
490 286022752871353713310
491 302507168760209179711
492 319923948102236706667
493 338324846267473319977
494 357764438482351026868
495 378300270372386763427
496 399993016918152842860
497 422906649222087173018
498 447108610553545659455
499 472670001053975305854
500 499665772673551753139
501 528174933706585345559
502 558280764608772497011
503 590071044450377865916
504 623638289808588286541
505 659080005441548678408
506 696498948676583458416
507 736003406845524889855
508 777707489838743635366
509 821731437103561149105
510 868201941308372395686
511 917252487993672664184
512 969023713592548444696
513 1023663781140578032544
514 1081328776231364976876
515 1142183122540148644366
516 1206400019658849293592
517 1274161902571812927228
518 1345660925717315454589
519 1421099470975901118567
520 1500690682748084435749
521 1584659029480000652135
522 1673240895034098601549
523 1766685199287469098682
524 1865254051607974033282
525 1969223436622191643833
526 2078883936198459556756
527 2194541487098848890275
528 2316518178518216645286
529 2445153089013480822884
530 2580803167359693663093
531 2723844156896108975323
532 2874671568242791559431
533 3033701700023100913733
534 3201372712844298967923
535 3378145756257330362565
536 3564506154349794368087
537 3760964649794143636437
538 3968058712439514865386
539 4186353912387308199049
540 4416445364108734792931
541 4658959241681652863233
542 4914554372213165579821
543 5183923907683901248125
544 5467797082830431575042
545 5766941059484210167610
546 6082162865578813174716
547 6414311429452915220987
548 6764279718305340583107
549 7133006981668313989344
550 7521481109453279592249
551 7930741105707052210141
552 8361879688388829310142
553 8816046016614072948368
554 9294448556495096474509
555 9798358087373286395733
556 10329110860460721418944
557 10888111912080140297936
558 11476838544483572759987
559 12096843976882583532264
560 12749761180714101450151
561 13437306902274175014974
562 14161285887875453630018
563 14923595315221407620812
564 15726229447380831784203
565 16571284513684082283463
566 17460963835256621691976
567 18397583200214700412532
568 19383576507684191815599
569 20421501686453541523530
570 21514046908990696769938
571 22664037107512449893254
572 23874440814539129794531
573 25148377335601377729857
574 26489124278381013894746
575 27900125447042189573312
576 29384999128042811758122
577 30947546777394393432311
578 32591762137841169473380
579 34321840797273591898488
580 36142190219215998793294
581 38057440258199152581396
582 40072454193431146924437
583 42192340295236519148933
584 44422463960473568929474
585 46768460433238861092404
586 49236248150107874749076
587 51832042728257824755323
588 54562371639024534983372
589 57434089587493972672358
590 60454394644270498623578
591 63630845152516124666613
592 66971377460305665451309
593 70484324504148353524210
594 74178435297964029564510
595 78062895356409074434943
596 82147348111453908508120
597 86441917354468374103234
598 90957230767733812514638
599 95704444581346607432195
600 100695269424888058659363
601 105941997413914772550848
602 111457530546578394335621
603 117255410454936122724168
604 123349849592715018942985
605 129755763909056826920965
606 136488807097026892893754
607 143565406471881127521283
608 151002800575511691013418
609 158819078568082621035409
610 167033221511584274737242
611 175665145612937525271095
612 184735747540415405836731
613 194266951888292551534412
614 204281760913324226463483
615 214804306625967002172141
616 225859905370642630890759
617 237475114986749405027792
618 249677794696364683759103
619 262497167820000077247850
620 275963887479020824418549
621 290110105396694419049287
622 304969543970264298190976
623 320577571737652205251333
624 336971282426184583949313
625 354189577719716882528939
626 372273253947873286829294
627 391265092847783361834130
628 411209956619794743871012
629 432154887442903296593935
630 454149211690708207217652
631 477244649030471118975390
632 501495426667120059989559
633 526958398933229578486894
634 553693172509706471077636
635 581762237498428446808335
636 611231104656472833708271
637 642168449035324631141740
638 674646260361805696424189
639 708740000428359489944875
640 744528767858928292884317
641 782095470544598364049633
642 821527006147346084983649
643 862914450995107535331141
644 906353257801430425320596
645 951943462564712663072488
646 999789901118290827784172
647 1050002435721148570491678
648 1102696192201861639108772
649 1157991808083570424692326
650 1216015692247593146751522
651 1276900296605042057274325
652 1340784400383014743672371
653 1407813407540166371985482
654 1478139657971503978374917
655 1551922753066873909690810
656 1629329896340940046292332
657 1710536249753391882784870
658 1795725306500234333785638
659 1885089280954183202091037
660 1978829516603616129000594
661 2077156912732855370255015
662 2180292370767858187160411
663 2288467261100801615978930
664 2401923911398817644279341
665 2520916117287567140222835
666 2645709676503215032778486
667 2776582947487767702776014
668 2913827433617388780805960
669 3057748394130628778092479
670 3208665483050660255955032
671 3366913417268815780648584
672 3532842675197150668284288
673 3706820227266822238318256
674 3889230299803588318128290
675 4080475173676654258511154
676 4280976019386566489273073
677 4491173770118642915034654
678 4711530034573786600802619
679 4942528051245214436884790
680 5184673686111867470477273
681 5438496475571896377736102
682 5704550716759786821779860
683 5983416607239329896302545
684 6275701436403879279135795
685 6582040830760089127028301
686 6903100055630833230796751
687 7239575375653998716593018
688 7592195476834910289207350
689 7961722952747535635008202
690 8348955857883615606211825
691 8754729330982857402977281
692 9179917291605720075576112
693 9625434213041155990959477
694 10092236975096029131252313
695 10581326800140890558835429
696 11093751276268791179846197
697 11630606471249232302658856
698 12193039141470789022308968
699 12782249039889215211325248
700 13399491327540624209769091
701 14046079093000921016255223
702 14723385984748847844369510
703 15432848961210417420825176
704 16175971163874288329578750
705 16954324918687479246212074
706 17769554871590539123364694
707 18623381263871245671996802
708 19517603353706077178396255
709 20454102990079544999774603
710 21434848346004788723955914
711 22461897817791441472695826
712 23537404097886108978703840
713 24663618428636162130597265
714 25842895045155985295053003
715 27077695815304038483225562
716 28370595085659945414563367
717 29724284742225138954008358
718 31141579495507401588386518
719 32625422399490452698001899
720 34178890614986288542343746
721 35805201427716841301349122
722 37507718532531894565065485
723 39289958595028828410815152
724 41155598102968317317176834
725 43108480519750437342477291
726 45152623753417047051969840
727 47292227954530470148257602
728 49531683657557792337921142
729 51875580280290443446040797
730 54328714997191280265431774
731 56896102002480556137196779
732 59582982180223745002908051
733 62394833198625062195338541
734 65337380047277343374482146
735 68416606036084715292272787
736 71638764276223203058282403
737 75010389663498610389236548
738 78538311386218757103770932
739 82229665979723648402726544
740 86091910951591606686859549
741 90132839001602455378782070
742 94360592862538246664847489
743 98783680788006347026968967
744 103410992715602892150052849
745 108251817133885364809864754
746 113315858683899547932041911
747 118613256526208928857055348
748 124154603506804642035176267
749 129950966155535152960052770
750 136013905553289383761318370
751 142355499104493193768160224
752 148988363254249905315863274
753 155925677189854330690898007
754 163181207569369486416850304
755 170769334320434659936945791
756 178705077555635802266699798
757 187004125651338338273826894
758 195682864540262020096932747
759 204758408268745966545997934
760 214248630873264537651993376
761 224172199631533274414375316
762 234548609747406546546876032
763 245398220529668840874890211
764 256742293128952152647731521
765 268603029898046653810401156
766 281003615445290042876565999
767 293968259451903984588971077
768 307522241328873045302789128
769 321691956790307949451190788
770 336504966425293407768278157
771 351990046351747090655785479
772 368177241041230549491343961
773 385097918405377078635101568
774 402784827240397771956080718
775 421272157128068648807072775
776 440595600897808236408348833
777 460792419756635348969143286
778 481901511200443930308379756
779 503963479822474094142950505
780 527020711141978912987476453
781 551117448578815906429922922
782 576299873707321051171010613
783 602616189925867095261232017
784 630116709686683129302612414
785 658853945433900706166866626
786 688882704406554002863209805
787 720260187467026641842067528
788 753046092124830865595058111
789 787302719929781877974114848
790 823095088418701307611524016
791 860491047804411109090937823
792 899561402606579225750537422
793 940380038429097465710787839
794 983024054100255603810821516
795 1027573899397631699071267010
796 1074113518592044601828554668
797 1122730500051156376023414676
798 1173516232156644150990523496
799 1226566065795741523984981346
800 1281979483702255464063640225
801 1339860276929741710289724175
802 1400316728754874991146042076
803 1463461806317386311570577574
804 1529413360319419491450568154
805 1598294333116321632648531733
806 1670232975548573897410832026
807 1745363072874631429395353625
808 1823824180183436419000377001
809 1905761867676410240900540953
810 1991327976229127961917532917
811 2080680883654986079130549572
812 2173985782115080230573850125
813 2271414967131776149949824951
814 2373148138686986002315693314
815 2479372714900688813011900328
816 2590284158810508812585349672
817 2706086318789061587635050550
818 2826991783162932007991293605
819 2953222249614531947179448237
820 3085008909977261777255600287
821 3222592851053399893235821578
822 3366225472115496260390874599
823 3516168919772801265096573566
824 3672696540917954367852945939
825 3836093354491817525765462845
826 4006656542840551475879110374
827 4184695963463761071879683905
828 4370534681991461025472564626
829 4564509527254584844362908116
830 4766971669355603829319593332
831 4978287221675227792367922046
832 5198837867796144894261014180
833 5429021514356801617509790667
834 5669252970896591145844633110
835 5919964657788722974563973356
836 6181607343409053606074753989
837 6454650911727163768214422467
838 6739585161561892464247896613
839 7036920638784904258641684620
840 7347189502816008313133167786
841 7670946428798954686328622964
842 8008769546911115113983000710
843 8361261420309406338695094290
844 8729050063284382417344080636
845 9112790001247644408750108817
846 9513163374252544522858029672
847 9930881085806008399909175445
848 10366683998809790475331359336
849 10821344180532330354030735871
850 11295666198598965107909521447
851 11790488470056524005038961944
852 12306684665661481127216974470
853 12845165171614976649359963139
854 13406878611068230395932580122
855 13992813427802350837875045256
856 14603999534594359756227230306
857 15241510028868595247079167121
858 15906462978348658674357816422
859 16600023279519836310801877863
860 17323404591836741311371095861
861 18077871350713713579322076385
862 18864740862469815891203292987
863 19685385484511735175435286087
864 20541234894182409944207887818
865 21433778449824057267909418313
866 22364567647759776845303742231
867 23335218679028902618252811225
868 24347415089878608917792786326
869 25402910550156229833534581828
870 26503531733926823801106480038
871 27651181316794308467050449384
872 28847841094598274266247862345
873 30095575228325171316999681768
874 31396533620281105120519965342
875 32752955426753882073308286597
876 34167172712616371359244756568
877 35641614253518581116458010809
878 37178809491557369930320357026
879 38781392650524164656211648448
880 40452107017090981467500139640
881 42193809394523901377814900882
882 44009474735792884432768531367
883 45902200963194451355007971951
884 47875213981904812390466958640
885 49931872895148951464570967762
886 52075675428995168370903682808
887 54310263575074403286888569611
888 56639429459872355113819514264
889 59067121449555854079615836703
890 61597450499670210339749088679
891 64234696759383204994130738715
892 66983316440355249351964820577
893 69847948960681691468660347124
894 72833424374787883760278654921
895 75944771100553755314163829301
896 79187223955412384620219699985
897 82566232513595210119258328622
898 86087469797199904394921108767
899 89756841314219606366658779932
900 93580494457213939908613901089
901 97564828276802151053560901047
902 101716503644741689497427611131
903 106042453821895615359652104633
904 110549895447019598873473748619
905 115246339962882627356675791094
906 120139605496910683624221357379
907 125237829214172678517679900907
908 130549480161254456934285041420
909 136083372620247026070298112602
910 141848679992856974802132104526
911 147854949235381610264683805460
912 154112115866132631141933894712
913 160630519567685157981239030057
914 167420920407234212242523023578
915 174494515699196717411096398438
916 181862957535171187915485622940
917 189538371007291116553516580795
918 197533373152056191162877015392
919 205861092642722433302937065772
920 214535190259460096496461740716
921 223569880167563893374956225588
922 232979952035213507219483325495
923 242780794023442926395503774951
924 252988416682282634921644921774
925 263619477788290668804992389704
926 274691308160093102309621825413
927 286221938489904935361144249641
928 298230127230513438600852233017
929 310735389578662419461814429457
930 323758027597401517955926086288
931 337319161521535188191247678134
932 351440762292054855667411991927
933 366145685367131182793920663221
934 381457705859124670246777994751
935 397401555048898573328467837904
936 414002958330741832472854966598
937 431288674643177900196720094002
938 449286537443112197406168201156
939 468025497282892430054449341481
940 487535666052197481011519080893
941 507848362948957105471714457325
942 528996162246023133430730881897
943 551012942922776989571751627040
944 573933940233567083856715556185
945 597795799287524846568784224722
946 622636630717221454439163143611
947 648496068516488160702632168379
948 675415330130856265068876323723
949 703437278887154890056461803598
950 732606488852174159575129493709
951 762969312213621555207352357362
952 794573949280222636329836060063
953 827470521201393575866809142116
954 861711145510809338536975299965
955 897350014602043061276667625719
956 934443477248641921936025342746
957 973050123285152806206676037760
958 1013230871570116053875258805810
959 1055049061356512252827714849103
960 1098570547199990774906060673242
961 1143863797540018132927110599174
962 1190999997094291962554753785783
963 1240053153211944333853704392911
964 1291100206336656925358696428545
965 1344221144736384742632011812324
966 1399499123662404096141739609925
967 1457020589106400736320448202788
968 1516875406330784524161368108713
969 1579156993353875222229452388368
970 1643962459578559459130835949025
971 1711392749759969504448473464691
972 1781552793515210951187931272218
973 1854551660585646254668619092976
974 1930502722070277175902652675544
975 2009523817856817908944612056439
976 2091737430485687891732849211460
977 2177270865690813441478414811895
978 2266256439870410218585650634956
979 2358831674750235736158800096771
980 2455139499511777420095912276794
981 2555328460667865028928623025732
982 2659552939978917233641391942449
983 2767973380713814174010135634760
984 2880756522570908529012502241937
985 2998075645586284850702637946261
986 3120110823368756408076289167058
987 3247049186013561820043058097796
988 3379085193060025385424074416575
989 3516420916871858937653321140579
990 3659266336833074787958984064602
991 3807839644766903956083888780472
992 3962367562000468659456879906364
993 4123085668513468316471046607462
994 4290238744625634364849409330729
995 4464081125694385537827577370922
996 4644877070311836488487932767909
997 4832901142508241326687792876555
998 5028438608487990111657368140604
999 5231785848443549915263898447368
1000 5443250784013190347158534129494