0 0
1 1
2 1
3 1
4 2
5 2
6 3
7 4
8 6
9 7
10 10
11 13
12 17
13 22
14 28
15 36
16 46
17 58
18 72
19 92
20 113
21 141
22 174
23 216
24 263
25 324
26 394
27 481
28 583
29 707
30 852
31 1029
32 1235
33 1481
34 1774
35 2118
36 2524
37 3003
38 3567
39 4225
40 5003
41 5906
42 6968
43 8202
44 9646
45 11317
46 13275
47 15531
48 18160
49 21195
50 24718
51 28772
52 33472
53 38872
54 45107
55 52269
56 60514
57 69967
58 80832
59 93266
60 107516
61 123818
62 142454
63 163732
64 188025
65 215719
66 247266
67 283194
68 324045
69 370495
70 423240
71 483121
72 551004
73 627986
74 715121
75 813783
76 925334
77 1051464
78 1193867
79 1354694
80 1536041
81 1740571
82 1970949
83 2230440
84 2522376
85 2850837
86 3219943
87 3634715
88 4100354
89 4622991
90 5209082
91 5866227
92 6602402
93 7426910
94 8349702
95 9382129
96 10536488
97 11826738
98 13267988
99 14877299
100 16673355
101 18676924
102 20910935
103 23400831
104 26174649
105 29263377
106 32701416
107 36526433
108 40780409
109 45509280
110 50764117
111 56600742
112 63081409
113 70273790
114 78253473
115 87102683
116 96912975
117 107783931
118 119826559
119 133161276
120 147922263
121 164255249
122 182322121
123 202298832
124 224380768
125 248780007
126 275731831
127 305491960
128 338343246
129 374593384
130 414582440
131 458680131
132 507294525
133 560869775
134 619894914
135 684902610
136 756478759
137 835261317
138 921951165
139 1017312077
140 1122181452
141 1237472298
142 1364184746
143 1503408885
144 1656337590
145 1824271628
146 2008632267
147 2210969632
148 2432976171
149 2676497108
150 2943545499
151 3236316437
152 3557201891
153 3908810072
154 4293981527
155 4715812162
156 5177671614
157 5683232141
158 6236487352
159 6841788544
160 7503865700
161 8227869837
162 9019397725
163 9884542762
164 10829921481
165 11862735124
166 12990800566
167 14222620784
168 15567422372
169 17035238299
170 18636950096
171 20384385477
172 22290368890
173 24368832341
174 26634877424
175 29104903348
176 31796679018
177 34729491853
178 37924234930
179 41403574851
180 45192058546
181 49316305691
182 53805134313
183 58689782327
184 64004059111
185 69784595040
186 76071025536
187 82906275632
188 90336777080
189 98412794609
190 107188685759
191 116723268555
192 127080133622
193 138328063221
194 150541398021
195 163800516708
196 178192271256
197 193810528976
198 210756689607
199 229140303588
200 249079676771
201 270702578670
202 294146953678
203 319561724483
204 347107629236
205 376958139990
206 409300436244
207 444336458517
208 482284045139
209 523378132137
210 567872080480
211 616039051033
212 668173540534
213 724592961650
214 785639425065
215 851681544941
216 923116506717
217 1000372139995
218 1083909301221
219 1174224258688
220 1271851443509
221 1377366181618
222 1491387869304
223 1614583113754
224 1747669380020
225 1891418606311
226 2046661397978
227 2214291174574
228 2395268992771
229 2590628315180
230 2801480534181
231 3029020460764
232 3274532658228
233 3539397741067
234 3825099636604
235 4133232825612
236 4465510642999
237 4823773604536
238 5209998902889
239 5626309960111
240 6074987291117
241 6558479473701
242 7079415547225
243 7640617612369
244 8245114991703
245 8896158670861
246 9597237470929
247 10352094610369
248 11164746142287
249 12039499946588
250 12980976759614
251 13994131915010
252 15084279330264
253 16257116400739
254 17518751320432
255 18875731580162
256 20335075098171
257 21904302794541
258 23591474061575
259 25405224000634
260 27354803792501
261 29450123250025
262 31701796777212
263 34121191934201
264 36720481755911
265 39512700174313
266 42511801522465
267 45732723760085
268 49191456160613
269 52905111358422
270 56892002336445
271 61171724513550
272 65765243244116
273 70694987308860
274 75984948367945
275 81660787338828
276 87749947420404
277 94281775108010
278 101287648555734
279 108801115191746
280 116858037497473
281 125496749371788
282 134758221660806
283 144686239783315
284 155327591577071
285 166732269001769
286 178953681292000
287 192048883840347
288 206078820014618
289 221108580816592
290 237207679072142
291 254450343901407
292 272915831570615
293 292688759233990
294 313859457264206
295 336524347405129
296 360786341918645
297 386755271913603
298 414548339444703
299 444290602413451
300 476115486507438
301 510165333999570
302 546591983181288
303 585557389282519
304 627234280150821
305 671806858430059
306 719471543309742
307 770437764388652
308 824928800426906
309 883182676589798
310 945453112654203
311 1012010536655957
312 1083143156519278
313 1159158104908508
314 1240382649847175
315 1327165487374960
316 1419878108821747
317 1518916259772722
318 1624701483808033
319 1737682768745033
320 1858338288934171
321 1987177262283525
322 2124741916111352
323 2271609581174322
324 2428394909093706
325 2595752233022208
326 2774378067905266
327 2965013770993141
328 3168448360224464
329 3385521511639992
330 3617126735414461
331 3864214751963347
332 4127797069731998
333 4408949786793471
334 4708817620085324
335 5028618184734487
336 5369646530361371
337 5733279956925502
338 6120983120174358
339 6534313449811193
340 6974926893886998
341 7444584012734417
342 7945156440387505
343 8478633736808319
344 9047130653470196
345 9652894836178551
346 10298314992642530
347 10985929548898353
348 11718435828229472
349 12498699776764044
350 13329766275761331
351 14214870065561710
352 15157447328024179
353 16161147952950741
354 17229848543499244
355 18367666186564368
356 19578973051618005
357 20868411845420907
358 22240912195138763
359 23701707988553573
360 25256355754533989
361 26910754113873041
362 28671164394690197
363 30544232445190510
364 32537011749690695
365 34656987883447996
366 36912104425767837
367 39310790370064348
368 41861989164440533
369 44575189426311792
370 47460457479570432
371 50528471763028593
372 53790559275741730
373 57258734113954428
374 60945738283063058
375 64865084847625577
376 69031103621669934
377 73458989471440619
378 78164853454267245
379 83165776876124901
380 88479868513932173
381 94126325098648037
382 100125495328944332
383 106498947526444858
384 113269541229144932
385 120461502850995369
386 128100505732383364
387 136213754730534156
388 144830075704507739
389 153980010067151849
390 163695914792430289
391 174012068076863791
392 184964781079062929
393 196592515967810381
394 208936010740700816
395 222038411078939079
396 235945409743105791
397 250705393814977302
398 266369600335606852
399 282992280691228461
400 300630874346013418
401 319346192324652409
402 339202611098696081
403 360268277337076160
404 382615324233408812
405 406320099937065709
406 431463408864074019
407 458130766488294731
408 486412668460314564
409 516404874736233021
410 548208709640590642
411 581931378639176891
412 617686302829541465
413 655593472028001317
414 695779817554960183
415 738379605711545199
416 783534853151237044
417 831395765269026782
418 882121198923174380
419 935879150754510153
420 992847272543637540
421 1053213415028339027
422 1117176201758088027
423 1184945634585135320
424 1256743732519072926
425 1332805205738838547
426 1413378166657663447
427 1498724880049318823
428 1589122554315812336
429 1684864176144907800
430 1786259390841111302
431 1893635430841687002
432 2007338094929884392
433 2127732780946534666
434 2255205574763357024
435 2390164398641910423
436 2533040222018982027
437 2684288338196004920
438 2844389710284473935
439 3013852390273575317
440 3193213014914840446
441 3383038382721730105
442 3583927116158178100
443 3796511413786770102
444 4021458896875255092
445 4259474555751113707
446 4511302800871447988
447 4777729624472996524
448 5059584878288178767
449 5357744673821652862
450 5673133911253014751
451 6006728944151086270
452 6359560386705586744
453 6732716071425705492
454 7127344164719949942
455 7544656449143437862
456 7985931780517572862
457 8452519729626110643
458 8945844417565691270
459 9467408555468358489
460 10018797698640261455
461 10601684726944081720
462 11217834562545163601
463 11869109138066600387
464 12557472627461187924
465 13284996953988735574
466 14053867588920210075
467 14866389656828834564
468 15724994362549550197
469 16632245757281522331
470 17590847860526420481
471 18603652157116851629
472 19673665487807974485
473 20804058354637225487
474 21998173661500241373
475 23259535913288325095
476 24591860896214033533
477 25999065865028271038
478 27485280262160203275
479 29054856997068843405
480 30712384313500936533
481 32462698275781734953
482 34310895904768721540
483 36262348997719893733
484 38322718665943954338
485 40497970627911686530
486 42794391295275612715
487 45218604693240137480
488 47777590256671772941
489 50478701547534108596
490 53329685939380998798
491 56338705319037739129
492 59514357856000295749
493 62865700894672820907
494 66402275025252073465
495 70134129393871195342
496 74071848313622340713
497 78226579243098043477
498 82610062200479053138
499 87234660686427284022
500 92113394190858570691
501 97259972364135932138
502 102688830935509254493
503 108415169467335012319
504 114454991036440217248
505 120825143939941481102
506 127543365526266188842
507 134628328258340600624
508 142099688120004619390
509 149978135483214890845
510 158285448558444296909
511 167044549557475716509
512 176279563703460964808
513 186015881230236840021
514 196280222519457816281
515 207100706531580521934
516 218506922694309239342
517 230530006419956144511
518 243202718431843605327
519 256559528088148846638
520 270636700901449773506
521 285472390460971151520
522 301106734975708380785
523 317581958665844544869
524 334942478242488261612
525 353235014725578735552
526 372508710863956629285
527 392815254432060154873
528 414209007693560123282
529 436747143333404609643
530 460489787177440411341
531 485500168030745399500
532 511844774985476922537
533 539593522561911317645
534 568819924068189759039
535 599601273578146154233
536 632018836950773748900
537 666158052329894327364
538 702108740589280228092
539 739965326204769505324
540 779827069064341005345
541 821798307744822396512
542 865988714816281942516
543 912513564754489795462
544 961494015077368805345
545 1013057401342512471536
546 1067337546681823297743
547 1124475086572499848487
548 1184617809586279026566
549 1247921014884318966671
550 1314547887271746057733
551 1384669890653942793320
552 1458467180787599370103
553 1536129038250455549493
554 1617854322609239110085
555 1703851948799443772260
556 1794341386791127640026
557 1889553185652653050161
558 1989729523190214680997
559 2095124782382728494589
560 2206006155903376561968
561 2322654280065320780312
562 2445363899607030709833
563 2574444564783880738348
564 2710221362317347920422
565 2853035681809864357757
566 3003246019325315890797
567 3161228819898078907786
568 3327379360833216247896
569 3502112677730196845182
570 3685864535270694983719
571 3879092444888310493547
572 4082276731555365425433
573 4295921652007627143209
574 4520556566854928363844
575 4756737169120636946229
576 5005046771890704344142
577 5266097657858217285451
578 5540532493698658721152
579 5829025812327617100560
580 6132285566254356539518
581 6451054755373680945714
582 6786113132713673867135
583 7138278991799619430499
584 7508411039484132171318
585 7897410358251399796437
586 8306222462208894870361
587 8735839451154435081500
588 9187302267329042946648
589 9661703059658811715892
590 10160187660530101204887
591 10683958180355237089499
592 11234275725447060447250
593 11812463244955550433121
594 12419908512902764268811
595 13058067251611295095455
596 13728466403128174920229
597 14432707555531569697824
598 15172470531340023562803
599 15949517145558379885655
600 16765695141254917283099
601 17622942310910210232487
602 18523290812169057485941
603 19468871687007437022709
604 20461919593750293616380
605 21504777761794416290859
606 22599903179350527339898
607 23749872024978398327921
608 24957385354187851138699
609 26225275052883317533379
610 27556510069971244003745
611 28954202942003651060747
612 30421616623319235715398
613 31962171635751004167869
614 33579453552608091572778
615 35277220832305538480641
616 37059413017709490360366
617 38930159317995134390552
618 40893787590568465547231
619 42954833741402148867333
620 45118051562954977554561
621 47388423029719211855601
622 49771169072330564545060
623 52271760852132658189721
624 54895931559056060950179
625 57649688756718489941922
626 60539327299705846139883
627 63571442849137641394624
628 66752946013765794998685
629 70091077145105588410455
630 73593421816343812022463
631 77267927016133995081608
632 81122918089744765249489
633 85167116461517451700408
634 89409658174064925146394
635 93860113281269784700873
636 98528506133746580058794
637 103425336597206581966094
638 108561602245912662781737
639 113948821575346310869418
640 119599058280113050392809
641 125524946645221457538126
642 131739718100944580973452
643 138257228993770833131037
644 145091989628209628522598
645 152259194636721096161805
646 159774754737498465919653
647 167655329942559192567522
648 175918364281279479357744
649 184582122107476734414267
650 193665726061062063892485
651 203189196758518127716800
652 213173494289635488181703
653 223640561601459624178566
654 234613369853862316098955
655 246115965834980211690955
656 258173521528533945033552
657 270812385929207017028252
658 284060139206370621795864
659 297945649320971826593842
660 312499131204876073026907
661 327752208616882517329301
662 343737978794503389606889
663 360491080025956396431906
664 378047762272126151134161
665 396445960974075302941012
666 415725374187465970393435
667 435927543191583098114613
668 457095936726945976019165
669 479276039022374774943044
670 502515441779233404421434
671 526863940288046826190610
672 552373633860154739817172
673 579099030765186981542377
674 607097157873272500131834
675 636427675209718929673888
676 667152995638746844562511
677 699338409902449111130164
678 733052217250776611906774
679 768365861908763397868414
680 805354075637687255176813
681 844095026658169146327725
682 884670475214623869705818
683 927165936072753235259552
684 971670848254188605235105
685 1018278752325722060069725
686 1067087475574074811015515
687 1118199325411626827413990
688 1171721291373229111036228
689 1227765256079934927308111
690 1286448215561474730107779
691 1347892509346358432961471
692 1412226060745879142836459
693 1479582627776809374623398
694 1550102065186493436550070
695 1623930598064137630971013
696 1701221107542665718518192
697 1782133429117319264947714
698 1866834664129542823826532
699 1955499504988365345278052
700 2048310574725797026076580
701 2145458781508448230802724
702 2247143688753998888426985
703 2353573901529019739671464
704 2464967469933362331176094
705 2581552310206577728145161
706 2703566644323027655866805
707 2831259458875164393918996
708 2964890984078359129602222
709 3104733193766256437364229
710 3251070327282463959212265
711 3404199434213004332520178
712 3564430942943962834825410
713 3732089254070655828706933
714 3907513359728094819196587
715 4091057489957960631908721
716 4283091787274485073232672
717 4484003010640923405324692
718 4694195270119530333139093
719 4914090793511406765668647
720 5144130726358200648338843
721 5384775966735617051012223
722 5636508036329062855045532
723 5899829989344619238357095
724 6175267360874056723851348
725 6463369156400780665855827
726 6764708884204698954695086
727 7079885632497924844040119
728 7409525193200379554695233
729 7754281234344508881800068
730 8114836523182030846029024
731 8491904202152528742050176
732 8886229119964503332107240
733 9298589220133704656744801
734 9729796989422049170806569
735 10180700968722553140207327
736 10652187329042521225757219
737 11145181515347931215158267
738 11660649961147776682826876
739 12199601876817120095835080
740 12763091114783187900310191
741 13352218114828890129909898
742 13968131932904289817328633
743 14612032356977492575763480
744 15285172113604005515388549
745 15988859169046355330730700
746 16724459128935712420482070
747 17493397740632780707569911
748 18297163502618566133666041
749 19137310385424976932075960
750 20015460668803060368034307
751 20933307900020988696501989
752 21892619978387447065141649
753 22895242371306587029651036
754 23943101467391223481969884
755 25038208072389000787835826
756 26182661053915133433424751
757 27378651141232353389701189
758 28628464886577443576110779
759 29934488794801303014819353
760 31299213628369726884828840
761 32725238895061875669573648
762 34215277526006890850527152
763 35772160752012951437651677
764 37398843186471689652834059
765 39098408123460736703259427
766 40874073060022981127530435
767 42729195451969118045248051
768 44667278712935279690963408
769 46691978466825974754844965
770 48807109064189565705075864
771 51016650373504876584943163
772 53324754858808894831034081
773 55735754955562503202067787
774 58254170757139706739434775
775 60884718024831298988051448
776 63632316534782608175140505
777 66502098775832081993865585
778 69499419012789583262512150
779 72629862730285406274456946
780 75899256472940065551887280
781 79313678098245716224133475
782 82879467459219824851969644
783 86603237534585131137473412
784 90491886024954508659710848
785 94552607434249625446292759
786 98792905656366099325287952
787 103220607087909601792746756
788 107843874288675152482533309
789 112671220212420034392832499
790 117711523031397688056505343
791 122974041579069915827052718
792 128468431436406351511257770
793 134204761688207688158814085
794 140193532376961471678772946
795 146445692682850610725382738
796 152972659859694227337153389
797 159786338957802353459673305
798 166899143365979594602806513
799 174324016206212564457219859
800 182074452615931185041044820
801 190164522954139272337876213
802 198608896969174918766930153
803 207422868967380609396855121
804 216622384023546670766213972
805 226224065275634299679068884
806 236245242347996110365211473
807 246703980949087854066861180
808 257619113691514886818816335
809 269010272184176359997072041
810 280897920448269267631445263
811 293303389710989015004907428
812 306248914632923439169393025
813 319757671027379224699708510
814 333853815132213829611467503
815 348562524497168847069310355
816 363910040552222611232053225
817 379923712925097821271336714
818 396632045578784435233152598
819 414064744842766689760820438
820 432252769414586220702875135
821 451228382411429193107125100
822 471025205554604413723821656
823 491678275573080653213748138
824 513224102915685067434522086
825 535700732865130580047327124
826 559147809150748453115630290
827 583606640160653869754065271
828 609120267858077094633998280
829 635733539510752530402016819
830 663493182346582465573243816
831 692447881253284502280690928
832 722648359644401037942916960
833 754147463618899975902923741
834 787000249546637265789628227
835 821264075217189478535944785
836 856998694695007319730435534
837 894266357029495776470909424
838 933131908974502061159989013
839 973662901877797226277449093
840 1015929702907479501806963702
841 1060005610788817296918559481
842 1105966976231895255236211670
843 1153893327237539810902726082
844 1203867499476388793584379361
845 1255975771943646771845077915
846 1310308008100041006488485850
847 1366957802717778176837058198
848 1426022634658906001225861692
849 1487604025822424779695455113
850 1551807706505777833230570830
851 1618743787435997447647392767
852 1688526938735799868809961936
853 1761276576100332293320603026
854 1837117054471081803116572502
855 1916177869504686621110788888
856 1998593867146048588185664765
857 2084505461627261029468800974
858 2174058862226442393128232295
859 2267406309133634844692377069
860 2364706318784492146159001934
861 2466123939036577438208397663
862 2571831014577722310238163212
863 2682006462971101927684316722
864 2796836561757459933155997419
865 2916515247051313002258522548
866 3041244424084980924759645846
867 3171234290171969254929907515
868 3306703670579580247918244474
869 3447880367819693235222883302
870 3595001524886439888030480983
871 3748314002990056326176030159
872 3908074774357524722352383943
873 4074551330692779576630112045
874 4248022107912250122689183505
875 4428776927795402542975607098
876 4617117457214735817195896274
877 4813357685635439996034307260
878 5017824421601647699485370264
879 5230857808953970521772752071
880 5452811863551814356550965343
881 5684055031303888460048438199
882 5924970768341365449005346554
883 6175958144200395818064521616
884 6437432468914134795998385420
885 6709825944949189533628056437
886 6993588344957445504439243063
887 7289187716351676618302723910
888 7597111113752189859928620908
889 7917865360392102453916279129
890 8251977839610705057715582658
891 8599997317607834925297340778
892 8962494798677277551959667922
893 9340064414184047378763297266
894 9733324346598978978163618306
895 10142917789954510151448893062
896 10569513948137871290293220720
897 11013809072492238905111430816
898 11476527540252782005801565306
899 11958422975403063409873754897
900 12460279413597973955826091572
901 12982912512862419360601338778
902 13527170811840370788378263532
903 14093937037436782760270226453
904 14684129463765303850080472093
905 15298703324387817048776982383
906 15938652279907680647632157728
907 16605009943057266419617338669
908 17298851463502048208229132632
909 18021295174668259665727443906
910 18773504304989059441697504907
911 19556688756055404424249018939
912 20372106950252488226019010126
913 21221067750560852141267942519
914 22104932455303178559304764455
915 23025116870723542278501985006
916 23983093464395591172381082971
917 24980393602569975533118352186
918 26018609874689422502196866933
919 27099398508422391466747719346
920 28224481878693336007518977756
921 29395651114319483536363455396
922 30614768806000824566763313768
923 31883771819551938289139834302
924 33204674218411481892493568847
925 34579570299617910243259702407
926 36010637747598396185823371280
927 37500140910282276617863310141
928 39050434202220796964403135116
929 40663965639571768642783896879
930 42343280511991148609648908304
931 44091025196663814967133962744
932 45909951119903124139753249608
933 47802918871953527984854225773
934 49772902480842799452125650643
935 51822993851350615498605435426
936 53956407375388593545026951223
937 56176484720323744006055820993
938 58486699802022927437721122600
939 60890663949650681630333300241
940 63392131269516978026862673156
941 65995004215545490202493887835
942 68703339374217103809359074638
943 71521353472138101666345229772
944 74453429614688043363520353243
945 77504123764519283779725221473
946 80678171469008695252661937674
947 83980494846102956855488492497
948 87416209838352142028635182324
949 90990633745292782451968998669
950 94709293044721539716899151281
951 98577931513794615269660128509
952 102602518661296541798537852518
953 106789258482845594270114437214
954 111144598551242248189416340391
955 115675239454622497239048471046
956 120388144595549981023415928434
957 125290550364670401615920084657
958 130389976703059233990871542433
959 135694238067919932577448227466
960 141211454816835367070020490835
961 146950065026340797112145120288
962 152918836761173038457601854751
963 159126880811158336829564822639
964 165583663913331632973597280683
965 172299022477533172801446347646
966 179283176834405639661467182358
967 186546746025417009684947328326
968 194100763155262076828691820573
969 201956691327749961816872891021
970 210126440187066906035021934280
971 218622383087114213686816096245
972 227457374912461422291328988458
973 236644770575325669098297977071
974 246198444213890945818216374268
975 256132809118216577002024144973
976 266462838410954078539098169953
977 277204086511096702335843157960
978 288372711410027811304063134893
979 299985497790213980242976776810
980 312059881018007849872879451734
981 324613972043185578408896005670
982 337666583239045818512176320600
983 351237255218142888941906432568
984 365346284660017912381451314354
985 380014753188629638471769264528
986 395264557338573296701432441118
987 411118439650612712386152908373
988 427600020938540041853801224920
989 444733833770920532947079601072
990 462545357212878813370014808968
991 481061052874740161184340196064
992 500308402316057296096273345820
993 520315945855332381099540705265
994 541113322837587587051004417915
995 562731313413847816664589395946
996 585201881888578634180873112792
997 608558221693173316510836550633
998 632834802045708047310169057782
999 658067416359385987410286704126
1000 684293232464372293593270331347