0 1
1 0
2 0
3 0
4 0
5 0
6 0
7 1
8 1
9 1
10 1
11 1
12 1
13 1
14 2
15 2
16 3
17 3
18 4
19 4
20 5
21 6
22 7
23 8
24 10
25 11
26 13
27 15
28 18
29 20
30 24
31 27
32 32
33 36
34 42
35 48
36 56
37 63
38 73
39 83
40 96
41 108
42 125
43 141
44 162
45 183
46 209
47 236
48 270
49 304
50 346
51 390
52 443
53 498
54 565
55 635
56 719
57 807
58 911
59 1022
60 1153
61 1291
62 1453
63 1628
64 1829
65 2045
66 2295
67 2564
68 2873
69 3207
70 3589
71 4002
72 4474
73 4983
74 5562
75 6192
76 6903
77 7677
78 8550
79 9500
80 10569
81 11733
82 13038
83 14462
84 16058
85 17795
86 19737
87 21858
88 24221
89 26799
90 29671
91 32805
92 36287
93 40090
94 44307
95 48914
96 54018
97 59588
98 65752
99 72484
100 79919
101 88036
102 96996
103 106775
104 117555
105 129322
106 142274
107 156411
108 171962
109 188923
110 207563
111 227897
112 250218
113 274555
114 301254
115 330356
116 362251
117 397011
118 435072
119 476541
120 521920
121 571333
122 625367
123 684198
124 748476
125 818431
126 894823
127 977927
128 1068615
129 1167243
130 1274797
131 1391728
132 1519173
133 1657668
134 1808524
135 1972417
136 2150825
137 2344572
138 2555378
139 2784219
140 3033073
141 3303124
142 3596630
143 3915026
144 4260912
145 4635975
146 5043219
147 5484682
148 5963775
149 6482927
150 7046091
151 7656115
152 8317547
153 9033774
154 9810002
155 10650240
156 11560488
157 12545432
158 13611988
159 14765694
160 16014457
161 17364781
162 18825791
163 20405075
164 22113125
165 23958841
166 25954248
167 28109764
168 30439231
169 32954741
170 35672232
171 38605832
172 41773787
173 45192550
174 48883125
175 52864591
176 57161066
177 61794736
178 66793253
179 72182369
180 77993852
181 84257470
182 91009716
183 98285096
184 106125393
185 114570533
186 123668492
187 133465347
188 144016108
189 155374017
190 167602063
191 180761696
192 194925133
193 210163113
194 226558399
195 244192539
196 263160194
197 283555241
198 305486116
199 329060711
200 354403114
201 381637387
202 410905393
203 442349678
204 476132491
205 512417347
206 551389758
207 593237381
208 638172055
209 686408936
210 738190098
211 793761935
212 853400863
213 917389100
214 986042027
215 1059682675
216 1138670937
217 1223376144
218 1314208826
219 1411591294
220 1515991425
221 1627891750
222 1747825629
223 1876343944
224 2014054343
225 2161585664
226 2319629777
227 2488904122
228 2670196402
229 2864324457
230 3072184768
231 3294709528
232 3532918310
233 3787873035
234 4060733262
235 4352707888
236 4665115025
237 4999330594
238 5356852190
239 5739245047
240 6148210376
241 6585527652
242 7053128655
243 7553035995
244 8087442065
245 8658644698
246 9269131676
247 9921512089
248 10618607721
249 11363380238
250 12159028855
251 13008914004
252 13916661921
253 14886083508
254 15921287531
255 17026594600
256 18206658062
257 19466374276
258 20811012188
259 22246118060
260 23777655549
261 25411905190
262 27155614288
263 29015892045
264 31000370271
265 33117092594
266 35374688305
267 37782255599
268 40349547680
269 43086851561
270 46005187862
271 49116183010
272 52432285292
273 55966630917
274 59733275645
275 63747056119
276 68023838602
277 72580373685
278 77434565439
279 82605319616
280 88112832478
281 93978434579
282 100224901532
283 106876290895
284 113958278429
285 121497989048
286 129524358191
287 138067958843
288 147161390516
289 156839100310
290 167137804244
291 178096302877
292 189755934686
293 202160389405
294 215356196860
295 229392535439
296 244321761771
297 260199215963
298 277083792473
299 295037745326
300 314127304297
301 334422478208
302 355997723344
303 378931746441
304 403308226012
305 429215619826
306 456747944770
307 486004586577
308 517091146328
309 550119255552
310 585207491452
311 622481202640
312 662073499856
313 704125091451
314 748785360079
315 796212211534
316 846573240307
317 900045599604
318 956817265045
319 1017086924893
320 1081065354723
321 1148975333926
322 1221053136596
323 1297548483392
324 1378726160191
325 1464866006908
326 1556264680292
327 1653235687284
328 1756111299383
329 1865242643491
330 1981001783566
331 2103781871653
332 2233999417227
333 2372094510115
334 2518533289045
335 2673808252521
336 2838440946481
337 3012982370080
338 3198015909157
339 3394157851965
340 3602060584389
341 3822413238166
342 4055945174764
343 4303426776498
344 4565673252560
345 4843545595513
346 5137954732786
347 5449862677032
348 5780287057934
349 6130302484592
350 6501045501749
351 6893716193506
352 7309583596020
353 7749987582213
354 8216344777539
355 8710150751806
356 9232986494373
357 9786520955207
358 10372518124682
359 10992839975217
360 11649454206877
361 12344437629570
362 13079984648908
363 13858411144921
364 14682163759458
365 15553824342147
366 16476120121197
367 17451928772640
368 18484289570794
369 19576409159156
370 20731673765716
371 21953655768062
372 23246127081247
373 24613066598909
374 26058674880902
375 27587382575085
376 29203866519676
377 30913059272073
378 32720166769980
379 34630679079617
380 36650389782041
381 38785408085084
382 41042180091850
383 43427502443489
384 45948545660064
385 48612869472973
386 51428448458190
387 54403689251500
388 57547458685322
389 60869103112754
390 64378479302166
391 68085976086308
392 72002548303672
393 76139741036051
394 80509726882605
395 85125333086017
396 90000082475118
397 95148223779036
398 100584776621152
399 106325565373120
400 112387268583274
401 118787456774553
402 125544646755088
403 132678343764667
404 140209101171563
405 148158567443968
406 156549551747937
407 165406076280314
408 174753448360588
409 184618318677359
410 195028760541710
411 206014334682625
412 217606176349246
413 229837067374443
414 242741531913601
415 256355916518868
416 270718495394788
417 285869559337112
418 301851531424681
419 318709065777296
420 336489174726498
421 355241338395138
422 375017644512063
423 395872909950244
424 417864834408050
425 441054135180414
426 465504716089368
427 491283816829378
428 518462198683658
429 547114309963357
430 577318490138256
431 609157153058588
432 642717011328118
433 678089279106984
434 715369918757429
435 754659865245619
436 796065297219810
437 839697885257357
438 885675089793917
439 934120435610246
440 985163839289184
441 1038941912627203
442 1095598322484400
443 1155284126092679
444 1218158166490900
445 1284387442922058
446 1354147545384632
447 1427623063674443
448 1505008064841590
449 1586506544815042
450 1672332952980122
451 1762712690619785
452 1857882687261457
453 1958091950648192
454 2063602199864825
455 2174688472038418
456 2291639817795932
457 2414759970311499
458 2544368109217382
459 2680799598221476
460 2824406824080148
461 2975560009654070
462 3134648135256189
463 3302079834570232
464 3478284406420721
465 3663712801774908
466 3858838734645144
467 4064159769220432
468 4280198539516200
469 4507503946445105
470 4746652496789109
471 4998249621035743
472 5262931143131463
473 5541364730997225
474 5834251509697769
475 6142327657560226
476 6466366176633957
477 6807178648666048
478 7165617177913823
479 7542576322630695
480 7938995226807439
481 8355859744183131
482 8794204777109905
483 9255116611811115
484 9739735484132975
485 10249258146608834
486 10784940682828312
487 11348101328655383
488 11940123559040612
489 12562459187969133
490 13216631753625360
491 13904239924016244
492 14626961208935825
493 15386555700592293
494 16184870143546972
495 17023842042542784
496 17905504124330627
497 18831988847992392
498 19805533295861980
499 20828484124755251
500 21903302926724214
501 23032571663340715
502 24218998540629528
503 25465423972552238
504 26774827018718250
505 28150331927332117
506 29595215188870669
507 31112912713571603
508 32707027558982218
509 34381337802275788
510 36139805005091805
511 37986582846335718
512 39926026393667243
513 41962701568692931
514 44101395300636682
515 46347125902563246
516 48705154189885247
517 51180994853294355
518 53780428632458909
519 56509514779403799
520 59374604385800861
521 62382354039277290
522 65539740411915058
523 68854075221119393
524 72333021196895159
525 75984608469357972
526 79817252042844284
527 83839769743429153
528 88061401339818645
529 92491828196170991
530 97141194192600852
531 102020127242074334
532 107139762176970716
533 112511764303435475
534 118148354435809464
535 124062334677294782
536 130267115800687263
537 136776745461631640
538 143605938141772291
539 150770106019719046
540 158285391712538034
541 166168702049639192
542 174437743870003456
543 183111060966643460
544 192208073219845472
545 201749117004207714
546 211755487963722198
547 222249485199368437
548 233254458019538886
549 244794854255121296
550 256896271348380884
551 269585509173827404
552 282890625861556327
553 296840995535806840
554 311467369304441138
555 326801938364352724
556 342878400626985821
557 359732029680186701
558 377399747562010803
559 395920200111957469
560 415333836451220417
561 435682991304215672
562 457011971792747190
563 479367147360732638
564 502797044544187219
565 527352445187974506
566 553086489912571247
567 580054785373295267
568 608315517208320242
569 637929567157720939
570 668960636347161939
571 701475373156057042
572 735543507767218895
573 771237991752626883
574 808635144901047796
575 847814807575776677
576 888860500922016858
577 931859593143537186
578 976903474289005822
579 1024087737696090437
580 1073512370660938401
581 1125281952408485556
582 1179505862064442170
583 1236298494629441795
584 1295779487797792229
585 1358073957543388563
586 1423312745464286417
587 1491632675729583034
588 1563176824776424148
589 1638094801519613785
590 1716543041387729411
591 1798685111864069488
592 1884692033021361317
593 1974742610643668684
594 2069023785608114589
595 2167730997032835498
596 2271068563059018128
597 2379250076683581057
598 2492498820716193304
599 2611048199186939149
600 2735142189494642223
601 2865035812530073386
602 3000995625293965156
603 3143300233149382542
604 3292240826471024052
605 3448121738736506843
606 3611261031077421996
607 3781991100239343814
608 3960659315239947931
609 4147628679576464997
610 4343278524558206105
611 4548005230518370687
612 4762222981782692845
613 4986364552051504861
614 5220882126393731446
615 5466248156410399382
616 5722956255105475001
617 5991522127924715443
618 6272484546858011544
619 6566406363969438357
620 6873875571631042274
621 7195506405727895831
622 7531940499513026934
623 7883848084286673543
624 8251929245003389896
625 8636915226890366003
626 9039569801632689111
627 9460690689119178165
628 9901111043783397318
629 10361701001449484057
630 10843369296223340269
631 11347064943258889676
632 11873778997478700354
633 12424546384002369829
634 13000447810932925945
635 13602611760186855222
636 14232216567621984549
637 14890492588088025043
638 15578724457297348031
639 16298253446086648586
640 17050479919649572418
641 17836865897269097590
642 18658937725852437454
643 19518288862766194109
644 20416582782044801243
645 21355555999449740776
646 22337021231270361253
647 23362870682340721042
648 24435079479030252798
649 25555709242695592562
650 26726911820275793929
651 27950933167547452295
652 29230117402704388858
653 30566911025831275746
654 31963867322978360265
655 33423650950482231018
656 34949042719352063044
657 36542944575465410639
658 38208384796575971653
659 39948523402008539602
660 41766657797300308059
661 43666228649826483979
662 45650826019010823200
663 47724195737354799900
664 49890246067314072158
665 52153054630494654908
666 54516875635715922600
667 56986147402694607507
668 59565500209518695665
669 62259764460992568645
670 65073979207750072898
671 68013401013600941148
672 71083513202846299181
673 74290035485470741829
674 77638933993911791177
675 81136431729817659872
676 84789019456589421569
677 88603467036696908726
678 92586835251796547428
679 96746488105295932965
680 101090105647779784027
681 105625697325679610053
682 110361615896148069795
683 115306571909355813233
684 120469648803886870592
685 125860318617387564252
686 131488458361049073322
687 137364367061124261034
688 143498783519159910594
689 149902904795318002178
690 156588405469776210437
691 163567457687887348074
692 170852752047629121572
693 178457519336472355526
694 186395553179982766416
695 194681233610897619856
696 203329551625033066473
697 212356134734549851844
698 221777273589259155879
699 231609949678468002174
700 241871864188671290004
701 252581468031773951335
702 263757993124093025347
703 275421484933231208677
704 287592836378365724851
705 300293823103692404396
706 313547140216232267776
707 327376440510661276886
708 341806374278426747445
709 356862630727020460891
710 372571981113160961616
711 388962323619274131017
712 406062730083970187143
713 423903494619773868106
714 442516184236237437632
715 461933691505931096312
716 482190289399406042206
717 503321688331260285689
718 525365095551932559678
719 548359276932434527048
720 572344621285778442730
721 597363207277863881154
722 623458873081371816676
723 650677288831491682857
724 679066032047519488024
725 708674666085780300360
726 739554821799148066588
727 771760282475846910942
728 805347072244856677499
729 840373548028486287704
730 876900495242352138462
731 914991227331922303730
732 954711689359701707258
733 996130565741582928589
734 1039319392361283112879
735 1084352673171580038225
736 1131308001527184132391
737 1180266186369056944297
738 1231311383522073503960
739 1284531232237908489680
740 1340016997263350722910
741 1397863716579040968537
742 1458170355108471158388
743 1521039964556503813621
744 1586579849698302197090
745 1654901741293423472653
746 1726121975968560101468
747 1800361683260498077779
748 1877746980187015800000
749 1958409173555557752128
750 2042484970403404132074
751 2130116696798988495749
752 2221452525425991472802
753 2316646712201350750545
754 2415859842378759148950
755 2519259086412104087111
756 2627018466062544942608
757 2739319131048950999856
758 2856349646759885355383
759 2978306293354231445637
760 3105393376805661051167
761 3237823552247709219749
762 3375818160214372167881
763 3519607576165123209933
764 3669431573931908111653
765 3825539703511792105790
766 3988191683888593816180
767 4157657811344836585538
768 4334219383996478642837
769 4518169143052501842803
770 4709811731584572728903
771 4909464171352929842831
772 5117456358530340816998
773 5334131578917969849587
774 5559847043555784237423
775 5794974445372903727040
776 6039900537845797741171
777 6295027736365467243869
778 6560774743351597109648
779 6837577197875072179866
780 7125888350902074419369
781 7426179766986266106561
782 7738942053603069701568
783 8064685619022882834812
784 8403941460003985256814
785 8757261980277967316586
786 9125221841201565434959
787 9508418845629798511747
788 9907474856484306661583
789 10323036751160381639753
790 10755777413353980087362
791 11206396763547872038689
792 11675622829853513311659
793 12164212860551045282468
794 12672954480147834793053
795 13202666890409367053661
796 13754202118315861024465
797 14328446312518649566131
798 14926321090392444595911
799 15548784937387228325774
800 16196834660929196603882
801 16871506900714374041753
802 17573879697808939745451
803 18305074124550757072699
804 19066255977842886686275
805 19858637537996255161605
806 20683479395902060628779
807 21542092350866454679917
808 22435839382091880276705
809 23366137696326665492472
810 24334460854886062526172
811 25342340982770093913854
812 26391371063316365622968
813 27483207321332769881148
814 28619571698400525633076
815 29802254423529078280162
816 31033116683124170413533
817 32314093393705495444334
818 33647196081626096879171
819 35034515873504467927311
820 36478226601933787368842
821 37980588030474969427162
822 39543949202833213195261
823 41170751920543188803584
824 42863534354422508622098
825 44624934794461504305815
826 46457695543795408718770
827 48364666961796153638989
828 50348811662344743171305
829 52413208872718840983541
830 54561058959601936538287
831 56795688128076482439636
832 59120553300585513922220
833 61539247182185543267646
834 64055503519588499457998
835 66673202560810944765220
836 69396376723479336579073
837 72229216479142629618488
838 75176076462232436327361
839 78241481811595585676428
840 81430134753874129350195
841 84746921437274623131046
842 88196919025683171598852
843 91785403062331690920453
844 95517855113703276128815
845 99399970703595913172323
846 103437667548817392718044
847 107637094107198270920894
848 112004638450238244355405
849 116546937471898158472103
850 121270886446757200447830
851 126183648949934970817956
852 131292667152968297765284
853 136605672508996588218475
854 142130696842486896366182
855 147876083857878103088584
856 153850501083492806306796
857 160062952266198746127988
858 166522790234367375352756
859 173239730245796244552387
860 180223863839429404988954
861 187485673208815772441852
862 195036046117520111827663
863 202886291375794845900016
864 211048154900208428430054
865 219533836377008620330329
866 228356006552505471239890
867 237527825172831766507312
868 247062959598070523429284
869 256975604114804069224419
870 267280499973903102781572
871 277992956179432885947673
872 289128871057456858818480
873 300704754632572408294166
874 312737751843063571997993
875 325245666624607872581711
876 338246986895679379558585
877 351760910476842998824996
878 365807371979503322448469
879 380407070698727419716818
880 395581499548301770207892
881 411352975075245855422647
882 427744668594727687013593
883 444780638485398547744893
884 462485863689079125188008
885 480886278457814520377251
886 500008808395433433107062
887 519881407839849614500382
888 540533098636675683331942
889 561994010353844236562053
890 584295421991489519927349
891 607469805240494650993432
892 631550869347906890833720
893 656573607646607600302251
894 682574345811673641958001
895 709590791905089543328084
896 737662088275786965447187
897 766828865381255382710398
898 797133297602567531865112
899 828619161123982562142986
900 861331893954187977408505
901 895318658165620660996288
902 930628404434521233297188
903 967311938963823352144504
904 1005421992877527637710843
905 1045013294174734737180860
906 1086142642338413478294165
907 1128868985693592451328883
908 1173253501616938838645719
909 1219359679699399022456016
910 1267253407971246939663382
911 1317003062298707133635805
912 1368679599069409921554985
913 1422356651283880261072624
914 1478110628178796166129647
915 1536020818507833668129241
916 1596169497614919641266876
917 1658642038434947167475301
918 1723527026566510175414292
919 1790916379561616094791916
920 1860905470587364758813944
921 1933593256615170014373363
922 2009082411303688923517828
923 2087479462742417192407017
924 2168894936234090067677664
925 2253443502295048033732643
926 2341244130064535069848595
927 2432420246315165914782244
928 2527099900269272864718519
929 2625415934427384272133017
930 2727506161628266612306274
931 2833513548561802815207673
932 2943586405969907707354322
933 3057878585772849482730182
934 3176549685373068190860090
935 3299765259391108156310318
936 3427697039103845329387224
937 3560523159858107282712617
938 3698428396749241172731934
939 3841604408857527713773608
940 3990249992352745050783830
941 4144571342780993482454576
942 4304782326866303972338596
943 4471104764163865995598534
944 4643768718921190395159320
945 4823012802508385145574954
946 5009084486799336069937743
947 5202240428891044228842918
948 5402746807570189659495692
949 5610879671942099660449556
950 5826925302660396259234045
951 6051180586202409827457085
952 6283953402659900119196243
953 6525563027522201682911321
954 6776340547954806930157980
955 7036629294084803093429846
956 7306785285832007667115690
957 7587177695833945514084428
958 7878189329041866926184723
959 8180217119575274074807239
960 8493672645453208668414566
961 8818982661831870661378000
962 9156589653410761064776053
963 9506952406681992638055930
964 9870546602731988745404936
965 10247865431318466657964611
966 10639420226982253937138543
967 11045741127968486006209203
968 11467377758770592209000689
969 11904899937126905603701821
970 12358898406340937137694533
971 12829985593814324477819615
972 13318796396725165364632581
973 13825988995804078009665102
974 14352245698206682971961530
975 14898273810502626349893944
976 15464806542850436649838344
977 16052603945450865527620256
978 16662453878423534498303988
979 17295173016277149640944835
980 17951607888198908565290009
981 18632635955416405913547308
982 19339166726944099515449559
983 20072142915056495472001513
984 20832541631892575904966472
985 21621375628628687699972376
986 22439694578723316339798600
987 23288586406772658906860591
988 24169178664586202000201457
989 25082639956130007332627230
990 26030181413060046408802342
991 27013058222609656312921867
992 28032571209674452995038737
993 29090068474983244791908626
994 30186947091327675794320451
995 31324654859872270686066891
996 32504692128655977667292717
997 33728613675449261921575471
998 34998030657225802079979345
999 36314612628565109016678029
1000 37680089631403320046359675