1 0
2 0
3 1
4 1
5 2
6 4
7 5
8 7
9 11
10 14
11 19
12 26
13 33
14 43
15 55
16 70
17 88
18 111
19 137
20 170
21 208
22 256
23 311
24 378
25 456
26 551
27 658
28 790
29 940
30 1119
31 1325
32 1570
33 1847
34 2179
35 2554
36 2996
37 3499
38 4088
39 4753
40 5533
41 6414
42 7436
43 8593
44 9931
45 11439
46 13180
47 15140
48 17391
49 19926
50 22827
51 26087
52 29810
53 33988
54 38744
55 44076
56 50129
57 56908
58 64584
59 73170
60 82871
61 93709
62 105926
63 119562
64 134900
65 152000
66 171200
67 192579
68 216539
69 243195
70 273012
71 306148
72 343161
73 384244
74 430060
75 480872
76 537447
77 600127
78 669826
79 746964
80 832623
81 927345
82 1032384
83 1148426
84 1276962
85 1418823
86 1575769
87 1748842
88 1940092
89 2150810
90 2383414
91 2639466
92 2921817
93 3232382
94 3574486
95 3950468
96 4364240
97 4818614
98 5318183
99 5866356
100 6468497
101 7128715
102 7853300
103 8647171
104 9517698
105 10470776
106 11515009
107 12657448
108 13908158
109 15275528
110 16771320
111 18405516
112 20191841
113 22142144
114 24272436
115 26596753
116 29133767
117 31900067
118 34917407
119 38205376
120 41789298
121 45692258
122 49943721
123 54570842
124 59607896
125 65086778
126 71047300
127 77526900
128 84571804
129 92225850
130 100542698
131 109573632
132 119380862
133 130024329
134 141576114
135 154106150
136 167697939
137 182432979
138 198407877
139 215717557
140 234473731
141 254786753
142 276785767
143 300598957
144 326375449
145 354264031
146 384436793
147 417066197
148 452350777
149 490490239
150 531713379
151 576251317
152 624367575
153 676329265
154 732439781
155 793007590
156 858381666
157 928917983
158 1005017700
159 1087091175
160 1175599351
161 1271014875
162 1373866943
163 1484699605
164 1604120056
165 1732753910
166 1871297500
167 2020469704
168 2181068498
169 2353919355
170 2539936175
171 2740066042
172 2955355083
173 3186889095
174 3435864746
175 3703526075
176 3991241150
177 4300434195
178 4632668383
179 4989573121
180 5372933409
181 5784612163
182 6226646512
183 6701164895
184 7210490924
185 7757054783
186 8343505297
187 8972615476
188 9647403200
189 10371030590
190 11146934139
191 11978717468
192 12870291595
193 13825760777
194 14849573661
195 15946401913
196 17121303031
197 18379591350
198 19727013512
199 21169611464
200 22713911477
201 24366778785
202 26135621208
203 28028235093
204 30053024639
205 32218838619
206 34535206762
207 37012166977
208 39660519824
209 42491645955
210 45517780254
211 48751818886
212 52207614734
213 55899773738
214 59843973063
215 64056746627
216 68555827750
217 73359923190
218 78489082556
219 83964460624
220 89808715112
221 96045757279
222 102701180517
223 109801998535
224 117377107470
225 125457011521
226 134074320802
227 143263464740
228 153061228493
229 163506453421
230 174640615770
231 186507514290
232 199153893836
233 212629120683
234 226985854882
235 242279712825
236 258569992723
237 275919324777
238 294394453507
239 314065876552
240 335008688455
241 357302207899
242 381030888812
243 406283936864
244 433156292464
245 461748238138
246 492166459577
247 524523644347
248 558939628009
249 595540985621
250 634462269352
251 675845595246
252 719841979931
253 766610923847
254 816321856293
255 869153717678
256 925296520957
257 984950936547
258 1048329980245
259 1115658603358
260 1187175518469
261 1263132798654
262 1343797852242
263 1429453036395
264 1520397793442
265 1616948283214
266 1719439695798
267 1828225908649
268 1943681989954
269 2066203887987
270 2196211141880
271 2334146610237
272 2480479407876
273 2635704682441
274 2800346796324
275 2974959161980
276 3160127690217
277 3356470694882
278 3564642631808
279 3785334085571
280 4019275823911
281 4267238881424
282 4530038957607
283 4808536613198
284 5103642042556
285 5416315400705
286 5747571983177
287 6098482704674
288 6470179722315
289 6863857088360
290 7280776857266
291 7722269937885
292 8189742727244
293 8684678190970
294 9208643071314
295 9763289227640
296 10350361470277
297 10971699196470
298 11629244906919
299 12325046176855
300 13061264916609
301 13840179721929
302 14664195946445
303 15535848480074
304 16457812707036
305 17432907766646
306 18464108477623
307 19554549142215
308 20707536524268
309 21926554263435
310 23215277004259
311 24577575494439
312 26017531969600
313 27539446018590
314 29147851338789
315 30847522459501
316 32643492993851
317 34541063320538
318 36545820469836
319 38663646876277
320 40900742047706
321 43263632511836
322 45759195434065
323 48394669893209
324 51177682626582
325 54116260786574
326 57218860008254
327 60494378812546
328 63952189211371
329 67602152939094
330 71454654829389
331 75520621078250
332 79811555646405
333 84339560775740
334 89117376698720
335 94158404651626
336 99476750195179
337 105087248995936
338 111005514090295
339 117247964730254
340 123831877956391
341 130775420832227
342 138097706724206
343 145818831285440
344 153959933874466
345 162543237682207
346 171592116766642
347 181131140754143
348 191186148007088
349 201784295377379
350 212954138071191
351 224725684976521
352 237130485844463
353 250201692761538
354 263974155321957
355 278484488876176
356 293771178426942
357 309874654343448
358 326837405787641
359 344704064647711
360 363521529370365
361 383339057944972
362 404208403096741
363 426183915229519
364 449322690025514
365 473684682339092
366 499332867342263
367 526333366461964
368 554755623310104
369 584672542856829
370 616160683503771
371 649300410796291
372 684176107116787
373 720876341367173
374 759494097891893
375 800126963693516
376 842877378344290
377 887852840441442
378 935166180423699
379 984935788137696
380 1037285910644287
381 1092346902938518
382 1150255553025473
383 1211155358023624
384 1275196878989600
385 1342538044846383
386 1413344539658339
387 1487790137048469
388 1566057122870019
389 1648336663019329
390 1734829264713436
391 1825745180876971
392 1921304913517049
393 2021739658151008
394 2127291853087632
395 2238215667677142
396 2354777601642124
397 2477257021279545
398 2605946813353049
399 2741153973749791
400 2883200320847511
401 3032423141534498
402 3189175969400641
403 3353829293476119
404 3526771407063588
405 3708409185032377
406 3899169009627934
407 4099497622681416
408 4309863135286930
409 4530755961858767
410 4762689921174211
411 5006203259830243
412 5261859852807119
413 5530250324548675
414 5811993357918751
415 6107736921863277
416 6418159698403649
417 6743972426634096
418 7085919458242355
419 7444780228458929
420 7821370951507621
421 8216546230061679
422 8631200903021564
423 9066271806053316
424 9522739785164022
425 10001631622003712
426 10504022227882015
427 11031036748715074
428 11583852955391343
429 12163703544549673
430 12771878742578994
431 13409728819828847
432 14078666927017825
433 14780171842009851
434 15515791059027238
435 16287143788794244
436 17095924322697108
437 17943905308903135
438 18832941415517919
439 19764972907242528
440 20742029633636584
441 21766234933003249
442 22839809974098869
443 23965078016240105
444 25144469135220858
445 26380524871125920
446 27675903371844184
447 29033384462783349
448 30455875244198628
449 31946415619936332
450 33508184387884147
451 35144505268040574
452 36858853528724433
453 38654862557713635
454 40536331070456453
455 42507230271754506
456 44571711696128118
457 46734115011545673
458 48998976546335031
459 51371037790839361
460 53855254669832371
461 56456806802717643
462 59181107585374748
463 62033814274632584
464 65020838948837729
465 68148359487886040
466 71422831487603209
467 74851000212626688
468 78439913545972556
469 82196934998541797
470 86129757782053336
471 90246418965985237
472 94555314769384831
473 99065215963663663
474 103785284486758146
475 108725090198407408
476 113894628928734208
477 119304340701537608
478 124965129338648855
479 130888382276395069
480 137085991857136610
481 143570376874441048
482 150354505694082653
483 157451919674718566
484 164876758272347481
485 172643784495439331
486 180768412159552963
487 189266733548988486
488 198155549001973605
489 207452396965110481
490 217175586104341072
491 227344227953804908
492 237978271763797750
493 249098539962207762
494 260726765967978722
495 272885632701201963
496 285598813609236182
497 298891014480872501
498 312788017952437785
499 327316728902309594
500 342505222726096526
501 358382794610334581
502 374980011889324626
503 392328767521192304
504 410462336864331221
505 429415435705267364
506 449224281820052383
507 469926657931749310
508 491561978451642728
509 514171357774783947
510 537797682627790374
511 562485686143907026
512 588282026278573329
513 615235366141115434
514 643396458976365935
515 672818235268571555
516 703555894827393330
517 735667001221084520
518 769211581548404755
519 804252228802884246
520 840854209958736291
521 879085576916297242
522 919017283580267021
523 960723306088445242
524 1004280769614784393
525 1049770078639671952
526 1097275054268659253
527 1146883075363053555
528 1198685227228123911
529 1252776454487973250
530 1309255722064881163
531 1368226180752737720
532 1429795341482270798
533 1494075254623100201
534 1561182698608402035
535 1631239374077278723
536 1704372108017304358
537 1780713063946890432
538 1860399962825616074
539 1943576310571062595
540 2030391637085356745
541 2121001742503042514
542 2215568955788412704
543 2314262401220977150
544 2417258278132436813
545 2524740149254769311
546 2636899243288807906
547 2753934766867519350
548 2876054231780688379
549 3003473792443321511
550 3136418599743646860
551 3275123166054470059
552 3419831747825317763
553 3570798740333769538
554 3728289091307960792
555 3892578727786288399
556 4063955003234462086
557 4242717159066432477
558 4429176807911747719
559 4623658432549048769
560 4826499908185608142
561 5038053041768334921
562 5258684136359173857
563 5488774574018390243
564 5728721425598104094
565 5978938080639879026
566 6239854906165370425
567 6511919927296216722
568 6795599538896871202
569 7091379240910881409
570 7399764407007938807
571 7721281078938325597
572 8056476796655548643
573 8405921456321609678
574 8770208206720005106
575 9149954375900267279
576 9545802439065301346
577 9958421019226187398
578 10388505932144773184
579 10836781266780960949
580 11304000513298162317
581 11790947729527353185
582 12298438758501635824
583 12827322487636505240
584 13378482162752657870
585 13952836747182549075
586 14551342339770331767
587 15174993641663530974
588 15824825486348156703
589 16501914422473974853
590 17207380364594407427
591 17942388301007368977
592 18708150074526579652
593 19505926225000496207
594 20337027910147432878
595 21202818893146198920
596 22104717614325468047
597 23044199335004926197
598 24022798371643553077
599 25042110407953368738
600 26103794903985594669
601 27209577589444704644
602 28361253061130307255
603 29560687471351572357
604 30809821328150740526
605 32110672393761993777
606 33465338703124729039
607 34876001688451780245
608 36344929432702320162
609 37874480037527439129
610 39467105129619616920
611 41125353490595021358
612 42851874835474841791
613 44649423724449670763
614 46520863634184336133
615 48469171172897037271
616 50497440466720639510
617 52608887701125187918
618 54806855846222409111
619 57094819549272654014
620 59476390224593618378
621 61955321323729846954
622 64535513817530194356
623 67221021872528748222
624 70016058754797267234
625 72925002943200330788
626 75952404486818956271
627 79102991588009993840
628 82381677447545841674
629 85793567352839563988
630 89343966047464306158
631 93038385362513058505
632 96882552149862069892
633 100882416497429902968
634 105044160268444931743
635 109374205944365777071
636 113879225815517360853
637 118566151498648302983
638 123442183827627953972
639 128514803096060949469
640 133791779700304888572
641 139281185161254387754
642 144991403575762401124
643 150931143475663310085
644 157109450147778307933
645 163535718392487742401
646 170219705776891987181
647 177171546359787455095
648 184401764947259228651
649 191921291855784253054
650 199741478244572946694
651 207874111993739632242
652 216331434193110879725
653 225126156217991663711
654 234271477459943374152
655 243781103688660582177
656 253669266116418335438
657 263950741140986327159
658 274640870842082202925
659 285755584207117144059
660 297311419165099772203
661 309325545404361465367
662 321815788056967066985
663 334800652225443305358
664 348299348438902841476
665 362331819014231232765
666 376918765413857208917
667 392081676575881436999
668 407842858312768181588
669 424225463754563729686
670 441253524937785652908
671 458951985516224317415
672 477346734700010987188
673 496464642399569509006
674 516333595686302357785
675 536982536547111385648
676 558441501050403461256
677 580741659901282833384
678 603915360509700633063
679 627996170549994285653
680 653018923142046925994
681 679019763633372320397
682 706036198119174603149
683 734107143680715690801
684 763272980486239724369
685 793575605735983695055
686 825058489603126791026
687 857766733153588044329
688 891747128404555124418
689 927048220506234657492
690 963720372215189816784
691 1001815830645554295641
692 1041388796475450644311
693 1082495495596937821792
694 1125194253396286178797
695 1169545571655197513045
696 1215612208269777073787
697 1263459259780446966777
698 1313154246920187000484
699 1364767203177166644301
700 1418370766590338093012
701 1474040274777255813970
702 1531853863424517741468
703 1591892568243649605827
704 1654240430635332393195
705 1718984607068734060254
706 1786215482432071020242
707 1856026787365514485188
708 1928515719846556984359
709 2003783071043755833463
710 2081933355723769098151
711 2163074947232885848769
712 2247320217353626018471
713 2334785681063418246650
714 2425592146512502548628
715 2519864870254435188156
716 2617733718063881188553
717 2719333331382047281318
718 2824803299743005248117
719 2934288339228887066793
720 3047938477326854825187
721 3165909244244158983499
722 3288361871074995811435
723 3415463494884567025224
724 3547387371126085678930
725 3684313093466035730142
726 3826426821456762897456
727 3973921516142485009439
728 4126997184062512957963
729 4285861129749493646050
730 4450728217212644022878
731 4621821140516523519611
732 4799370703973046306057
733 4983616112071104747604
734 5174805269690887648516
735 5373195092742257277811
736 5579051829805402097809
737 5792651394929376623888
738 6014279712199737589802
739 6244233072248481835764
740 6482818501352460821241
741 6730354143312516115433
742 6987169654796571496707
743 7253606614359514826074
744 7530018945862390229200
745 7816773356525984610565
746 8114249790382975507676
747 8422841897387756763088
748 8742957518992262779093
749 9075019190472850017908
750 9419464660863372480129
751 9776747430807497906311
752 10147337309235044404246
753 10531720989205564006058
754 10930402643876597570970
755 11343904542972354490071
756 11772767690766073793916
757 12217552485986860155025
758 12678839404723468687243
759 13157229706773561893700
760 13653346166573724626039
761 14167833829199369316230
762 14701360792636446693966
763 15254619016857783227286
764 15828325160976644204855
765 16423221449057327612935
766 17040076565930377028943
767 17679686583642726694606
768 18342875919969928911399
769 19030498329675053159271
770 19743437930025825764163
771 20482610261312903977502
772 21248963383970429953170
773 22043479013104369211338
774 22867173692124833817727
775 23721100006355107161884
776 24606347838414443940036
777 25524045666319491303949
778 26475361906208457886188
779 27461506300710258553727
780 28483731354976378118438
781 29543333821480674254283
782 30641656235725450952092
783 31780088504048006444717
784 32960069545793979358956
785 34183088991147078695665
786 35450688937017377928043
787 36764465762379970363052
788 38126072005610375735033
789 39537218305317997106933
790 40999675407377099454204
791 42515276239773891969168
792 44085918058131689460646
793 45713564663658320865126
794 47400248696550272658442
795 49148074006732179571254
796 50959218105149292408268
797 52835934697635430664012
798 54780556304768481200469
799 56795496969889926042214
800 58883255058906883044440
801 61046416154217868180455
802 63287656046599920718284
803 65609743827574489726444
804 68015545086322405852718
805 70508025213853749406085
806 73090252818749986454167
807 75765403257385626505620
808 78536762283209077119821
809 81407729818205281576293
810 84381823851398320406262
811 87462684467746698791071
812 90654078012585213223972
813 93959901395212030779337
814 97384186537088860317805
815 100931104968515570227396
816 104604972579580523348243
817 108410254529528614378542
818 112351570320702280008368
819 116433699041497175995735
820 120661584784863675089773
821 125040342247115911574625
822 129575262513978648488363
823 134271819038975368810694
824 139135673821511666090872
825 144172683790122060777517
826 149388907398684320420062
827 154790611441458678980682
828 160384278095233859268681
829 166176612194852694749736
830 172174548750906624191189
831 178385260716315075783451
832 184816167011117751961926
833 191474940812668666413061
834 198369518121131987247286
835 205508106607972892857152
836 212899194757950898631411
837 220551561312846762081855
838 228474285028075371287503
839 236676754750989324201407
840 245168679832710407630386
841 253960100882905269193707
842 263061400880069609439569
843 272483316647389187812057
844 282236950707514008567662
845 292333783527008977387093
846 302785686164637119530984
847 313604933334979384663561
848 324804216902417474881432
849 336396659817773104495857
850 348395830513554207563731
851 360815757770942626975846
852 373670946075454916758839
853 386976391475306942519405
854 400747597960455568141783
855 415000594377302777229103
856 429751951898141431138634
857 445018802061344892126265
858 460818855402553826924393
859 477170420693945446467399
860 494092424813084993268000
861 511604433259598080482121
862 529726671342487008700723
863 548480046057557765291791
864 567886168679185669782623
865 587967378087193927052866
866 608746764854564402898593
867 630248196118146888697187
868 652496341259669326173172
869 675516698420697012081996
870 699335621880523827541971
871 723980350322220636143453
872 749479036017607838671621
873 775860774958055692424587
874 803155637963773006054830
875 831394702800273954731934
876 860610087336693621014443
877 890834983776542536307316
878 922103693997704290020461
879 954451666034288533999045
880 987915531739407900910321
881 1022533145663642305206661
882 1058343625190662562199494
883 1095387391967065047863736
884 1133706214670440173046658
885 1173343253155160275199529
886 1214343104022616924329147
887 1256751847657981783745038
888 1300617096783094132082458
889 1345988046570301960332717
890 1392915526369908819822633
891 1441452053098980501904318
892 1491651886347399430717573
893 1543571085252033185651514
894 1597267567198338692116962
895 1652801168403577427026041
896 1710233706444606780544653
897 1769629044787940560420988
898 1831053159388910040117390
899 1894574207421357733911900
900 1960262598208797687149468
901 2028191066422448840702566
902 2098434747621428047599042
903 2171071256204733296923635
904 2246180765854922042642014
905 2323846092547604120062908
906 2404152780211554026080775
907 2487189189118332135252376
908 2573046587091418049226551
909 2661819243618814108088120
910 2753604526964637220524026
911 2848503004369042101214210
912 2946618545437844634887651
913 3048058428816909448589130
914 3152933452258876775518404
915 3261358046183370103706927
916 3373450390844843255941251
917 3489332537215663935652999
918 3609130531705575814463766
919 3732974544831992874035987
920 3860999003969675384130379
921 3993342730301523424292789
922 4130149080106893947565242
923 4271566090516910837151484
924 4417746629881506819396697
925 4568848552885878948114559
926 4725034860569934167913458
927 4886473865397126654443246
928 5053339361535636080092244
929 5225810800507546926911551
930 5404073472378917633677171
931 5588318692656229108931915
932 5778743995072641920671057
933 5975553330439986567174706
934 6178957271761093434875440
935 6389173225789463699759564
936 6606425651242739843827552
937 6830946283868734554959195
938 7062974368583043751812784
939 7302756898889481639430195
940 7550548863815688212369013
941 7806613502588391259858806
942 8071222567294800672734558
943 8344656593768672213097442
944 8627205180962496385779973
945 8919167279059264292716052
946 9220851486601144955355804
947 9532576356904351838980932
948 9854670714054366428728454
949 10187473978767588130109576
950 10531336504431422870607237
951 10886619923626694658579041
952 11253697505463308123573587
953 11632954524051945872873762
954 12024788638462778919307048
955 12429610284514022927604457
956 12847843078762570515810733
957 13279924235060799140104066
958 13726304994074309620079460
959 14187451066147252027153879
960 14663843087933866885412826
961 15155977093206822808024085
962 15664364998286279095802703
963 16189535102525627306967610
964 16732032604324652836347714
965 17292420133132977910005348
966 17871278297942940628184535
967 18469206252763304415535689
968 19086822279603061515731705
969 19724764389486979751665226
970 20383690942064060408008169
971 21064281284362635188727959
972 21767236409287075136536015
973 22493279634443849964219906
974 23243157301927728238766019
975 24017639499691913297441396
976 24817520805170853600302034
977 25643621051817745554630113
978 26496786119265671513409163
979 27377888747814908671540848
980 28287829377997943544015249
981 29227537015967675184537786
982 30197970125505461689170930
983 31200117547440013365519362
984 32234999447321582818679415
985 33303668292190699666528877
986 34407209857336528187680718
987 35546744263935224124570404
988 36723427048516994863672218
989 37938450265206421215021035
990 39193043621741543849494310
991 40488475650273687189057821
992 41826054914013680681425337
993 43207131250787286810801118
994 44633097054629206449543481
995 46105388596542929757176560
996 47625487385623274712494941
997 49194921571737174487566228
998 50815267391031006921482891
999 52488150655532378480189606
1000 54215248288190318262304396