0 1
1 1
2 0
3 0
4 1
5 2
6 3
7 4
8 5
9 7
10 9
11 13
12 17
13 24
14 31
15 42
16 54
17 71
18 90
19 117
20 147
21 188
22 236
23 298
24 371
25 466
26 576
27 716
28 882
29 1088
30 1331
31 1633
32 1987
33 2422
34 2935
35 3557
36 4290
37 5177
38 6216
39 7465
40 8932
41 10682
42 12731
43 15169
44 18016
45 21387
46 25321
47 29955
48 35353
49 41696
50 49063
51 57689
52 67698
53 79375
54 92896
55 108633
56 126817
57 147922
58 172272
59 200456
60 232916
61 270409
62 313504
63 363168
64 420173
65 485719
66 560825
67 647025
68 745632
69 858589
70 987616
71 1135142
72 1303401
73 1495470
74 1714197
75 1963461
76 2246941
77 2569474
78 2935767
79 3351915
80 3823877
81 4359295
82 4965752
83 5652769
84 6429956
85 7309224
86 8302647
87 9425089
88 10691776
89 12121159
90 13732346
91 15548309
92 17592910
93 19894667
94 22483410
95 25394414
96 28664859
97 32338423
98 36461249
99 41087317
100 46273914
101 52087542
102 58599132
103 65890647
104 74049653
105 83176964
106 93380627
107 104784359
108 117521206
109 131742946
110 147612974
111 165317192
112 185056145
113 207057061
114 231565613
115 258859386
116 289238723
117 323042199
118 360636647
119 402434340
120 448882599
121 500483027
122 557780100
123 621383276
124 691954663
125 770233607
126 857024055
127 953222151
128 1059802556
129 1177850056
130 1308545046
131 1453198870
132 1613239194
133 1790249737
134 1985954801
135 2202264770
136 2441260110
137 2705242338
138 2996718526
139 3318458799
140 3673480500
141 4065113991
142 4496987063
143 4973098999
144 5497806586
145 6075907809
146 6712628808
147 7413719705
148 8185443359
149 9034683510
150 9968937318
151 10996438017
152 12126150675
153 13367912666
154 14732434202
155 16231457464
156 17877764691
157 19685359024
158 21669480175
159 23846811753
160 26235506878
161 28855423724
162 31728165237
163 34877347608
164 38328654934
165 42110147171
166 46252333776
167 50788524593
168 55754928507
169 61191054144
170 67139836061
171 73648094935
172 80766697563
173 88551082374
174 97061462479
175 106363427029
176 116528192467
177 127633293505
178 139762892750
179 153008571427
180 167469711063
181 183254399671
182 200479895234
183 219273667755
184 239773960416
185 262130983736
186 286507595467
187 313080670818
188 342041917782
189 373599453271
190 407978778942
191 445424589677
192 486201941605
193 530598328854
194 578925071937
195 631519707272
196 688747634811
197 751004861644
198 818719957310
199 892357206136
200 972418915691
201 1059449043777
202 1154035920386
203 1256816414175
204 1368479141190
205 1489769252839
206 1621492204299
207 1764519262535
208 1919791926845
209 2088328256700
210 2271228055705
211 2469680143358
212 2684968416455
213 2918480211276
214 3171713384202
215 3446285917547
216 3743944187344
217 4066573998819
218 4416210218597
219 4795049458746
220 5205461288473
221 5650002799538
222 6131431650853
223 6652722794630
224 7217083625751
225 7827973194053
226 8489119784412
227 9204542967753
228 9978573992027
229 10815881089041
230 11721493090822
231 12700828476898
232 13759722706166
233 14904461534371
234 16141812631118
235 17479063789829
236 18924059456362
237 20485244549870
238 22171706638091
239 23993226162774
240 25960325110637
241 28084324567584
242 30377400827282
243 32852651338523
244 35524159347651
245 38407069420790
246 41517661882804
247 44873439284158
248 48493212043432
249 52397197429904
250 56607118038943
251 61146315044674
252 66039861377519
253 71314691268794
254 76999730223150
255 83126043169689
256 89726983640061
257 96838363117503
258 104498622180054
259 112749024024730
260 121633850671899
261 131200624063109
262 141500330881252
263 152587675037900
264 164521335166849
265 177364252868375
266 191183927439151
267 206052744851136
268 222048314937830
269 239253846703686
270 257758533914741
271 277657983128344
272 299054654383134
273 322058349216041
274 346786714092150
275 373365796589168
276 401930620255521
277 432625818278562
278 465606289558997
279 501037920443937
280 539098333159950
281 579977707526186
282 623879634397819
283 671022050904213
284 721638213158582
285 775977760379351
286 834307823064182
287 896914233296597
288 964102786746452
289 1036200618792262
290 1113557641041599
291 1196548105500935
292 1285572239084371
293 1381058020872751
294 1483463041181026
295 1593276520276043
296 1711021421938671
297 1837256745725400
298 1972579928924328
299 2117629448497748
300 2273087549759555
301 2439683198875273
302 2618195181432612
303 2809455451678465
304 3014352649796321
305 3233835899869480
306 3468918800993836
307 3720683732701147
308 3990286381971693
309 4278960622393822
310 4588023647162947
311 4918881496562253
312 5273034876009128
313 5652085416009709
314 6057742264217380
315 6491829172725094
316 6956291964473668
317 7453206554576041
318 7984787404144957
319 8553396595898363
320 9161553402558877
321 9811944552154428
322 10507435054238661
323 11251079807101669
324 12046135843070393
325 12896075448993098
326 13804600011851489
327 14775654845313520
328 15813444839609012
329 16922451210721274
330 18107449183902224
331 19373526909077373
332 20726105435606222
333 22170960067676343
334 23714242919922872
335 25362507020149776
336 27122731771217691
337 29002350146412655
338 31009277422809619
339 33151941857085868
340 35439317100545716
341 37880956790409032
342 40487031106973522
343 43268365768727522
344 46236483248070201
345 49403646718185925
346 52782906506818514
347 56388149609158207
348 60234152029645437
349 64336634549788307
350 68712321686420142
351 73379004486786086
352 78355606919922474
353 83662256564200028
354 89320359347057136
355 95352679094536979
356 101783421644325168
357 108638324343323458
358 115944750682139557
359 123731790956446121
360 132030368708585937
361 140873353913963268
362 150295682668525713
363 160334484423807796
364 171029216530659109
365 182421807227305481
366 194556806841150633
367 207481548436679578
368 221246317690274051
369 235904533330571822
370 251512937939784581
371 268131800570444723
372 285825130992680657
373 304660907152383971
374 324711315679901910
375 346053007167986648
376 368767366088249190
377 392940797215897445
378 418665028469005710
379 446037432196555361
380 475161364865786347
381 506146527363931387
382 539109345916949118
383 574173376037987443
384 611469729570861495
385 651137527456869343
386 693324378363670854
387 738186886041679906
388 785891185631728016
389 836613512048971286
390 890540800766916871
391 947871324410044272
392 1008815365594635738
393 1073595929738238639
394 1142449498410072957
395 1215626827284582110
396 1293393789424435675
397 1376032268329071968
398 1463841101651490232
399 1557137080430911431
400 1656256004944834766
401 1761553802479452112
402 1873407708352661919
403 1992217515982998230
404 2118406897601203737
405 2252424801942065869
406 2394746930810517283
407 2545877301457080814
408 2706349896995633785
409 2876730412453684339
410 3057618099071826911
411 3249647715164060293
412 3453491586588370739
413 3669861785931825099
414 3899512433950221275
415 4143242133236361797
416 4401896538210102973
417 4676371072362426665
418 4967613797468452884
419 5276628446754854173
420 5604477627438365513
421 5952286205777644340
422 6321244880843704151
423 6712613961425692889
424 7127727353161214466
425 7567996771709626464
426 8034916190051638237
427 8530066537274106720
428 9055120658037310910
429 9611848551781064589
430 10202122902112889732
431 10827924917302163482
432 11491350493720429600
433 12194616725205343553
434 12940068771750224530
435 13730187112759674225
436 14567595200016596101
437 15455067538091619340
438 16395538209290064465
439 17392109873607104006
440 18448063262961767272
441 19566867203199595135
442 20752189185558893171
443 22007906524413856082
444 23338118125695066987
445 24747156906457599377
446 26239602893010834081
447 27820297042110136488
448 29494355815977643154
449 31267186560089070988
450 33144503718229085416
451 35132345938635042812
452 37237094109885916635
453 39465490385736777013
454 41824658242171757248
455 44322123631800023779
456 46965837284001606081
457 49764198222468198927
458 52726078554247967378
459 55860849609123808114
460 59178409489762500709
461 62689212119374444272
462 66404297854349735557
463 70335325757317257242
464 74494607605889352767
465 78895143742130642322
466 83550660846657185766
467 88475651752965000785
468 93685417395481595392
469 99196111018563390627
470 105024784750556902851
471 111189438682949446830
472 117709072570493453902
473 124603740306424451261
474 131894607301693029195
475 139604010937843115682
476 147755524236888394919
477 156374022934901297497
478 165485756118634444118
479 175118420630691328382
480 185301239420239433001
481 196065044065473974426
482 207442361664372491378
483 219467506342728386407
484 232176675597613260033
485 245608051750325521194
486 259801908750870020258
487 274800724635609538485
488 290649299906538654085
489 307394882164180419403
490 325087297291725198890
491 343779087555815670823
492 363525656953822843360
493 384385424209762917796
494 406419983784283524407
495 429694275341302006013
496 454276762076001873522
497 480239618391246047016
498 507658927370471794237
499 536614888583040519142
500 567192036717948982629
501 599479471635681609574
502 633571100386881336270
503 669565891846789627465
504 707568144572343501293
505 747687768595939410000
506 790040581826935936194
507 834748621846448456162
508 881940473837257507653
509 931751615513037501634
510 984324779866715243288
511 1039810336688620990276
512 1098366693760175873574
513 1160160718768820138220
514 1225368182944590929218
515 1294174227568509401199
516 1366773854457466125323
517 1443372441690547760922
518 1524186285796328126122
519 1609443171792206009170
520 1699382972421737010807
521 1794258278119630710993
522 1894335059189538472451
523 1999893361876547012866
524 2111228039972675372696
525 2228649523804538983218
526 2352484628410012592205
527 2483077402936750497799
528 2620790023254821107609
529 2766003730018042330842
530 2919119814370228060358
531 3080560653752464067404
532 3250770800231906626644
533 3430218124051455550072
534 3619395015067415872064
535 3818819645041521633165
536 4029037293725550891306
537 4250621741998036202591
538 4484176735289279514008
539 4730337520875910324202
540 4989772462608674503516
541 5263184737007771855427
542 5551314114649242907385
543 5854938831164185800400
544 6174877552169566529653
545 6511991436877525204761
546 6867186305136105376059
547 7241414913114684664292
548 7635679342863822938991
549 8051033511474412193475
550 8488585805589346299927
551 8949501847553725446507
552 9435007399531545956891
553 9946391412490255084045
554 10485009227011969075695
555 11052285933507531430315
556 11649719899484527877192
557 12278886472185288345714
558 12941441865005689613206
559 13639127236821860122671
560 14373772973469073413728
561 15147303181389010530241
562 15961740403603934859685
563 16819210569008400615983
564 17721948186139797846529
565 18672301793486211153483
566 19672739678592523291058
567 20725855879193371343787
568 21834376479839543705778
569 23001166218528437287957
570 24229235418126921438789
571 25521747258501633264429
572 26882025405593838399139
573 28313562014892229904338
574 29820026127128573568099
575 31405272475334396387824
576 33073350722823517905199
577 34828515153083628622398
578 36675234833047980584976
579 38618204272750625573321
580 40662354604924495117661
581 42812865309757545975541
582 45075176510653557862661
583 47455001868634004777554
584 49958342103732519027969
585 52591499173668544678078
586 55361091140894573808837
587 58274067761203975565286
588 61337726827996872480949
589 64559731308564951407295
590 67948127309780087783493
591 71511362913020445221171
592 75258307919317124605755
593 79198274548354339603764
594 83341039136244068114685
595 87696864879864195546110
596 92276525676990082043463
597 97091331114554356432737
598 102153152658979271037121
599 107474451105887856698730
600 113068305348295562562042
601 118948442526024890245336
602 125129269621085813293965
603 131625906567708432228559
604 138454220947940050158480
605 145630864347991308515080
606 153173310452989920070740
607 161099894962429889796484
608 169429857411350998773080
609 178183384987300265475163
610 187381658436174016599611
611 197046900155477042599018
612 207202424576911999947683
613 217872690946107058629264
614 229083358611028733345173
615 240861344937018046306222
616 253234885970524749890418
617 266233599980544681808592
618 279888554011338390671531
619 294232333587524988684005
620 309299115717697147420112
621 325124745350854979494559
622 341746815445533593423062
623 359204750820341821443123
624 377539895960782382838443
625 396795606966816834084792
626 417017347832422386860849
627 438252791258795977883972
628 460551924210335834278743
629 483967158433824709810147
630 508553446169470824397352
631 534368401294718453376085
632 561472426150800800600929
633 589928844315308860772869
634 619804039594017698874199
635 651167601519648129970496
636 684092477656202065776389
637 718655133023179799785928
638 754935716966033571619362
639 793018237816221872815492
640 832990745697462277924108
641 874945523853246656728325
642 918979288885214056321667
643 965193400312024210541430
644 1013694079874324958327380
645 1064592641033172863545526
646 1118005729126766966178998
647 1174055572673988434757012
648 1232870246332433301152191
649 1294583946044286206669063
650 1359337276924427501172511
651 1427277554473029926617828
652 1498559119717965475264600
653 1573343668922600306802687
654 1651800598519825279150234
655 1734107365966026748245216
656 1820449867236379046781631
657 1911022831718521412722496
658 2006030235291985401033084
659 2105685732419488105870275
660 2210213108109375453788021
661 2319846750650581396866302
662 2434832146057763659523253
663 2555426395209977887888869
664 2681898754705955667632449
665 2814531202508684612093370
666 2953619029495409279237475
667 3099471458083074307251418
668 3252412289146703797211607
669 3412780578506751176669116
670 3580931344313342740402516
671 3757236306718914886450706
672 3942084661287446859628410
673 4135883887657537089768381
674 4339060595038516911016394
675 4552061406193781364529654
676 4775353881633174750712222
677 5009427485817704363271146
678 5254794597253735629908602
679 5511991564442260860359517
680 5781579809729489197088449
681 6064146983201048464993659
682 6360308168850122102828458
683 6670707145354143527283630
684 6996017703890733924364801
685 7336945025536831690585721
686 7694227120899767096602656
687 8068636334752028539028425
688 8460980918555785341996619
689 8872106673896787946084687
690 9302898669971936734553964
691 9754283038419832389866395
692 10227228848919553562875908
693 10722750069140374692969860
694 11241907612773320712278693
695 11785811479546430244809559
696 12355622991287107731612070
697 12952557128280579380699011
698 13577884970349467421756513
699 14232936247281040791296013
700 14919102003420455857803445
701 15637837381467108492486182
702 16390664530720104011527188
703 17179175645256391834935042
704 18005036137752617576085690
705 18869987954919611050304913
706 19775853040766172634132523
707 20724536954188738294747089
708 21718032647653241289844647
709 22758424414039329753370496
710 23847892009010735451770387
711 24988714956605382491391521
712 26183277046058424876354871
713 27434071028229346527932686
714 28743703520352062877392932
715 30114900128215441632690459
716 31550510795260101952036965
717 33053515388498946199470924
718 34627029531580591683456039
719 36274310695772379586116923
720 37998764560087481633028438
721 39803951652277081207713313
722 41693594282895678194334891
723 43671583785186254519481430
724 45741988074061698327719911
725 47909059538043362729936060
726 50177243278593526567492983
727 52551185711912647329663444
728 55035743548898365896711608
729 57635993169651165964840775
730 60357240409592116047693182
731 63205030775004408136592989
732 66185160106550023893980352
733 69303685710122385543182975
734 72566937975199580567863243
735 75981532501740819765470345
736 79554382757542077089826170
737 83292713288919217378399713
738 87204073508535660146258250
739 91296352085224489914042378
740 95577791961685505551238395
741 100057006027057800286235780
742 104742993472487802695730405
743 109645156859027332843058852
744 114773319928411815000458990
745 120137746188585824858869254
746 125749158307163097809722394
747 131618758347436112834202479
748 137758248882983460234498688
749 144179855028471382177676186
750 150896347425801624868437091
751 157921066226436114711218894
752 165267946112417673180938814
753 172951542400425373924825080
754 180987058275035945144917193
755 189390373199334734318615567
756 198178072553008713083513114
757 207367478550191507779778479
758 216976682491488619569922154
759 227024578406927606186160880
760 237530898148919521720486449
761 248516247996828446767633797
762 260002146837286100850316509
763 272011065987109030004310034
764 284566470728431199658908245
765 297692863628612636287870549
766 311415829720473171857170953
767 325762083621594231793886099
768 340759518674672451733875175
769 356437258194369155643939882
770 372825708909613948172859833
771 389956616694069221025463615
772 407863124681272618074189633
773 426579833865035071585902791
774 446142866289802787702516995
775 466589930940089792732455277
776 487960392442565427934416993
777 510295342699144805634389705
778 533637675574283667520826913
779 558032164764838073987246424
780 583525544986109402220540731
781 610166596613281876060937797
782 638006233923160000488020395
783 667097597087162790618296433
784 697496148072708126693651156
785 729259770616670696051217272
786 762448874441288837471481120
787 797126503889987236204184877
788 833358451167831967518101775
789 871213374379011710130500294
790 910762920561591889484336510
791 952081853928099267727439118
792 995248189529000205442034999
793 1040343332565131589554634982
794 1087452223584355256796619692
795 1136663489807443247449037162
796 1188069602838176833641066520
797 1241767043023179701014267733
798 1297856470737807329302324535
799 1356442904885817996081218605
800 1417635908912245833137113619
801 1481549784641235909797326644
802 1548303774263262334784671919
803 1618022270809501916244254192
804 1690835037464841445014138202
805 1766877436085442110585955417
806 1846290665301619367766158664
807 1929222008602424343533271868
808 2015825092814368512085361605
809 2106260157403638944280747066
810 2200694335048526762641864445
811 2299301943947077898703966579
812 2402264792343776998487198493
813 2509772495778853958470612784
814 2622022807584145983266602300
815 2739221963170838990018798461
816 2861585038676421659235788653
817 2989336324561318322653381062
818 3122709714769476710521381227
819 3261949112092201373722591662
820 3407308850400278733447792988
821 3559054134436487436854975670
822 3717461497888444584697904861
823 3882819280490982035134999645
824 4055428124937374460819814334
825 4235601494410356254504698380
826 4423666211576444626888399735
827 4619963019921263193631715876
828 4824847168338789965369356856
829 5038689019924396864860669266
830 5261874685959638993197507821
831 5494806686116682193993541934
832 5737904635951438880269919149
833 5991605962797637778823444843
834 6256366651218571848915418205
835 6532662019219906665616509680
836 6820987526475053640723768987
837 7121859615865010005139620409
838 7435816589686580263945086682
839 7763419521937349830821316994
840 8105253208141994823472563700
841 8461927154243348802185785332
842 8834076606142395078380163415
843 9222363621534918438938514876
844 9627478185758192803536529254
845 10050139373429749780496398776
846 10491096557731199046058459084
847 10951130669264247253468487357
848 11431055506482690261258374087
849 11931719099784272247387690783
850 12454005131429087030528331183
851 12998834413537728338055151858
852 13567166426511817973990317079
853 14160000920312991137910171332
854 14778379581133005549503496283
855 15423387766088555863137098970
856 16096156308678693036890117806
857 16797863397851715767433938803
858 17529736533641059645683922744
859 18293054562447363521079112404
860 19089149795165548423977643840
861 19919410211482767576113726511
862 20785281753804447145753241226
863 21688270714402765844136901053
864 22629946219523750702862696058
865 23611942814337192978312727635
866 24635963152766707434054979065
867 25703780796397037290756635780
868 26817243126821002048142317648
869 27978274375960937152758725049
870 29188878779077899025017629778
871 30451143855368024819543040675
872 31767243821238018148018176203
873 33139443141552579791323078888
874 34570100224354448570622056728
875 36061671264774447422791844896
876 37616714244073232451872258129
877 39237893089990293368719781238
878 40927982004817797134674551914
879 42689869967869171997619654617
880 44526565419273496045721737665
881 46441201132298950974963708297
882 48437039281690381357052466353
883 50517476715799634190736086708
884 52686050440591349189423594751
885 54946443323923608029009655120
886 57302490028830788906688692070
887 59758183184877606739080069721
888 62317679807007058551568035128
889 64985307971673453944286868422
890 67765573760433251722626705231
891 70663168481563788208365825686
892 73682976180691479782072144019
893 76830081451839587177285056428
894 80109777560749400285090322323
895 83527574892790754845145070972
896 87089209738256333110303927746
897 90800653428332391461754266092
898 94668121835554553607333994677
899 98698085253094425088676810822
900 102897278667779125410584131994
901 107272712442324877454433818220
902 111831683422865589206523653907
903 116581786488481560545178932182
904 121530926560080044180717586663
905 126687331086652215171635526451
906 132059563027628101054302858387
907 137656534350776214318687553048
908 143487520065845901217875129284
909 149562172814931994943534660888
910 155890538041351074991470703925
911 162483069759660917312542106570
912 169350646950327357541116454693
913 176504590603450432590591277412
914 183956681436902048888661082421
915 191719178315205431798329080684
916 199804837396499924715097446577
917 208226932035988456672285176510
918 216999273475356819328977271130
919 226136232348789175284450604099
920 235652761037380547531775458513
921 245564416904970074407405703733
922 255887386449686097683905284309
923 266638510406811630707027823643
924 277835309839943927252590415887
925 289496013258840990250118950720
926 301639584803818380332606572804
927 314285753538088177004070856445
928 327455043891015829783444371741
929 341168807296916819713903585635
930 355449255075720918358398828373
931 370319492603604644157724961328
932 385803554823529629554314466885
933 401926443147533664151781194303
934 418714163804599498138553326520
935 436193767689982109924590926280
936 454393391774005370279512155611
937 473342302130552324048483783471
938 493070938647766952507770417552
939 513610961485868167982685178928
940 534995299349446211580069849537
941 557258199644176934543091773842
942 580435280590547926488178053238
943 604563585369951962051873539076
944 629681638381365060615228202375
945 655829503689798964749686044504
946 683048845750798346853968008249
947 711382992498452473252617246876
948 740877000887706721441947682672
949 771577724985202763854884768516
950 803533886706444767818453697850
951 836796149300794735780235804696
952 871417193689640538627839487649
953 907451797767068047710045282391
954 944956918776501526594512234629
955 983991778881067559063855353492
956 1024617954049884821192525738061
957 1066899466387099137491491541598
958 1110902880035268143404402040037
959 1156697400789667463682172188035
960 1204354979565238369110262175573
961 1253950419863241162269769807352
962 1305561489390216958314230044501
963 1359269035987609701156696307368
964 1415157108036358233368713078542
965 1473313079506952564700658350008
966 1533827779831857379870054855670
967 1596795628783857803356317896304
968 1662314776550775919586565063015
969 1730487249204161067560257835569
970 1801419099766971141618388282911
971 1875220565092956656282839349150
972 1952006228778433085183774114937
973 2031895190335401733358027391138
974 2115011240863554354625540149340
975 2201483045467594871091887799230
976 2291444332675532425963444845512
977 2385034091123167885144082878272
978 2482396773779910702693230870619
979 2583682510001350430790553971821
980 2689047325704667403754425634710
981 2798653371974027360450306834756
982 2912669162414565766183823717457
983 3031269819585457996348665056345
984 3154637330854892634964944770733
985 3282960814032547197645166154927
986 3416436793148410459757368697019
987 3555269484760535265362400269075
988 3699671095188542683550219276403
989 3849862129084466513673368565838
990 4006071709767829580028322756490
991 4168537911767715798845580015205
992 4337508106031048563774455093360
993 4513239318273344450876929380242
994 4695998600965886340991504473059
995 4886063419471591865806578927733
996 5083722052860847268898556101565
997 5289274009958275738941550354340
998 5503030461191819686609369944551
999 5725314686836683183612350388180
1000 5956462542268611626940369846426