0 1
1 0
2 0
3 0
4 0
5 1
6 0
7 3
8 2
9 5
10 5
11 13
12 7
13 23
14 21
15 33
16 35
17 65
18 55
19 104
20 97
21 151
22 166
23 252
24 235
25 377
26 399
27 549
28 591
29 846
30 858
31 1237
32 1311
33 1749
34 1934
35 2556
36 2705
37 3659
38 3991
39 5090
40 5608
41 7244
42 7841
43 10086
44 11075
45 13794
46 15420
47 19195
48 21003
49 26240
50 29089
51 35483
52 39606
53 48341
54 53458
55 65073
56 72405
57 86943
58 97346
59 116599
60 129352
61 155037
62 173045
63 204680
64 229093
65 270845
66 301768
67 356168
68 397667
69 465605
70 521164
71 609236
72 679036
73 792905
74 885832
75 1027046
76 1148800
77 1330718
78 1484240
79 1716485
80 1915920
81 2205390
82 2464588
83 2832213
84 3156789
85 3623460
86 4042429
87 4620990
88 5156321
89 5887815
90 6558008
91 7478097
92 8331307
93 9470763
94 10553983
95 11981308
96 13329773
97 15116625
98 16819819
99 19023323
100 21163787
101 23911833
102 26569642
103 29983570
104 33310417
105 37511253
106 41669036
107 46873052
108 52005816
109 58443395
110 64830480
111 72721477
112 80644359
113 90374471
114 100125181
115 112092778
116 124145920
117 138775711
118 153648845
119 171594279
120 189811325
121 211798448
122 234206392
123 260979988
124 288475145
125 321185271
126 354749532
127 394641602
128 435701768
129 484140093
130 534299828
131 593224103
132 654206313
133 725798226
134 800087661
135 886717605
136 977055521
137 1082063335
138 1191518933
139 1318608063
140 1451357933
141 1604705512
142 1765516142
143 1950689317
144 2144833011
145 2368199840
146 2602801805
147 2871471465
148 3154543848
149 3477935702
150 3818610767
151 4207389268
152 4617523533
153 5083843421
154 5577046917
155 6136503207
156 6728173736
157 7398721009
158 8108681867
159 8910668161
160 9761543513
161 10720907947
162 11738707037
163 12885091292
164 14102437695
165 15469930271
166 16924516067
167 18555597522
168 20290473232
169 22234192286
170 24303137944
171 26615657685
172 29080477029
173 31831360281
174 34763334010
175 38032609178
176 41519207496
177 45399258682
178 49541666349
179 54145147464
180 59059714399
181 64517020844
182 70345860220
183 76806942734
184 83713860388
185 91360875924
186 99535257109
187 108578349621
188 118248587563
189 128930550799
190 140361112689
191 152973696558
192 166469465681
193 181350249105
194 197277522070
195 214815703263
196 233597393288
197 254258890938
198 276383884961
199 300706448426
200 326757160558
201 355362305736
202 386012658142
203 419638398160
204 455665654037
205 495165504421
206 537492583399
207 583850909688
208 633543028523
209 687925075810
210 746212854892
211 809963310411
212 878298712189
213 952969943048
214 1033030413279
215 1120449720212
216 1214169353691
217 1316446853817
218 1426100905911
219 1545668251688
220 1673880451202
221 1813592164173
222 1963389218839
223 2126535165503
224 2301460651496
225 2491833587992
226 2695974624204
227 2918007260050
228 3156070000985
229 3414871256892
230 3692352720827
231 3993802794669
232 4317032069892
233 4667986767381
234 5044250975455
235 5452599439080
236 5890378723292
237 6365199130192
238 6874253658315
239 7426094034767
240 8017644507333
241 8658637830304
242 9345714173825
243 10089800468692
244 10887376037034
245 11750719871901
246 12676000501020
247 13677167462009
248 14750073362276
249 15910382632695
250 17153792428419
251 18497896803877
252 19938062254439
253 21494256662488
254 23161514167859
255 24962246193755
256 26891387245270
257 28974109784574
258 31205026454857
259 33612666021330
260 36191347056163
261 38973093881058
262 41952240723157
263 45164741562446
264 48604701037036
265 52312830348607
266 56283055018770
267 60561056696535
268 65141028996509
269 70074261628264
270 75354920537265
271 81041014007488
272 87126807379392
273 93677394310976
274 100687748775553
275 108230927289947
276 116302311550680
277 124984463720097
278 134273378192482
279 144261676444055
280 154946844104763
281 166432833655194
282 178718296714106
283 191920593501836
284 206039935604839
285 221207980022371
286 237427704541585
287 254846824046930
288 273470824938674
289 293466367097441
290 314842057041437
291 337784811456891
292 362308099030791
293 388621622196932
294 416743539668775
295 446910244268347
296 479145622241079
297 513714784105765
298 550649757012957
299 590247890520905
300 632549456571787
301 677889455626713
302 726317986910023
303 778210654703970
304 833630872642297
305 892999874861766
306 956394869237824
307 1024290073577188
308 1096779017279832
309 1174393356052250
310 1257247808652643
311 1345938462976580
312 1440602499455703
313 1541910618134445
314 1650026263099392
315 1765701176546027
316 1889132064332739
317 2021161648846960
318 2162022267237579
319 2312661517970415
320 2473353229185795
321 2645159365975575
322 2828405070704989
323 3024280507622715
324 3233166485297916
325 3456400591847478
326 3694427970141009
327 3948747243289408
328 4219881952410391
329 4509511336853730
330 4818244451942312
331 5147967440816275
332 5499387923251989
333 5874618737142756
334 6274485876830556
335 6701356127209039
336 7156185509269795
337 7641631120821199
338 8158798082947595
339 8710662028503006
340 9298505436412944
341 9925660851696551
342 10593606165642081
343 11306080644514424
344 12064785826847628
345 12873908280250634
346 13735412960103525
347 14653987127930850
348 15631887158280006
349 16674369895761718
350 17784024003741373
351 18966733390119123
352 20225475528914372
353 21566836260248343
354 22994223955249980
355 24515020866831244
356 26133125854373830
357 27856799513736834
358 29690510637434686
359 31643502237601239
360 33720876248616239
361 35932988587346052
362 38285659896455604
363 40790474400964904
364 43454083930448022
365 46289446419742855
366 49304137831306783
367 52512668913117107
368 55923663084539704
369 59553347224891421
370 63411549985923184
371 67516416056772819
372 71879115975789504
373 76519959269162234
374 81451634175644832
375 86696843984978836
376 92270016935939004
377 98196530900171914
378 104492751978505636
379 111187071763659424
380 118298045236582701
381 125857399466945298
382 133886189359727231
383 142419866120127204
384 151482271000270867
385 161113046413657906
386 171339175252322726
387 182204940167377603
388 193740901951860854
389 205996522924627448
390 219006351639036144
391 232825670799823529
392 247493519985120011
393 263071629764373920
394 279604139366351808
395 297159972076435970
396 315788952682067064
397 335568078178429324
398 356553566746486409
399 378831361175060990
400 402464922981029945
401 427550170912900394
402 454158640337954517
403 482397433144580630
404 512347154309961535
405 544127301345547595
406 577828730315400058
407 613584753381907492
408 651497653193478949
409 691716213416390785
410 734355535852513405
411 779581553758663637
412 827523831098286998
413 878367406790386392
414 932257960089707545
415 989401902630541513
416 1049962975437436004
417 1114171285349446719
418 1182210910818020107
419 1254338341449702660
420 1330760313799544733
421 1411762804861338701
422 1497577917293775528
423 1588524317326723175
424 1684862625445883326
425 1786947889983707477
426 1895072489933198644
427 2009632096492377266
428 2130954610862438756
429 2259480739965404550
430 2395578256738952250
431 2539737963415758155
432 2692372022338148980
433 2854027125175882723
434 3025165034550714186
435 3206394392953124783
436 3398232562451721226
437 3601357066873459182
438 3816347137826450678
439 4043957079595838142
440 4284835198471273685
441 4539820899454015316
442 4809639813007075763
443 5095225913624145885
444 5397390843666612844
445 5717173913815267669
446 6055482707612510864
447 6413473260407565273
448 6792160430433306847
449 7192829908261212045
450 7616615818956868125
451 8064948153774443008
452 8539093969418211131
453 9040643131783166591
454 9571011158778002859
455 10131965407441838426
456 10725086381639411207
457 11352338842462757594
458 12015487029554753139
459 12716714353411781094
460 13457990044142708571
461 14241740144649007893
462 15070161573359356087
463 15945950029006991815
464 16871555809498049087
465 17849973219987441105
466 18883934958383471056
467 19976766518637444063
468 21131514121129290062
469 22351871098588553151
470 23641232302272852210
471 25003698266211442685
472 26443052047554075494
473 27963845606040460748
474 29570292760866872111
475 31267446514105665864
476 33059999353907560047
477 34953558782733115241
478 36953349806105109830
479 39065594339896430772
480 41296107995995285370
481 43651794219765088534
482 46139124445818694540
483 48765756101663189995
484 51538889620340643063
485 54467017493457598647
486 57558148247263660642
487 60821700073971137734
488 64266578238992858972
489 67903224715623212379
490 71741540743167872106
491 75793101612177583715
492 80068912052395249670
493 84581802954613849091
494 89344002774472216974
495 94369730524518399110
496 99672572778955590707
497 105268284484494084561
498 111171956156299849363
499 117401043396402560061
500 123972303495105366772
501 130905071545628510267
502 138217953274256596722
503 145932362395147023938
504 154068950527620780832
505 162651431661821901399
506 171702723399087593719
507 181249080919943015483
508 191315933023327670521
509 201932344037016883438
510 213126520780321105278
511 224930634546470587387
512 237375967208121223384
513 250498121156465747885
514 264331783736383606929
515 278916348435511208816
516 294290268059792385551
517 310497126908187619306
518 327579543383692533824
519 345585727981072480499
520 364562909309030612700
521 384564407142190991697
522 405642545060064453302
523 427856287811379791592
524 451263592189808387990
525 475929651993852198770
526 501918654488559159167
527 529302669797260079212
528 558152767445995068251
529 588548611009620089846
530 620568875036139637325
531 654301598884504814707
532 689833863339420143982
533 727262949771042685288
534 766685220022426395981
535 808208156129593560142
536 851938370139861104978
537 897994591315807621138
538 946494755013542398073
539 997569995296583612658
540 1051350743252848638498
541 1107981817802557304376
542 1167607443168157663776
543 1230387521084056581923
544 1296481504227366536282
545 1366065922183620318884
546 1439317024750574834000
547 1516429676254136989153
548 1597598658021672329135
549 1683039034125881084209
550 1772966034291709200444
551 1867616981666234181488
552 1967229650183549503514
553 2072065895466055217392
554 2182388350694506948305
555 2298485888528227074235
556 2420648557962654632102
557 2549194990194034717037
558 2684445445755879842864
559 2826751338338824035296
560 2976466225826569004270
561 3133977610238474363265
562 3299675751594856379440
563 3473987884993292791719
564 3657344696789055657477
565 3850217172768698237905
566 4053080532781485032262
567 4266453905899390635420
568 4490861573965079654201
569 4726875649147836206326
570 4975074428932304995689
571 5236088339529739680057
572 5510555153347374215196
573 5799169440125288298358
574 6102634461876125550082
575 6421715350230450271928
576 6757187436901147878273
577 7109893480804759149084
578 7480688129667815951259
579 7870499495975650394079
580 8280269521845436131787
581 8711020175039688004741
582 9163789420254855703969
583 9639702433021305324758
584 10139902806487995331002
585 10665629151887898086799
586 11218141259791554120828
587 11798802424258299911289
588 12409000195679924486686
589 13050234916654380845862
590 13724034613928320420084
591 14432050201078378780736
592 15175964164443721101883
593 15957592850320020579023
594 16778788500850656323193
595 17641549224936024366891
596 18547913833835522221157
597 19500080056101032463913
598 20500291748596196785770
599 21550965873589515291972
600 22654571543645753998562
601 23813766495142054370116
602 25031267297365531613886
603 26309996012972003444182
604 27652941051783426431614
605 29063314659023949378681
606 30544403752897595066699
607 32099739141056397749811
608 33732935529316568229303
609 35447873315495329345599
610 37248527132519875382221
611 39139161013029476795410
612 41124144662825221029243
613 43208163098456853493379
614 45396019664377792015613
615 47692861188440695399821
616 50103966965370635638995
617 52634990409945014021494
618 55291733028027583477560
619 58080403917652128003482
620 61007377532920716244309
621 64079472316399472680414
622 67303691306120689037952
623 70687521110131112474676
624 74238654168909780193091
625 77965309723183572122915
626 81875936284738883035465
627 85979556174847100379521
628 90285447047245428387446
629 94803511490326281874750
630 99543936160360008810104
631 104517588467957327832944
632 109735651573464497055433
633 115210050092819950079488
634 120953059547078884350548
635 126977762929927523913842
636 133297632866099309061145
637 139927021509273676126358
638 146880713297247036474098
639 154174450555784334093014
640 161824455141445671009702
641 169847992020114299022854
642 178262857684621900539821
643 187087984726041035160536
644 196342894480758184423097
645 206048345505903314562026
646 216225748381224282980256
647 226897860883893486782646
648 238088162394605404225878
649 249821599456595946577893
650 262123916718262359194848
651 275022456446546628627952
652 288545443495751159886678
653 302722842213225510799387
654 317585592355526160925663
655 333166527887303921084821
656 349499560157183426003927
657 366620662961435299560666
658 384566999942249162144374
659 403377980146618413887892
660 423094325940578283774441
661 443759204554711769967819
662 465417232082068983767734
663 488115686365717807557165
664 511903443417143423553474
665 536832276843054924356323
666 562955722223567102409836
667 590330469781048077867849
668 619015151404137572106121
669 649071833111167586465663
670 680564720302810521017429
671 713561756407838476896060
672 748133241010588391381932
673 784353542851820676716397
674 822299624462337857381555
675 862052877539097472222340
676 903697548775581230115494
677 947322705453253462701447
678 993020556045535235482562
679 1040888555994115341303439
680 1091027615472571681330358
681 1143544355153549622969677
682 1198549194753109880015114
683 1256158768414668820290472
684 1316493886349596868236816
685 1379682121987436492398215
686 1445855637615303076275713
687 1515153955288140622756898
688 1587721638826948560923234
689 1663711260293620355669608
690 1743280929159621484984955
691 1826597469158033155858147
692 1913833783780184321087308
693 2005172258160249911157022
694 2100801951756460147770354
695 2200922239748312360147982
696 2305739821947362680980512
697 2415472621751688713558797
698 2530346598373521366678134
699 2650599921265064060828978
700 2776479574754345859665607
701 2908245825686558229956850
702 3046168607417555459965845
703 3190532302660828251153263
704 3341631891501290587897294
705 3499778071326199101608418
706 3665293155858275812262134
707 3838516553920195610129720
708 4019800403985439521932582
709 4209515438556617130822661
710 4408046336033667848209871
711 4615797997435401105734035
712 4833190600140781356890980
713 5060666313588976823404486
714 5298684036501672559250080
715 5547726584186395772355107
716 5808295087702789496816282
717 6080916685401265507671944
718 6366138565710428708280185
719 6664536195538375712813252
720 6976706984925951374098284
721 7303279092033595799862778
722 7644904684206082176191210
723 8002269359395759490719714
724 8376084981976731165315808
725 8767099760539983562903762
726 9176090632761286730653483
727 9603874047950085988939176
728 10051297870976322864788650
729 10519252918210730290421548
730 11008664354942324735853503
731 11520504033604159155022602
732 12055781354431497977924869
733 12615556464873548193898006
734 13200930548203294079877465
735 13813059943494037595942984
736 14453145832116718317021659
737 15122449338103844987221959
738 15822280576987520443097355
739 16554014808282698624242422
740 17319080805281576693098651
741 18118978132113612708137827
742 18955264799220072557241648
743 19829575738202581830086380
744 20743609701360057121094776
745 21699149021649754600768513
746 22698045707852000979313607
747 23742242578086538373916924
748 24833758509386297726115386
749 25974711034319177346568889
750 27167300696355826131672763
751 28413835215941466168785566
752 29716712895177170296194271
753 31078448461253214028564203
754 32501655472413790088881453
755 33989073948311265755816824
756 35543551720702767482311320
757 37168073980194936140548421
758 38865743505975098474129758
759 40639812260653641624542567
760 42493660443329542821199252
761 44430830266513379396025839
762 46455003766936693502085340
763 48570038922235143230578010
764 50779946143405749591019704
765 53088926891947353936371089
766 55501348789602032467947025
767 58021786899843106066099104
768 60654997379195626659158840
769 63405961615069129183910779
770 66279858330799014596858933
771 69282110775955808584416511
772 72418357211157358951384803
773 75694501351258270334041717
774 79116681142891927076401428
775 82691322694405384979197265
776 86425107245204060097455633
777 90325028821754623769187916
778 94398359314169602429098029
779 98652710103393001118243788
780 103095995145538191841864598
781 107736496855084799732855693
782 112582827081520187824494257
783 117643997540663804611805524
784 122929378587606719971067538
785 128448774495881098575004457
786 134212379913578048687495400
787 140230860337384467248870294
788 146515306120639374822207601
789 153077318498738915061725820
790 159928961040841090856577015
791 167082851593220589219327019
792 174552111046967366883013384
793 182350461622058910311660292
794 190492172802723422762726815
795 198992166397439288038593632
796 207865959520974314273697366
797 217129776878585334266309498
798 226800490651717957021151916
799 236895740521644787585490438
800 247433870292538800964180551
801 258434056185800871685137257
802 269916240066608854523748022
803 281901266557245117819383225
804 294410812708533112817517222
805 307467534560088499861785760
806 321094993071751221165692476
807 335317810779449889626879584
808 350161593840439206534779584
809 365653099455365909049283997
810 381820153853331320305246582
811 398691831245702733881350755
812 416298367547744797520730412
813 434671351656235240195294479
814 453843634750433491927374060
815 473849534713843004253643266
816 494724740826519315583739034
817 516506532264338305600717468
818 539233677961964188623653998
819 562946670157050942320411664
820 587687619258370580499672252
821 613500503438417632529641266
822 640431058307065750520647487
823 668527043690959806783110338
824 697838127877241605199058326
825 728416172761354412105310762
826 760315112491263468593210204
827 793591258211466720488238140
828 828303170900999963832990853
829 864511987102216773146882550
830 902281285706566259626545461
831 941677436111857888226714136
832 982769458789078717559794310
833 1025629397370362149222410141
834 1070332172789746057987988388
835 1116955980996181094742888679
836 1165582140418982599062318717
837 1216295517069894353938067041
838 1269184365179039630929170436
839 1324340781524502080053409669
840 1381860539041803166033284751
841 1441843572448689722421482134
842 1504393804586139192295003701
843 1569619665494406274902398636
844 1637633911358345761443339379
845 1708554179284685717074152590
846 1782502798679418136920445018
847 1859607384250515603276147794
848 1940000639598516020246700134
849 2023820991080105342739181567
850 2111212383531227780472606239
851 2202324957745826832836064332
852 2297314838205149628349674697
853 2396344857253618597719203981
854 2499584334660359658957889479
855 2607209851714546268271013654
856 2719405022612668924174776987
857 2836361321845118332242909263
858 2958277847357329818693837274
859 3085362204991898864633408223
860 3217830263325507381088583288
861 3355907099106946102283996264
862 3499826743874221746998090864
863 3649833194517167442817525137
864 3806180151737055280753050183
865 3969132100332172235129663896
866 4138964039519183671573469814
867 4315962637761479926635944277
868 4500425955217759651345208346
869 4692664678168941483452967733
870 4893001833822990816874257684
871 5101774109959573606255513615
872 5319331562284615346278996789
873 5546039025188875546213313826
874 5782275812144550500630660879
875 6028437223770282182936332699
876 6284934241736648641059064240
877 6552195141005320261356890072
878 6830665177686077935481876972
879 7120808312665052327726569828
880 7423106894220417266795659796
881 7738063500625050086756066879
882 8066200618318412495157410641
883 8408062611879951931880597659
884 8764215398549452128627211971
885 9135248554400862374446200773
886 9521774986447311561115906088
887 9924433184308801707242169103
888 10343886891153428149791366979
889 10780827511125837385525287717
890 11235973780397302640476155081
891 11710074341163584469722889291
892 12203907414619566070628271688
893 12718283552913518650597875554
894 13254045315911489130775405173
895 13812070213665850480793344970
896 14393270388895002932193437702
897 14998595763198910685914514553
898 15629033727843072319786296408
899 16285612507676008992993315378
900 16969400862905465659951496543
901 17681511686080476303114608226
902 18423101717660806125202779907
903 19195375392267810070739940257
904 19999584571661689958312190239
905 20837032657364398028664930566
906 21709074344824098092747794644
907 22617120021208931747003904552
908 23562635544725234319968815183
909 24547146947427474579517799299
910 25572240244653285639561249794
911 26639566463815107146412592977
912 27750841489171167170461261367
913 28907851439605958572257044440
914 30112452554240938477702060778
915 31366576943513445853943562936
916 32672232522355488577797801780
917 34031509160272776816068329381
918 35446578669195246756076866423
919 36919701380720493092566709178
920 38453226196156871958715848821
921 40049597620712656767370884108
922 41711355884755939476213307835
923 43441144466462008965636386644
924 45241710293850217080884871362
925 47115911790371749676359139765
926 49066719167872810433349266402
927 51097223031614013043326333426
928 53210634776159810003481164550
929 55410295788468763332106233763
930 57699677959452574105888011284
931 60082393527363385130599181211
932 62562195718583784514301013175
933 65142989276028045914499830414
934 67828831245000399909864773854
935 70623942233993855554521881110
936 73532707362471676469634281510
937 76559688305779205274994363322
938 79709624422815467254093129118
939 82987445639863101421264932665
940 86398273778922195851805871324
941 89947436338567741097069767396
942 93640468045086682912892117190
943 97483125593711171130880502998
944 101481389446196773551550727263
945 105641479599605391974729769875
946 109969857657417245427772013138
947 114473243697133394504720188982
948 119158618643840572862585779941
949 124033242314238685810341945657
950 129104656123565502082872077627
951 134380702388393201048974272351
952 139869527402082080168758702437
953 145579602083759230339866895643
954 151519725459879184284897423525
955 157699046754469189883319819285
956 164127069316997998879408633091
957 170813674254832838427048819686
958 177769124852871704782763172739
959 185004091855432081015973962116
960 192529658426261451478065868101
961 200357347196366609704901207545
962 208499125816446129391986492848
963 216967435894419128060582785439
964 225775199198809694505666725250
965 234935848617490477610163719675
966 244463335074658414562206661968
967 254372160653568768128025261902
968 264677386294203527531867220825
969 275394667231728284361130018244
970 286540261549955925488073808654
971 298131068096848404496138591747
972 310184635974202237570751511012
973 322719205105167186797503377076
974 335753716746345963820542612897
975 349307856893368819204521201672
976 363402067911480615446320121484
977 378057594977051587450208213836
978 393296498929579061725862771558
979 409141705963578437851291429837
980 425617021812352245453036437655
981 442747184918363665171418543371
982 460557882071318772822626991384
983 479075805299747646032922463035
984 498328669094743091073763803362
985 518345271285574084136112206721
986 539155511989935807842330316164
987 560790458753277810651155583792
988 583282367381478729741096909793
989 606664751641609378817725412706
990 630972406144182191711812771255
991 656241480927481581743688590449
992 682509506568689368306848553944
993 709815473994699356928884418751
994 738199862020004713288124141119
995 767704722749164374090955092742
996 798373711753655541528713642711
997 830252179460809883789314200707
998 863387204197292020225949209261
999 897827689984950087238459317392
1000 933624402701530276086414004161