0 1
1 0
2 0
3 0
4 0
5 1
6 1
7 2
8 3
9 5
10 7
11 10
12 13
13 18
14 23
15 31
16 39
17 51
18 64
19 81
20 102
21 128
22 159
23 198
24 245
25 304
26 374
27 460
28 563
29 689
30 841
31 1023
32 1242
33 1505
34 1819
35 2195
36 2642
37 3173
38 3804
39 4551
40 5435
41 6477
42 7707
43 9151
44 10850
45 12843
46 15175
47 17902
48 21089
49 24802
50 29132
51 34164
52 40012
53 46796
54 54663
55 63766
56 74296
57 86458
58 100493
59 116670
60 135306
61 156736
62 181375
63 209663
64 242116
65 279314
66 321915
67 370650
68 426373
69 490020
70 562666
71 645509
72 739920
73 847411
74 969726
75 1108792
76 1266786
77 1446162
78 1649677
79 1880399
80 2141817
81 2437793
82 2772683
83 3151361
84 3579287
85 4062545
86 4607973
87 5223188
88 5916698
89 6698022
90 7577774
91 8567757
92 9681196
93 10932776
94 12338861
95 13917698
96 15689558
97 17676989
98 19905098
99 22401751
100 25197899
101 28327942
102 31830042
103 35746515
104 40124346
105 45015586
106 50477879
107 56575166
108 63378175
109 70965196
110 79422906
111 88847116
112 99343746
113 111029940
114 124035042
115 138501917
116 154588321
117 172468357
118 192334037
119 214397263
120 238891551
121 266074278
122 296229097
123 329668386
124 366736032
125 407810728
126 453309011
127 503689159
128 559455171
129 621161106
130 689415801
131 764888359
132 848313562
133 940498270
134 1042328265
135 1154775597
136 1278906558
137 1415890938
138 1567011152
139 1733673041
140 1917417312
141 2119931882
142 2343065411
143 2588842447
144 2859479028
145 3157400526
146 3485260681
147 3845962312
148 4242679688
149 4678883604
150 5158367443
151 5685276505
152 6264139642
153 6899903284
154 7597968560
155 8364232279
156 9205130052
157 10127684449
158 11139556684
159 12249102577
160 13465433320
161 14798482126
162 16259075158
163 17859009582
164 19611137942
165 21529459161
166 23629217321
167 25927009679
168 28440901783
169 31190553800
170 34197356886
171 37484580209
172 41077530636
173 45003726193
174 49293082062
175 53978113379
176 59094154236
177 64679593941
178 70776132783
179 77429059612
180 84687549767
181 92604988765
182 101239322093
183 110653431734
184 120915543929
185 132099670342
186 144286082152
187 157561824047
188 172021268725
189 187766714131
190 204909029024
191 223568350262
192 243874832857
193 265969460724
194 290004921410
195 316146547291
196 344573331766
197 375479025687
198 409073316117
199 445583098998
200 485253850705
201 528351103046
202 575162034400
203 625997183584
204 681192292860
205 741110294399
206 806143449332
207 876715647296
208 953284883443
209 1036345924595
210 1126433174591
211 1224123758954
212 1330040844127
213 1444857202776
214 1569299051167
215 1704150175081
216 1850256361763
217 2008530166517
218 2179956036387
219 2365595811420
220 2566594639275
221 2784187329132
222 3019705173448
223 3274583276661
224 3550368427436
225 3848727545255
226 4171456753290
227 4520491117868
228 4897915097338
229 5305973758727
230 5747084815804
231 6223851537550
232 6739076602242
233 7295776956781
234 7897199749287
235 8546839417585
236 9248456014888
237 10006094849017
238 10824107541536
239 11707174599692
240 12660329602045
241 13688985118782
242 14798960488485
243 15996511566006
244 17288362597460
245 18681740360065
246 20184410718880
247 21804717777610
248 23551625801547
249 25434764089295
250 27464475016154
251 29651865456248
252 32008861810433
253 34548268896013
254 37283832963967
255 40230309106331
256 43403533376785
257 46820499933316
258 50499443536210
259 54459927777949
260 58722939432516
261 63310989316742
262 68248220131305
263 73560521735615
264 79275654350598
265 85423380234850
266 92035604402353
267 99146524964071
268 106792793765954
269 115013687995787
270 123851293479667
271 133350700462073
272 143560212699295
273 154531570720214
274 166320190229281
275 178985416633418
276 192590796746183
277 207204368821625
278 222898972120964
279 239752577266908
280 257848638787688
281 277276471284114
282 298131650752514
283 320516442727144
284 344540258990762
285 370320144678313
286 397981297793873
287 427657623224030
288 459492323465273
289 493638528470916
290 530259967141009
291 569531683104908
292 611640797701405
293 656787323166806
294 705185029239354
295 757062366638019
296 812663451054063
297 872249111486353
298 936098007083288
299 1004507816837728
300 1077796506750034
301 1156303679425428
302 1240392011335612
303 1330448783256689
304 1426887509848766
305 1530149674618599
306 1640706576892385
307 1759061297911040
308 1885750793537789
309 2021348121494505
310 2166464811643071
311 2321753388254684
312 2487910053754322
313 2665677544092624
314 2855848166455655
315 3059267030631064
316 3276835486170481
317 3509514778122317
318 3758329934869869
319 4024373902543921
320 4308811941269039
321 4612886299386946
322 4937921182921074
323 5285328038467634
324 5656611168785067
325 6053373701635123
326 6477323933568779
327 6930282071613536
328 7414187397347205
329 7931105879191467
330 8483238260274427
331 9072928650996622
332 9702673657059212
333 10375132075499059
334 11093135193393299
335 11859697725814131
336 12678029431756179
337 13551547449232521
338 14483889393031284
339 15478927261165201
340 16540782198950384
341 17673840172392251
342 18882768605562085
343 20172534040064585
344 21548420877959587
345 23016051273058665
346 24581406239537447
347 26250848050684183
348 28031144004804505
349 29929491640050938
350 31953545484522490
351 34111445432978927
352 36411846847067618
353 38863952481413157
354 41477546343808461
355 44263029604295557
356 47231458674360226
357 50394585584449976
358 53764900795685324
359 57355678589300005
360 61181025185536164
361 65255929752785317
362 69596318476769124
363 74219111869273274
364 79142285506549392
365 84384934398185539
366 89967341198655378
367 95911048486269558
368 102238935346796688
369 108975298512548857
370 116145938322333821
371 123778249782567936
372 131901319025680989
373 140546025479185525
374 149745150076252070
375 159533489857356016
376 169947979332715424
377 181027818995909349
378 192814611400986289
379 205352505239142357
380 218688347875250103
381 232871846830426020
382 247955740724575030
383 263995980221447440
384 281051919549064435
385 299186519201031047
386 318466560457751020
387 338962872402300126
388 360750572143857084
389 383909319001106102
390 408523583439807400
391 434682931603607508
392 462482326323380581
393 492022445539581622
394 523410019124496394
395 556758185145671798
396 592186866669326325
397 629823170264076711
398 669801807428926679
399 712265540237078518
400 757365652558939727
401 805262448302481756
402 856125778188090645
403 910135596659286017
404 967482550618091281
405 1028368601766516522
406 1093007684433932282
407 1161626400872672773
408 1234464756112431572
409 1311776934579207941
410 1393832120804324056
411 1480915366675893070
412 1573328507819473359
413 1671391131834986634
414 1775441601265046697
415 1885838134327040317
416 2002959946605130792
417 2127208457071643648
418 2259008561990575503
419 2398809980447700149
420 2547088675453848546
421 2704348354782184616
422 2871122055923925439
423 3047973819783208893
424 3235500457981498417
425 3434333418903256968
426 3645140757890044500
427 3868629217281692443
428 4105546422307842172
429 4356683199154735913
430 4622876021871634942
431 4905009595136889327
432 5204019580278302495
433 5520895472338384069
434 5856683636389372550
435 6212490511739810484
436 6589485993135373530
437 6988906998539725934
438 7412061233589783734
439 7860331163356825634
440 8335178202607159883
441 8838147136348669598
442 9370870783074282797
443 9935074913768373696
444 10532583440431513492
445 11165323888606166491
446 11835333169147779876
447 12544763665288136015
448 13295889651883181935
449 14091114064624130483
450 14932975637923393645
451 15824156431170061924
452 16767489764080089958
453 17765968582951019587
454 18822754280773227288
455 19941185995347634286
456 21124790410819845564
457 22377292089367790819
458 23702624361171283664
459 25104940802255836580
460 26588627331343666985
461 28158314958460958305
462 29818893219749711191
463 31575524334721099056
464 33433658124062890708
465 35399047728085960598
466 37477766167969829555
467 39676223794143879528
468 42001186668428803449
469 44459795928969792207
470 47059588189517247703
471 49808517027264407197
472 52714975616241469365
473 55787820566192837164
474 59036397029939843897
475 62470565145465337530
476 66100727882348497581
477 69937860365742616246
478 73993540754834900803
479 78279982756657352331
480 82810069860246075257
481 87597391380485282312
482 92656280405523103923
483 98001853746426680458
484 103650053992766701252
485 109617693783089954508
486 115922502404771226637
487 122583174843548511776
488 129619423409141749221
489 137052032069757078091
490 144902913635002358549
491 153195169933791875320
492 161953155141222057174
493 171202542416175509479
494 180970394019565080947
495 191285235091689956706
496 202177131276163790540
497 213677770387300760494
498 225820548327738702964
499 238640659473464792070
500 252175191754300455705
501 266463226669332343134
502 281545944488773625884
503 297466734906320124507
504 314271313419266437208
505 332007843727501139905
506 350727066457025890003
507 370482434528883478566
508 391330255510371737106
509 413329841302186562740
510 436543665532725864879
511 461037529049239711682
512 486880733914857584021
513 514146266340815352796
514 542910989004491215847
515 573255843226173675881
516 605266061500886997470
517 639031390906145680767
518 674646327932238290530
519 712210365308621327516
520 751828251428299077572
521 793610263001721387379
522 837672491602826288849
523 884137144802460130218
524 933132862618579249521
525 984795050048461753420
526 1039266226485718754467
527 1096696392864254761618
528 1157243417412587123450
529 1221073440945188214254
530 1288361302662836741155
531 1359290987481468733941
532 1434056095958812570420
533 1512860337940262565454
534 1595918051100121397485
535 1683454745611644559383
536 1775707676239353399995
537 1872926443209991548996
538 1975373623284423532923
539 2083325432521832400193
540 2197072422299930936750
541 2316920210230717521513
542 2443190247690722246516
543 2576220625767887531603
544 2716366921514394044429
545 2864003086486036183910
546 3019522379644385822890
547 3183338346798165219622
548 3355885848865167226021
549 3537622141345953263527
550 3729028007515665981830
551 3930608947960827624725
552 4142896429214232728358
553 4366449194373254298891
554 4601854638725316356933
555 4849730253549252189351
556 5110725141413078410859
557 5385521606447654427349
558 5674836823242121150974
559 5979424588181273110484
560 6300077157227446323140
561 6637627174340501056276
562 6992949694929448785364
563 7366964308938593863828
564 7760637368390192854228
565 8174984324435034741718
566 8611072179202453099954
567 9070022057992614327896
568 9553011907617010588461
569 10061279326968421855492
570 10596124536189792369624
571 11158913491113087510684
572 11751081149954836875933
573 12374134899585397749854
574 13029658149034674148312
575 13719314098258758263147
576 14444849690570491470360
577 15208099757533043725378
578 16010991365530044454467
579 16855548373659431482112
580 17743896213051904172417
581 18678266898189538312789
582 19661004281296735282505
583 20694569561395240340805
584 21781547060158472735907
585 22924650277268983761262
586 24126728238577649195862
587 25390772150985343611439
588 26719922378618617410618
589 28117475755551606198192
590 29586893251038350701099
591 31131808003964342977933
592 32756033744004932727941
593 34463573617792708639429
594 36258629439247769827592
595 38145611384115610281661
596 40129148149688857831731
597 42214097601663210891828
598 44405557931096532824503
599 46708879345505129918728
600 49129676319244891967982
601 51673840429489403054836
602 54347553805334551467781
603 57157303218832000803343
604 60109894848084629309033
605 63212469743928219618717
606 66472520033178045743510
607 69897905892939390917601
608 73496873332070320696303
609 77278072817546354765762
610 81250578785213259539588
611 85423910076229295767238
612 89808051342395460316063
613 94413475465555221696208
614 99251167038317705662165
615 104332646955524270846386
616 109669998168142100028210
617 115275892653634067752542
618 121163619659326318578964
619 127347115277878434752971
620 133840993416660633943427
621 140660578225663315493809
622 147821938051511855475661
623 155341920988239339304393
624 163238192098687829395969
625 171529272383770901356177
626 180234579580342817676573
627 189374470872089541180513
628 198970287601690769755753
629 209044402076507418109208
630 219620266564233094868012
631 230722464579319000402231
632 242376764565547406480117
633 254610176084898098422177
634 267451008627833816805951
635 280928933165334024032483
636 295075046568441039079367
637 309921939026758877174029
638 325503764603273458919218
639 341856315069054313935534
640 359017097167864021164026
641 377025413467454265684681
642 395922446961379147577132
643 415751349592520310004238
644 436557334877208043604830
645 458387774816852039461001
646 481292301292379726113628
647 505322912145534423578623
648 530534082160226064528538
649 556982879166670761362143
650 584729085501019394437495
651 613835325063577990003420
652 644367196229582992890484
653 676393410877832292022668
654 709985939814308806619241
655 745220164880289157778212
656 782175038047327756552090
657 820933247814970060240065
658 861581393241102236953528
659 904210165949513325713526
660 948914540474556841241588
661 995793973318779336021659
662 1044952611116062372308363
663 1096499508310231843204054
664 1150548854777255983396007
665 1207220213838113201415592
666 1266638771129197215140567
667 1328935594817775383259201
668 1394247907671563395623516
669 1462719371513964275373676
670 1534500384619982156445678
671 1609748392632303189889838
672 1688628213602580961878985
673 1771312377789617460362269
674 1857981482873940080685836
675 1948824565277289909720828
676 2044039488305808052308818
677 2143833347867288443584052
678 2248422896545813426497343
679 2358034986851460589011627
680 2472907034498626363763862
681 2593287502603917015463014
682 2719436407733576738440389
683 2851625848771123992597995
684 2990140559618322526943483
685 3135278486786897235982889
686 3287351392984594362948999
687 3446685487847361540361828
688 3613622087019669930898624
689 3788518300837405692406495
690 3971747753922412622667906
691 4163701337054767288099846
692 4364787992748311007654558
693 4575435536016953113420752
694 4796091511883904467582052
695 5027224091253410937628947
696 5269323006834850202533405
697 5522900530882353351233017
698 5788492496589541413790392
699 6066659365058658136548900
700 6357987339846471184861908
701 6663089531175947059228174
702 6982607171993029300859306
703 7317210888142019985046461
704 7667602025031242035275444
705 8034514033263012711693527
706 8418713915808661680455512
707 8821003739420562122855851
708 9242222213089100236482468
709 9683246336473384692950141
710 10144993121360498349855117
711 10628421389339434018431539
712 11134533649012757233257266
713 11664378056211733359074989
714 12219050460829385752933591
715 12799696544040967549546618
716 13407514049842893300515442
717 14043755115009560896247309
718 14709728701742982621573015
719 15406803137473031686728640
720 16136408766456704733929960
721 16900040718023421615139722
722 17699261796520363728305767
723 18535705498227538260643937
724 19411079160737008625984792
725 20327167250524926225104243
726 21285834794689026478763279
727 22289030963078519665766063
728 23338792807308237260914421
729 24437249163424928041907597
730 25586624725281193731408873
731 26789244295972187975345577
732 28047537225002371833050265
733 29364042039174840401410081
734 30741411275534545837455418
735 32182416525049701669493501
736 33689953696083344104425480
737 35267048507090053257814699
738 36916862218371831466390947
739 38642697613142752962635377
740 40448005238584920958025801
741 42336389918029204882394844
742 44311617545863920840369598
743 46377622177263830141736603
744 48538513425341363876559745
745 50798584178852667747222617
746 53162318654143765382885988
747 55634400795597760680529925
748 58219723039443476801094308
749 60923395456410234757191329
750 63750755289363621730521399
751 66707376902734142467277039
752 69799082161255682016555972
753 73031951256264875549196905
754 76412333998576967290381041
755 79946861597749778813446875
756 83642458948376280759060397
757 87506357444909306244578521
758 91546108347420546205552204
759 95769596721631570845497467
760 100185055977528728799927334
761 104801083031887947299089913
762 109626654121091316907483064
763 114671141291716582199328745
764 119944329597525030360359865
765 125456435032664599943588723
766 131218123232145220993381447
767 137240528971934419413918430
768 143535276502365126695416027
769 150114500749946566185439151
770 156990869424125258199319792
771 164177606067058907337511307
772 171688514086043606612575006
773 179538001809876908936994264
774 187741108612148472242696048
775 196313532146228877574130425
776 205271656738578653367936021
777 214632582988926429986388665
778 224414158627870527559264672
779 234635010684545297402906467
780 245314579019165469061976296
781 256473151277522006793580371
782 268131899326855089910452325
783 280312917234977481216065103
784 293039260857068561911907814
785 306334989097209664731433877
786 320225206914489163068234756
787 334736110146375368345214600
788 349895032225041114570272620
789 365730492865430609395510833
790 382272248807091528499710175
791 399551346695158436678189672
792 417600178189372645504792024
793 436452537393663978864290774
794 456143680702607240293649230
795 476710389165006309097301365
796 498191033468957813539428151
797 520625641657010553919197933
798 544055969684472840375192518
799 568525574938534490706061669
800 594079892840670488630630592
801 620766316659786598575549879
802 648634280668761222350989497
803 677735346782440416646830314
804 708123294820762531656886802
805 739854216546533965767334038
806 772986613633456977887076800
807 807581499726333626728624861
808 843702506761946344696479318
809 881415995725955406072040092
810 920791172028267009897307090
811 961900205686723666182530301
812 1004818356516662266811029179
813 1049624104531886295592001365
814 1096399285770919193105082689
815 1145229233771058517525671547
816 1196202926921748299564672695
817 1249413141938143451197246711
818 1304956613705469351476791778
819 1362934201754896445210009772
820 1423451063642169064712143189
821 1486616835511165521431987194
822 1552545820135939227353425808
823 1621357182746615244121196099
824 1693175154956810925987560539
825 1768129247123031613334704697
826 1846354469479781748219381725
827 1927991562407948158757135899
828 2013187236208376200176785513
829 2102094420767492345475509203
830 2194872525517350908431176581
831 2291687710108620936220868710
832 2392713166231805895264675832
833 2498129411039428479247861631
834 2608124592640041540111014811
835 2722894808153770621116331300
836 2842644434838681724390055262
837 2967586474817628715909817295
838 3097942913956398210481999752
839 3233945095465967089805659849
840 3375834108824551390117839674
841 3523861194638888794503353323
842 3678288166088895306725822400
843 3839387847625506137491839436
844 4007444531618189055750537325
845 4182754453676344539572449167
846 4365626287397621594148265401
847 4556381659326123228718871406
848 4755355684934595045988558048
849 4962897526477029616902960948
850 5179370973591725441692342022
851 5405155047569761280593311309
852 5640644630240135289939687662
853 5886251118460526470664228841
854 6142403105241818180715969303
855 6409547088575236722590356768
856 6688148209073261294231180166
857 6978691017579416127621367189
858 7281680273947725007438365882
859 7597641778240058547761736536
860 7927123235638904094317778038
861 8270695156424308002639873895
862 8628951792416954101928264108
863 9002512111344626966080753311
864 9392020810646743658775357043
865 9798149372291305387533955163
866 10221597160240606598826411603
867 10663092562266432322303476705
868 11123394177882367233827112116
869 11603292054230327640921663461
870 12103608971830609706649041331
871 12625201782179726771511507423
872 13168962799258192544391759927
873 13735821247091306187954211330
874 14326744765590025077248496720
875 14942740976986290752471622113
876 15584859115267827313311378143
877 16254191721111587873092324896
878 16951876404912817201442928751
879 17679097680608265855615259246
880 18437088873097576657554477795
881 19227134102176417435110723972
882 20050570346008709235244170077
883 20908789587283457262531765992
884 21803241045324399141617642125
885 22735433497548114542005849998
886 23706937693798571004641546819
887 24719388867223498948083289869
888 25774489345500687252809378804
889 26874011266370469687432323064
890 28019799401584539392805764085
891 29213774093540999091111171498
892 30457934309041452094534393227
893 31754360814778195349163294784
894 33105219479338431121187479551
895 34512764706698117939813964633
896 35979343006370892775381258351
897 37507396705577683524270069466
898 39099467809010472061915760958
899 40758202011979452138815530840
900 42486352872956852713670309809
901 44286786151763276562821072324
902 46162484319883858339685597021
903 48116551249652209828113081111
904 50152217089300339495323999572
905 52272843331142868020684562930
906 54481928080444284021262070472
907 56783111532809081303905396336
908 59180181668236791563433127921
909 61677080170297590301897361159
910 64277908579209740047528081239
911 66986934687938090844143613355
912 69808599190783647160047126348
913 72747522594298313675975515518
914 75808512400736848471421136916
915 78996570574650297991229280416
916 82316901303632299988398474329
917 85774919064652174340290422161
918 89376257007847253685973294868
919 93126775670102033953588646379
920 97032572031214068788745504831
921 101099988925936734257871758113
922 105335624825697717249340297566
923 109746344004320023516548484639
924 114339287102620175519343378682
925 119121882107326818681605774853
926 124101855760352947243228079799
927 129287245415067195696280449510
928 134686411356844946322320680300
929 140308049605839235425397618534
930 146161205220595489810113264539
931 152255286121843912828670962378
932 158600077456539821649041064632
933 165205756522986405048540888502
934 172082908278667251069414691171
935 179242541453238650934197259796
936 186696105289985223331533467920
937 194455506939927965533912681729
938 202533129533692610598865658813
939 210941850957199382284203170807
940 219695063358224165318044322034
941 228806693411907068853541875681
942 238291223374348724060604467091
943 248163712954538841539822805011
944 258439822036007030979150903268
945 269135834280774178205316739464
946 280268681649415363012248190470
947 291855969872324021879876154295
948 303916004908593509522846115129
949 316467820430308150436031549378
950 329531206371463118459748993093
951 343126738582212927343310818251
952 357275809630683915409813877862
953 372000660796178890837726003298
954 387324415299254172522642132267
955 403271112815862792953691628810
956 419865745324534880986597379108
957 437134294337409552594144220787
958 455103769567844430124697223263
959 473802249089311696548335353466
960 493258921042345972782275520754
961 513504126948441979766309691779
962 534569406692011706303264990901
963 556487545233804543595012215720
964 579292621121572567283225785913
965 603020056866229955346449933929
966 627706671254313645315666822613
967 653390733670205093029430690862
968 680112020504323853942427406739
969 707911873726356247838164705290
970 736833261705540298719054192749
971 766920842363095307310373002456
972 798221028745064796074559883878
973 830782057107139291235727332496
974 864654057606444746780781784241
975 899889127698827799132442534714
976 936541408343845054684333375199
977 974667163123475006892945228417
978 1014324860384522877001791582270
979 1055575258518785771234463056212
980 1098481494499293328829162629399
981 1143109175795342970398447666072
982 1189526475793614611664954090617
983 1237804232857383153536135292833
984 1288016053160754275860296484714
985 1340238417439936346805112842875
986 1394550791808835135683575624448
987 1451035742791725240601989295616
988 1509779056731419711420354689871
989 1570869863737234511130053394548
990 1634400766343134721700316189015
991 1700467973052762538549522578952
992 1769171436954591163314939815205
993 1840614999597232037031555457738
994 1914906540321954092023759393569
995 1992158131256761785384875298220
996 2072486198183932873157332548416
997 2156011687500746785353420504212
998 2242860239501250002315540687801
999 2333162368215316300617623091729
1000 2427053648049977785612976687912