1 0
2 0
3 0
4 0
5 0
6 0
7 0
8 0
9 0
10 1
11 1
12 2
13 3
14 5
15 7
16 11
17 15
18 22
19 30
20 43
21 57
22 79
23 104
24 140
25 183
26 242
27 312
28 407
29 520
30 670
31 849
32 1081
33 1359
34 1715
35 2141
36 2678
37 3322
38 4125
39 5085
40 6274
41 7691
42 9430
43 11502
44 14025
45 17024
46 20655
47 24959
48 30140
49 36270
50 43612
51 52274
52 62604
53 74763
54 89200
55 106158
56 126213
57 149713
58 177413
59 209795
60 247838
61 292217
62 344193
63 404694
64 475355
65 557434
66 653036
67 763867
68 892633
69 1041615
70 1214305
71 1413722
72 1644349
73 1910193
74 2216985
75 2569992
76 2976556
77 3443556
78 3980368
79 4595960
80 5302273
81 6110927
82 7037132
83 8095882
84 9306485
85 10688256
86 12265647
87 14063419
88 16112532
89 18444610
90 21098749
91 24115254
92 27543387
93 31434351
94 35850145
95 40855613
96 46528609
97 52951092
98 60220641
99 68440535
100 77732922
101 88227613
102 100077194
103 113444528
104 128519865
105 145507032
106 164642913
107 186182022
108 210418777
109 237670410
110 268302214
111 302708739
112 341342573
113 384693478
114 433321230
115 487832741
116 548919249
117 617331411
118 693921621
119 779616650
120 875465960
121 982611942
122 1102344729
123 1236070106
124 1385371895
125 1551977192
126 1737827497
127 1945041487
128 2175995764
129 2433285315
130 2719815520
131 3038759993
132 3393665641
133 3788408347
134 4227312395
135 4715104544
136 5257050189
137 5858905782
138 6527074364
139 7268557185
140 8091130920
141 9003299497
142 10014496530
143 11135037859
144 12376353090
145 13750940620
146 15272631869
147 16956550798
148 18819416195
149 20879507080
150 23157009055
151 25673988705
152 28454789850
153 31526020616
154 34917007535
155 38659798629
156 42789684468
157 47345222776
158 52368835692
159 57906862280
160 64010244368
161 70734613287
162 78141078271
163 86296356940
164 95273680815
165 105152980726
166 116021928227
167 127976187545
168 141120614494
169 155569590835
170 171448403834
171 188893681714
172 208054982908
173 229095352870
174 252193156110
175 277542780981
176 305356750806
177 335866607647
178 369325347245
179 406008515950
180 446217020964
181 490278483762
182 538550482521
183 591422212765
184 649318230860
185 712700478811
186 782072608096
187 857982438842
188 941026952900
189 1031855269070
190 1131174411900
191 1239752895543
192 1358427390844
193 1488107030292
194 1629781111290
195 1784524253148
196 1953505300469
197 2137993481110
198 2339368698471
199 2559128868695
200 2798901815993
201 3060453996195
202 3345704247207
203 3656734135761
204 3995803853135
205 4365364466121
206 4768076288060
207 5206823359640
208 5684734682169
209 6205201300820
210 6771900845381
211 7388817654842
212 8060271133290
213 8790939423734
214 9585892170630
215 10450618325381
216 11391063996100
217 12413665066130
218 13525390908306
219 14733782603195
220 16047003420736
221 17473883540609
222 19023978338549
223 20707620660012
224 22535988096525
225 24521164024668
226 26676215244581
227 29015263174044
228 31553573424977
229 34307638764340
230 37295282430103
231 40535754714458
232 44049852098660
233 47860029585627
234 51990538038275
235 56467554720825
236 61319341567100
237 66576396756614
238 72271637052339
239 78440573648595
240 85121522176023
241 92355806553170
242 100188000769607
243 108666165023956
244 117842124008550
245 127771740235744
246 138515234230612
247 150137500682485
248 162708476721156
249 176303507352180
250 191003768898756
251 206896691106208
252 224076443846866
253 242644424368844
254 262709816504995
255 284390152763690
256 307811956622166
257 333111390536511
258 360434993402828
259 389940427172805
260 421797323263437
261 456188142274767
262 493309145099445
263 533371382284956
264 576601807811660
265 623244417012370
266 673561523492948
267 727835067191868
268 786368077812184
269 849486177621480
270 917539258024283
271 990903205183376
272 1069981820046613
273 1155208798794571
274 1247049930871830
275 1346005370702742
276 1452612153055115
277 1567446797558682
278 1691128186128544
279 1824320547566105
280 1967736747955400
281 2122141709121982
282 2288356169890946
283 2467260599610786
284 2659799496045280
285 2866985863553917
286 3089906122392286
287 3329725230615951
288 3587692289720128
289 3865146400141180
290 4163523059637916
291 4484360854459693
292 4829308759936644
293 5200133783158321
294 5598729289974835
295 6027123730702914
296 6487490134379059
297 6982156066687004
298 7513614451209550
299 8084534928728275
300 8697776186538802
301 9356398910931777
302 10063679829690316
303 10823126475108926
304 11638493172070350
305 12513797857782002
306 13453340278574890
307 14461721145197588
308 15543862836152590
309 16705031204193300
310 17950859123262404
311 19287371303335278
312 20721011062239155
313 22258668552931030
314 23907711191299815
315 25676015752839706
316 27572002943854895
317 29604673884054782
318 31783649371982253
319 34119211337340595
320 36622347422862768
321 39304798065912223
322 42179107099592046
323 45258675208418367
324 48557817342130305
325 52091823386406032
326 55877023284850898
327 59930855873897746
328 64271942723448907
329 68920166206781425
330 73896753199610845
331 79224363592912214
332 84927185135546742
333 91031033751996395
334 97563460977368180
335 104553867615234673
336 112033625397725187
337 120036205713564290
338 128597317332563457
339 137755052152855275
340 147550041061461184
341 158025618895578829
342 169228000771771861
343 181206468732546018
344 194013571169570940
345 207705333936969998
346 222341485823017959
347 237985697259678262
348 254705835166359812
349 272574232776156795
350 291667977589335016
351 312069216275154859
352 333865479937532905
353 357150028542968771
354 382022218221863920
355 408587890224653157
356 436959785566304258
357 467257984130895412
358 499610372621742218
359 534153140127300920
360 571031306073037168
361 610399279337912935
362 652421453725861989
363 697272838591546199
364 745139730269973925
365 796220423143682380
366 850725966499646620
367 908880966060253849
368 970924436890140998
369 1037110706633300940
370 1107710376383728289
371 1183011338235950494
372 1263319857477746090
373 1348961718588753158
374 1440283443728919965
375 1537653583027764064
376 1641464086149057939
377 1752131754622782276
378 1870099785286229347
379 1995839404545638985
380 2129851604751073651
381 2272668982660350276
382 2424857692327708940
383 2587019512707878243
384 2759794043456393465
385 2943861029589248118
386 3139942829739639020
387 3348807029113539067
388 3571269213262042872
389 3808195904285111935
390 4060507677101539463
391 4329182457996984081
392 4615259024751474071
393 4919840711251770579
394 5244099337721811645
395 5589279370278011819
396 5956702332957581812
397 6347771476849991261
398 6763976731695575698
399 7206899945643272210
400 7678220440969143886
401 8179720892664413267
402 8713293560378068862
403 9280946882014054693
404 9884812462421435160
405 10527152467066203474
406 11210367457374556975
407 11937004679445395749
408 12709766846403450295
409 13531521428147566535
410 14405310492710185812
411 15334361115318355588
412 16322096403717948131
413 17372147158498520274
414 18488364221770090220
415 19674831535925321076
416 20935879971116578704
417 22276101946569342990
418 23700366910179377289
419 25213837705339884315
420 26821987895861376194
421 28530620082243791290
422 30345885287236795475
423 32274303448808469242
424 34322785106258277990
425 36498654323064556620
426 38809672940806454708
427 41264066213901007547
428 43870549928985310948
429 46638359065595520635
430 49577278112441401453
431 52697673103685155251
432 56010525501074510321
433 59527467995038890981
434 63260822363343076140
435 67223639470159607719
436 71429741558216686897
437 75893766927804583481
438 80631217170816838257
439 85658507065832780300
440 90993017319543759831
441 96653150274203271785
442 102658388785303778312
443 109029358404444041696
444 115787893092451316745
445 122957104614795894375
446 130561455867386305542
447 138626838303847662696
448 147180653737783135624
449 156251900712394915810
450 165871265739014646064
451 176071219620646674025
452 186886119193033278093
453 198352314725797687363
454 210508263350344788565
455 223394648786548741979
456 237054507772625424123
457 251533363503043766050
458 266879366520503341578
459 283143443403376333810
460 300379453740587569904
461 318644355775994078254
462 337998381264950591771
463 358505219970351402948
464 380232214396802829530
465 403250565240507009577
466 427635548215277355157
467 453466742788158454679
468 480828273553236410710
469 509809064839207679375
470 540503109354512761985
471 573009751534568278229
472 607433986477905586242
473 643886775212313389235
474 682485377269379466135
475 723353701393500300121
476 766622675464802787706
477 812430636556321331292
478 860923742316357009187
479 912256404700919154535
480 966591747370165175402
481 1024102087889664378093
482 1084969446186069701835
483 1149386080526518018793
484 1217555052620986728260
485 1289690823259305899796
486 1366019880247104640632
487 1446781400210108359875
488 1532227946213088816419
489 1622626202937547392540
490 1718257751565158300993
491 1819419886304422610273
492 1926426474928893351290
493 2039608865478446107087
494 2159316841735984426315
495 2285919629867879310808
496 2419806959109559987145
497 2561390179146534844123
498 2711103437368824619065
499 2869404918938820312205
500 3036778153177428534216
501 3213733389528870427212
502 3400809046969257304422
503 3598573240473423913260
504 3807625388802156865075
505 4028597907615640291995
506 4262157992612719878611
507 4509009497134192908130
508 4769894909411709520628
509 5045597434378107773830
510 5336943185751752529243
511 5644803493838157755088
512 5970097335346355593703
513 6313793891245669226480
514 6676915239604557527120
515 7060539190080053424737
516 7465802267708921948623
517 7893902853378542752471
518 8346104489409864174299
519 8823739358413279310940
520 9328211944709916647543
521 9861002887342797853570
522 10423673034917296541081
523 11017867712247845068542
524 11645321210092683846895
525 12307861509003932218713
526 13007415249722035884756
527 13746012962299844413511
528 14525794567647948982299
529 15349015164962932099055
530 16218051120119459033191
531 17135406469894531230916
532 18103719658633390873634
533 19125770623775319192688
534 20204488248530400583045
535 21342958199832938133914
536 22544431171712275906294
537 23812331554087344520097
538 25150266549160024003030
539 26562035757484627210635
540 28051641258125759449601
541 29623298207262053034568
542 31281445982107915485942
543 33030759897020886527700
544 34876163521371183815520
545 36822841628803699202873
546 38876253810441977400097
547 41042148784704555240696
548 43326579439550885438064
549 45735918643172081694745
550 48276875862534910715822
551 50956514629473761605166
552 53782270897685271651435
553 56761972334367256666055
554 59903858594192462961940
555 63216602623809082171027
556 66709333049321826785784
557 70391657699838541615537
558 74273688324768360539940
559 78366066563335315755645
560 82679991229739961658982
561 87227246978345046733918
562 92020234418628448888989
563 97072001750776501253177
564 102396277998590183834540
565 108007507917716100180158
566 113920888663482224826122
567 120152408304192974372913
568 126718886272514674167347
569 133638015849420453471600
570 140928408782491829708989
571 148609642142506822052414
572 156702307530171392269443
573 165228062747312737425351
574 174209686055429780038110
575 183671133147325155623795
576 193637596966825355347721
577 204135570514833854375234
578 215192912790010492148600
579 226838918016064107659180
580 239104388318525801021377
581 252021710018070533044860
582 265624933719238785225480
583 279949858378173146083842
584 295034119545750344275235
585 310917281987877122186096
586 327640936898550508945194
587 345248803927363767121792
588 363786838258130382346215
589 383303342982146925107240
590 403849087025866188605617
591 425477428900450629140108
592 448244446558295609145367
593 472209073650251275610119
594 497433242496379439855410
595 523982034092761329346225
596 551923835497597339979825
597 581330504950668898067713
598 612277545102716643760073
599 644844284743387567372950
600 679114069440800361812259
601 715174461519277752115080
602 753117449828270975177150
603 793039669770546662220926
604 835042634086444609416345
605 879232974907764031904412
606 925722697626034192689255
607 974629447138552149224757
608 1026076787069444476738100
609 1080194492583704915642950
610 1137118857448944670365881
611 1196993016022564115038819
612 1259967280882005836659022
613 1326199496841226528499913
614 1395855412139921147765765
615 1469109067620266364368276
616 1546143204753093906996607
617 1627149693406668261281921
618 1712329980302464303618577
619 1801895559136934673022430
620 1896068463403914379471602
621 1995081782990563301045586
622 2099180205680232247719817
623 2208620584737909793054088
624 2323672533819644869615560
625 2444619050494023161293780
626 2571757169735228897449901
627 2705398648798748265756710
628 2845870684968443922525239
629 2993516667720566419932575
630 3148696966934709885912511
631 3311789758844381270966147
632 3483191891511659206278696
633 3663319791679467908195764
634 3852610414954813144678935
635 4051522241352377850422151
636 4260536318336418506966630
637 4480157353582625632414699
638 4710914859799646605301775
639 4953364354042095384602070
640 5208088614075237114441990
641 5475698994452865827328571
642 5756836805109496536359832
643 6052174755379400290931746
644 6362418466506844752761470
645 6688308055834340501641226
646 7030619796020836617361751
647 7390167852776317475717713
648 7767806104778878837164249
649 8164430049588075661850810
650 8580978799563719524127009
651 9018437171961462536036445
652 9477837877589037987868229
653 9960263812584982777600680
654 10466850458112858453218580
655 10998788392959211963718174
656 11557325924275010398406049
657 12143771841914384743544658
658 12759498302098099209554793
659 13405943846363891981534510
660 14084616562063446675434104
661 14797097390923021539760025
662 15545043592508522294211770
663 16330192369717692594743609
664 17154364663774298625772230
665 18019469126507961428672051
666 18927506278086435946068188
667 19880572858705273778676942
668 20880866383156612098061850
669 21930689907569023283929460
670 23032457018063779493107801
671 24188697051478066127401542
672 25402060558798923727471362
673 26675325022395060114800285
674 28011400838670237282355525
675 29413337578246961723124990
676 30884330536372881463697673
677 32427727586772767374178997
678 34047036352803867581042233
679 35745931710352472227135620
680 37528263637600156498487219
681 39398065427422281610643530
682 41359562278932555031702135
683 43417180285380512095747456
684 45575555836425887545977025
685 47839545453571172165120126
686 50214236078422392886897009
687 52704955834275532260079781
688 55317285282492632687920258
689 58057069196035352793431400
690 60930428873575048873441521
691 63943775018585366734890031
692 67103821208966686564965527
693 70417597983829312449301321
694 73892467575305718909602445
695 77536139314438450036725447
696 81356685741542453133917404
697 85362559452724451193484439
698 89562610715712361407693678
699 93966105889548701869156095
700 98582746684300811474206704
701 103422690298469162491513362
702 108496570473513553425858943
703 113815519506584255621894116
704 119391191264435421973251895
705 125235785243316477752864716
706 131362071721692313879979567
707 137783418054626000653142969
708 144513816160891969689412750
709 151567911256049512360375095
710 158961031887135286085235363
711 166709221326990195332498872
712 174829270388876277545839637
713 183338751724607807993046436
714 192256055672290763193221720
715 201600427722563884726397070
716 211392007675353970454103141
717 221651870562207853027965567
718 232402069412653853864542933
719 243665679946368013666327940
720 255466847276604983962285297
721 267830834713972490220078542
722 280784074763632408869278834
723 294354222412952916139896726
724 308570210810987287633405525
725 323462309445446823381357212
726 339062184927563252236843662
727 355402964499908837158046852
728 372519302387379330971303185
729 390447449116631866485901445
730 409225323934850865556691890
731 428892590464251967855613304
732 449490735734797038991717951
733 471063152743619187999778293
734 493655226696243034514031400
735 517314425091242576365546593
736 542090391817133238434494977
737 568035045437428909344637344
738 595202681847565355822880586
739 623650081495152510086776590
740 653436621363457572266617407
741 684624391926462833720614829
742 717278319293007362912093828
743 751466292766703060114052177
744 787259298058268320357594070
745 824731556396906795319563020
746 863960669798165861017088550
747 905027772756565376916776439
748 948017690643021312956096238
749 993019105098891165844234665
750 1040124726731207513487268782
751 1089431475426495684372348888
752 1141040668614401514831022309
753 1195058217826299793863067039
754 1251594833909066803991732350
755 1310766241269355067103889316
756 1372693401540003968630691305
757 1437502747076687749441484070
758 1505326424710588948761490876
759 1576302550200777979380474540
760 1650575473849174429679040591
761 1728296057760404066732906264
762 1809621965249695794142416209
763 1894717962923078080757389826
764 1983756235976737624566137580
765 2076916717285337194287346689
766 2174387430873614831199442256
767 2276364850390493548150783443
768 2383054273231539273920733534
769 2494670210982651178868609475
770 2611436796886735244162913671
771 2733588211064478260612805184
772 2861369124251653484352005096
773 2995035160847270914681059579
774 3134853382100851351144864940
775 3281102790301712216506863681
776 3434074854869993218310671406
777 3594074061286715041328826995
778 3761418483840118271287331919
779 3936440383206299305419118640
780 4119486829925487734901225397
781 4310920354879552309502404206
782 4511119627923305220158608990
783 4720480165870180920821705191
784 4939415071083807515637809590
785 5168355801979073826335686061
786 5407752976791525504718621406
787 5658077212030427885197556631
788 5919819997090708236018692412
789 6193494606560282271268760645
790 6479637051824174917066003363
791 6778807073633324291404125876
792 7091589177376310153752529852
793 7418593712864345400996461564
794 7760458000516119732105011660
795 8117847505907267214610136353
796 8491457064731866197741385909
797 8882012160308153045469191429
798 9290270255850181756445806521
799 9717022183819071379432547745
800 10163093594764518321429087963
801 10629346468166888285747539663
802 11116680687895339524173960885
803 11626035685005433681730519434
804 12158392150713596560018771510
805 12714773822502853867437610539
806 13296249346437663712803945652
807 13903934218892535894798060671
808 14538992811032795445930194343
809 15202640479523329856502531795
810 15896145767085940825885999942
811 16620832696674890712563259200
812 17378083163197040857254470372
813 18169339426864380132635804972
814 18996106712436559938473865895
815 19859955918785905854144714144
816 20762526443401269764017750148
817 21705529126636496595747061114
818 22690749320708399958452667910
819 23720050088654300278074289360
820 24795375538674769287855917904
821 25918754299509421908414527918
822 27092303142727000635117238637
823 28318230758051625348183798836
824 29598841688099751159697460050
825 30936540429162940209535856208
826 32333835704945057084079142827
827 33793344920444622221409224821
828 35317798803469089836514412611
829 36910046241573259474053159390
830 38573059322534421074432133586
831 40309938586807491327520384867
832 42123918500750125269711331361
833 44018373159765709789561001899
834 45996822230887342258694281800
835 48062937144713298627130123229
836 50220547547010467855113892806
837 52473648020721499712932212941
838 54826405089550651196825850285
839 57283164514757037607511479615
840 59848458897259186524415493589
841 62527015597645751959699796180
842 65323764987201294613704482483
843 68243849043587241284258784821
844 71292630305374175071795328225
845 74475701200196312724308880918
846 77798893761900436659351064292
847 81268289752683259435283584924
848 84890231206861633568912326365
849 88671331413592522059651365365
850 92618486356563045080766292189
851 96738886629398300238472080633
852 101040029846295272301351795898
853 105529733568177821033120179391
854 110216148765490162878644001495
855 115107773839596986476438181242
856 120213469225647530996531856391
857 125542472600680869377594163522
858 131104414721710934163108520097
859 136909335919524468949176786365
860 142967703274964257258314771864
861 149290428505545339248856643620
862 155888886591375189940746614721
863 162774935170511357270234202196
864 169960934735104127394183260600
865 177459769660928436464904272954
866 185284870104221362540141813658
867 193450234801099819253447030053
868 201970454806251041255806863193
869 210860738209056474906508537685
870 220136935866841931848483315141
871 229815568196533357527612528825
872 239913853067653169173602949170
873 250449734841306503945908061783
874 261441914601595473043442018695
875 272909881627751954679788194564
876 284873946157211927710828473075
877 297355273491855790272931327629
878 310375919501726677623746236788
879 323958867582701052757913011220
880 338128067126840791019301273980
881 352908473566491790304688324877
882 368326090055629699043675639445
883 384408010854476443615439081099
884 401182466486041677522773429695
885 418678870735968441742022967415
886 436927869569903024881318628998
887 455961392045552207704778373625
888 475812703299658609558041457125
889 496516459693303271391004555060
890 518108766202256840575359636820
891 540627236142532889947502754597
892 564111053324873082624625220606
893 588601036735599779128269259920
894 614139707845132555758956164140
895 640771360649466222593250570801
896 668542134554075847701391638255
897 697500090214033832232093551986
898 727695288448623128323501941799
899 759179872353393627545509550155
900 792008152737464870150394198157
901 826236697018911469842570406520
902 861924421716308797787947751937
903 899132688679949012942189772749
904 937925405211893810207519130815
905 978369128229893328094308488107
906 1020533172636304508490843756665
907 1064489724059469433955848242821
908 1110313956141600515149763134998
909 1158084152554047023364764068055
910 1207881833927923924934508563587
911 1259791889895451000929799661997
912 1313902716445017323001970753662
913 1370306358800934601314240570748
914 1429098660047114256640381221615
915 1490379415722478173240792900415
916 1554252534624835644815238916120
917 1620826206069209502027247306829
918 1690213073856218757428811052298
919 1762530417216103397554752902810
920 1837900339004357536564888317394
921 1916449961435699719706592008782
922 1998311629654304598552314828675
923 2083623123449827835436862196499
924 2172527877440829469683356839180
925 2265175210059719102175609185314
926 2361720561686365482331031318795
927 2462325742291012116364479354297
928 2567159188961178687822649409869
929 2676396233701783821041157969560
930 2790219381912860498476476565202
931 2908818601964929457048216420706
932 3032391626308413930984077740517
933 3161144264570399176834265583031
934 3295290729109631614759967536955
935 3435053973518892997909041922842
936 3580666044582847793710768317198
937 3732368448219124680574319781193
938 3890412529950832669099049595675
939 4055059870479906565649664389130
940 4226582696952706395375834893235
941 4405264310532138739084794908509
942 4591399530914310189826099202991
943 4785295158452342153079086476286
944 4987270454575562118164178636615
945 5197657641218817358039234526079
946 5416802420004227802379625034730
947 5645064511946283894518170862048
948 5882818218480902819067463357271
949 6130453004649861275135380436285
950 6388374105304030707706747415682
951 6657003155222030792512777198353
952 6936778844075400564262513754549
953 7228157597207143698646381569183
954 7531614283227652844943634497050
955 7847642949470538128306367965390
956 8176757586390901277782724824139
957 8519492922030090764425990840440
958 8876405247714076060236243072003
959 9248073276197273202114507489535
960 9635099033510077813647720275188
961 10038108785816499404523065326216
962 10457754002638288461878991165095
963 10894712357853790826602725875373
964 11349688769933606688238262309085
965 11823416482930961163152043000809
966 12316658189802673165598435190054
967 12830207199696727978962135767769
968 13364888650904889183451882979305
969 13921560771243518406356136940645
970 14501116187692989168341985481601
971 15104483287195777368922231745779
972 15732627630585678559865143408800
973 16386553421695637327055621928955
974 17067305033769580787493830042835
975 17775968595384425742005051310603
976 18513673638172293107440539838948
977 19281594808719916688932265678566
978 20080953647112504320448576053607
979 20913020434682904575791996719555
980 21779116113624093054549661987030
981 22680614281223729659626046842956
982 23618943261584107791113876445219
983 24595588257799233745114150684293
984 25612093587673310248235356757585
985 26670065006181573029960766065685
986 27771172117995529923759317659364
987 28917150883520205092701251712819
988 30109806222021299739273303395353
989 31351014715555278432468059599290
990 32642727417555598020142314831908
991 33986972770073654446992714608363
992 35385859633823871752915441435235
993 36841580435338745352948638137345
994 38356414435701938712481416385275
995 39932731125495775581157508887693
996 41572993750774050854838755378916
997 43279762975052068159821520115047
998 45055700682493606080426377287370
999 46903573927669194152438858958190
1000 48826259037462073317003539456935