0 1
1 1
2 2
3 3
4 5
5 7
6 11
7 14
8 20
9 27
10 37
11 48
12 65
13 83
14 109
15 139
16 179
17 225
18 287
19 357
20 449
21 556
22 691
23 848
24 1047
25 1276
26 1561
27 1893
28 2299
29 2772
30 3348
31 4015
32 4820
33 5756
34 6874
35 8171
36 9716
37 11501
38 13614
39 16058
40 18932
41 22249
42 26138
43 30613
44 35838
45 41848
46 48831
47 56847
48 66139
49 76780
50 89073
51 103136
52 119327
53 137816
54 159056
55 183260
56 210993
57 242557
58 278626
59 319610
60 366354
61 419372
62 479710
63 548059
64 625679
65 713471
66 812999
67 925393
68 1052583
69 1196033
70 1358075
71 1540579
72 1746425
73 1977940
74 2238657
75 2531532
76 2860842
77 3230303
78 3645163
79 4110018
80 4631281
81 5214700
82 5868033
83 6598426
84 7415352
85 8327587
86 9346654
87 10483413
88 11751788
89 13165148
90 14740407
91 16493893
92 18446103
93 20617059
94 23031466
95 25713786
96 28693903
97 32001527
98 35672724
99 39743665
100 44257706
101 49258748
102 54799014
103 60931563
104 67719186
105 75226072
106 83527477
107 92700879
108 102836580
109 114027776
110 126382636
111 140013311
112 155049059
113 171624569
114 189894359
115 210019757
116 232185214
117 256583945
118 283435679
119 312971432
120 345452964
121 381155876
122 420391584
123 463488768
124 510817289
125 562768532
126 619781639
127 682321822
128 750909871
129 826098440
130 908504212
131 998782851
132 1097664271
133 1205925125
134 1324428382
135 1454093415
136 1595939171
137 1751052652
138 1920636286
139 2105973524
140 2308481859
141 2529675601
142 2771223802
143 3034911209
144 3322701838
145 3636696599
146 3979204354
147 4352696371
148 4759884030
149 5203671282
150 5687240032
151 6213998948
152 6787678742
153 7412277520
154 8092165156
155 8832026707
156 9636977188
157 10512501148
158 11464580655
159 12499631422
160 13624643205
161 14847114332
162 16175206308
163 17617674725
164 19184041532
165 20884522895
166 22730218540
167 24733038989
168 26905914299
169 29262718472
170 31818502037
171 34589414646
172 37592961123
173 40847925291
174 44374652694
175 48194973530
176 52332517651
177 56812638095
178 61662758549
179 66912301554
180 72593072718
181 78739191582
182 85387519870
183 92577597430
184 100352115448
185 108756862800
186 117841250192
187 127658265480
188 138265058086
189 149722906877
190 162097867184
191 175460758556
192 189887882471
193 205461029340
194 222268279276
195 240404033949
196 259969904654
197 281074778860
198 303835806855
199 328378504104
200 354837852721
201 383358447943
202 414095721778
203 447216147259
204 482898599784
205 521334622836
206 562729948837
207 607304838866
208 655295774697
209 706955891311
210 762556861878
211 822389431103
212 886765522337
213 956018890113
214 1030507467694
215 1110614165209
216 1196749487861
217 1289352493984
218 1388893723556
219 1495876343327
220 1610839413273
221 1734359255620
222 1867053101638
223 2009580708683
224 2162648441118
225 2327011174812
226 2503476853620
227 2692908733256
228 2896230472415
229 3114428754217
230 3348558985772
231 3599748354653
232 3869202197634
233 4158207564954
234 4468140341117
235 4800469376172
236 5156764459720
237 5538701101847
238 5948069448926
239 6386779816840
240 6856872664354
241 7360524967745
242 7900061391242
243 8477961621918
244 9096872864771
245 9759618282017
246 10469210974994
247 11228863660336
248 12042004330890
249 12912287338252
250 13843610915781
251 14840129870401
252 15906275194002
253 17046768558121
254 18266644279543
255 19571265859255
256 20966350562652
257 22457988287208
258 24052669073344
259 25757304581636
260 27579258901544
261 29526372979719
262 31606999095738
263 33830028640364
264 36204930698377
265 38741783579725
266 41451318017532
267 44344952934369
268 47434843775433
269 50733923067289
270 54255954498903
271 58015578847710
272 62028374510376
273 66310909473508
274 70880809024517
275 75756814545172
276 80958859253107
277 86508134632068
278 92427175173880
279 98739933394495
280 105471874597453
281 112650061558739
282 120303260491215
283 128462036545266
284 137158872311923
285 146428275463748
286 156306911220077
287 166833723632903
288 178050083645562
289 189999925631049
290 202729912888253
291 216289591276248
292 230731574124770
293 246111715049000
294 262489314527257
295 279927314140531
296 298492527354696
297 318255857741640
298 339292556703861
299 361682468559353
300 385510318312503
301 410865986722189
302 437844831605798
303 466547996427750
304 497082768916549
305 529562927147752
306 564109139742810
307 600849353768089
308 639919241297608
309 681462634006340
310 725632021302644
311 772589037083926
312 822505015295576
313 875561534814090
314 931951038981126
315 991877445325312
316 1055556836220521
317 1123218140950584
318 1195103905512233
319 1271471055232268
320 1352591752664794
321 1438754249967805
322 1530263844689454
323 1627443832180477
324 1730636570228195
325 1840204542767973
326 1956531545574769
327 2080023873874464
328 2211111642477836
329 2350250111330240
330 2497921155032267
331 2654634741739309
332 2820930568692756
333 2997379711670800
334 3184586444780292
335 3383190079595670
336 3593866989546568
337 3817332659774116
338 4054343938706722
339 4305701322062067
340 4572251456436024
341 4854889683477048
342 5154562823104391
343 5472272006479257
344 5809075769495003
345 6166093206378648
346 6544507407149194
347 6945568967172142
348 7370599806011863
349 7820997071804509
350 8298237382988830
351 8803881170657823
352 9339577388804119
353 9907068342484321
354 10508194917200855
355 11144901945529142
356 11819244011687936
357 12533391415016115
358 13289636611411494
359 14090400838302071
360 14938241261286441
361 15835858331759788
362 16786103714350389
363 17791988456021065
364 18856691777492292
365 19983570141001233
366 21176166997776726
367 22438222850427934
368 23773686058226890
369 25186724000309577
370 26681735050747733
371 28263360959907184
372 29936500123108116
373 31706321309299184
374 33578278360026075
375 35558125408180458
376 37651933157715540
377 39866105750099204
378 42207398790938820
379 44682938037607965
380 47300239356137857
381 50067229421570456
382 52992267806836114
383 56084169907174077
384 59352231383601895
385 62806253543918359
386 66456570386227343
387 70314076693057052
388 74390257944908383
389 78697221410307752
390 83247729227064105
391 88055232799315714
392 93133909374508612
393 98498700090345699
394 104165350408141102
395 110150452187445819
396 116471488373146321
397 123146879513116115
398 130196033136617299
399 137639395172505787
400 145498504499865378
401 153796049770462876
402 162555929661120558
403 171803315654009686
404 181564718573435338
405 191868057933324567
406 202742735398613845
407 214219711370338870
408 226331586075983769
409 239112684128679035
410 252599144021111877
411 266829011468977317
412 281842338159161539
413 297681284768185048
414 314390229900026469
415 332015883757708668
416 350607408298772381
417 370216542635236396
418 390897735535272259
419 412708283733012969
420 435708478016489321
421 459961755744127432
422 485534861881023425
423 512498017146779777
424 540925095494753292
425 570893809455710388
426 602485905701364820
427 635787369300330069
428 670888639167714185
429 707884833117854028
430 746875985176212074
431 787967293497150036
432 831269381707027505
433 876898571955171544
434 924977172667772518
435 975633779220747065
436 1029003590713275460
437 1085228740992405531
438 1144458647307765991
439 1206850374680229772
440 1272569019575592277
441 1341788110898680929
442 1414690032124522616
443 1491466462515281340
444 1572318841478385616
445 1657458853947727252
446 1747108941099924732
447 1841502834219582036
448 1940886116298732022
449 2045516809119407155
450 2155665990694152249
451 2271618440749452648
452 2393673319438098964
453 2522144876901549116
454 2657363199199989844
455 2799674988171925543
456 2949444381093091826
457 3107053807639981357
458 3272904890406173221
459 3447419386421985943
460 3631040176329298931
461 3824232298614354157
462 4027484035979461193
463 4241308051213747640
464 4466242580105086592
465 4702852678714917972
466 4951731533050558609
467 5213501828428570357
468 5488817187087936209
469 5778363671326777232
470 6082861361284913297
471 6403066004633845696
472 6739770747898751862
473 7093807946676551916
474 7466051065116508875
475 7857416661942669111
476 8268866474074905036
477 8701409595155546250
478 9156104760776788612
479 9634062737763992385
480 10136448830097970389
481 10664485498898312408
482 11219455109898479729
483 11802702805920516637
484 12415639518687632922
485 13059745117596490813
486 13736571710756934848
487 14447747096061872336
488 15194978378638342082
489 15980055752610893169
490 16804856464646291114
491 17671348957417475578
492 18581597211651420132
493 19537765285143277140
494 20542122068688576798
495 21597046257599403416
496 22705031560136684408
497 23868692141859881580
498 25090768328704036427
499 26374132568172687387
500 27721795673048034728
501 29136913347448489120
502 30622793021343038193
503 32182900993863574128
504 33820869913355049666
505 35540506595086173413
506 37345800206532343770
507 39240930821809611224
508 41230278377289243018
509 43318432030720076583
510 45510199958159945834
511 47810619591886754029
512 50224968336038460036
513 52758774764096831876
514 55417830337595330012
515 58208201651232331504
516 61136243246594635396
517 64208611000865665852
518 67432276135768033100
519 70814539854443329581
520 74363048654793320151
521 78085810328474520133
522 81991210697588350684
523 86088031099916144706
524 90385466678534499062
525 94893145488497441789
526 99621148480502838612
527 104580030376277148137
528 109780841499984510325
529 115235150582663566304
530 120955068608731235530
531 126953273724063813056
532 133243037279790595140
533 139838251034091983408
534 146753455591619529344
535 154003870105902052152
536 161605423330269528027
537 169574786046043303830
538 177929404959894767536
539 186687538102862504228
540 195868291829787178711
541 205491659455774979339
542 215578561635847884844
543 226150888528920517954
544 237231543860234797405
545 248844490928383880063
546 261014800679642886184
547 273768701901222781310
548 287133633665431423254
549 301138300082374252104
550 315812727503167469364
551 331188324237910349101
552 347297942941151319666
553 364175945736347563112
554 381858272243668947588
555 400382510590587926701
556 419787971582131601938
557 440115766118950329504
558 461408886053578625031
559 483712288582580655938
560 507072984379529119789
561 531540129576937843021
562 557165121817814555119
563 584001700496373320507
564 612106051425518351385
565 641536916063120527668
566 672355705552992828651
567 704626619726214673820
568 738416771338446767144
569 773796315703786577337
570 810838586022088239871
571 849620234576562159100
572 890221380121556242389
573 932725761655072787451
574 977220898920714929234
575 1023798259852983057276
576 1072553435337355555092
577 1123586321520189924992
578 1177001310068751087572
579 1232907486639407296906
580 1291418837985455717976
581 1352654467987702100018
582 1416738823072865673202
583 1483801927330254436877
584 1553979627828070986001
585 1627413850469530181132
586 1704252866929310324267
587 1784651573042907434591
588 1868771779231664912995
589 1956782513371290885495
590 2048860336732254500304
591 2145189673438198598327
592 2245963154119992364849
593 2351381974253263098615
594 2461656267910150488830
595 2577005497458460001268
596 2697658859996311201240
597 2823855711104721258301
598 2955846006768115678969
599 3093890764098762000496
600 3238262541781904602840
601 3389245940935774836695
602 3547138127375358095098
603 3712249376037262313561
604 3884903638632384419307
605 4065439135352336415297
606 4254208971780290537374
607 4451581781906690920204
608 4657942398491131832890
609 4873692551751671831771
610 5099251597720700555530
611 5335057277336352091453
612 5581566507714124136415
613 5839256206762859789928
614 6108624152703676629222
615 6390189879759192584550
616 6684495611694570468257
617 6992107234589658812380
618 7313615310656391530192
619 7649636134602066328032
620 8000812834495823950056
621 8367816518770451522980
622 8751347471471303041096
623 9152136397527003702606
624 9570945720320382387244
625 10008570933488740801559
626 10465842009411747811444
627 10943624866483349165662
628 11442822897820015282911
629 11964378563682934153351
630 12509275050475786644847
631 13078537998791946294154
632 13673237303598593748082
633 14294488989244026281340
634 14943457162619296350994
635 15621356047390465781008
636 16329452102895411206842
637 17069066230870405786732
638 17841576073883935165640
639 18648418408912332763594
640 19491091640240507039107
641 20371158395413827422440
642 21290248228754260487757
643 22250060436482142100987
644 23252366988312441943426
645 24299015579907932135508
646 25391932811441796775809
647 26533127497020944066486
648 27724694110636295395999
649 28968816373790141771137
650 30267770990913049269300
651 31623931538151554748986
652 33039772512120275877309
653 34517873544665785689000
654 36060923790754629940059
655 37671726496036606474437
656 39353203751755047992173
657 41108401444099590488399
658 42940494406276223490920
659 44852791780978342203160
660 46848742602183686200349
661 48931941604596381096916
662 51106135270359812997487
663 53375228122045975938181
664 55743289272302474151645
665 58214559239904252451445
666 60793457043405465073365
667 63484587582939230513032
668 66292749322238310489711
669 69222942282288959383288
670 72280376359636813713780
671 75470479981690467203573
672 78798909113060833058178
673 82271556626289525306816
674 85894562052102732409197
675 89674321723631307661885
676 93617499330917049421554
677 97731036901319603890668
678 102022166223419063860279
679 106498420731295216583459
680 111167647868152336470926
681 116038021947536938244608
682 121118057532597389007079
683 126416623353107036903996
684 131942956782293991514868
685 137706678894789458096743
686 143717810129455065080269
687 149986786580116212925292
688 156524476939811535835003
689 163342200123435243192336
690 170451743596374445195253
691 177865382436012819904474
692 185595899155848052373449
693 193656604321244892677149
694 202061357988881440168400
695 210824592001228964654055
696 219961333170610337886253
697 229487227386676561163868
698 239418564684524791044076
699 249772305309990968054744
700 260566106822223971962082
701 271818352272977446406580
702 283548179505830371864521
703 295775511617900815535375
704 308521088630605538350608
705 321806500415400477193417
706 335654220924651615151160
707 350087643777202710237054
708 365131119252660611319196
709 380809992747876601127775
710 397150644753810907521341
711 414180532410472473610482
712 431928232702604792152610
713 450423487358348214452300
714 469697249518374192449654
715 489781732242609234307288
716 510710458927235426514315
717 532518315704347964014416
718 555241605902542005691494
719 578918106646475703202745
720 603587127679690652441921
721 629289572494836987733144
722 656068001862048613033065
723 683966699846182635486011
724 713031742410621890226345
725 743311068705423138914708
726 774854555144988756675732
727 807714092380652104312528
728 841943665281398214575238
729 877599436036296940308356
730 914739830500520758314786
731 953425627907334177609905
732 993720054077229252868697
733 1035688878256073113405412
734 1079400513723444670316872
735 1124926122313224304919168
736 1172339722998368470716850
737 1221718304692903593763365
738 1273141943434633679415871
739 1326693924113396540684110
740 1382460866920793246978272
741 1440532858698917699533935
742 1501003589377372771709947
743 1563970493689749742568376
744 1629534898373219606924595
745 1697802175057091385887209
746 1768881899059422504069658
747 1842888014313319292506465
748 1919939004658602427473150
749 2000158071737444728071033
750 2083673319747483851851790
751 2170617947309260436382502
752 2261130446720641216903229
753 2355354810874688301480815
754 2453440748134217744696656
755 2555543905460587714017456
756 2661826100112074098343038
757 2772455560232029177956199
758 2887607174665939481338193
759 3007462752351925590973059
760 3132211291649321881294090
761 3262049259976042330072368
762 3397180884146784574998139
763 3537818451810890773118772
764 3684182624411362452347032
765 3836502762094051825172752
766 3995017261020150440949919
767 4159973903543446266590732
768 4331630221739430979741446
769 4510253874782585475732208
770 4696123040695393946226292
771 4889526823002855159231410
772 5090765672855199532156537
773 5300151827192793519195345
774 5518009763557982919168914
775 5744676672171043140053488
776 5980502945920125454090051
777 6225852688928743288865508
778 6481104244399143315547936
779 6746650742444902764145005
780 7022900668663111718934866
781 7310278454212948270841440
782 7609225088206835208350516
783 7920198753238387091753392
784 8243675484913257494103258
785 8580149856268715737678407
786 8930135688012370107949520
787 9294166785532011336223597
788 9672797703676003152520796
789 10066604540327188358489655
790 10476185759843787805957519
791 10902163047466455637202374
792 11345182195844421753069886
793 11805914024861654018800963
794 12285055336001216332448289
795 12783329902516499082457748
796 13301489496738950012204706
797 13840314955885130586494673
798 14400617287790829122085462
799 14983238818036068009163656
800 15589054379993967632790735
801 16218972549375671874350993
802 16873936924917166632707037
803 17554927456896446231835912
804 18262961825247910860265425
805 18999096869087145552939132
806 19764430069542783014388505
807 20560101087842345091291848
808 21387293360687976387104471
809 22247235755012404002489036
810 23141204284300308714167387
811 24070523888719266124398863
812 25036570281405491884841938
813 26040771863313498523698074
814 27084611709146489123134597
815 28169629626953460583306130
816 29297424294093794310658427
817 30469655472344934469322773
818 31688046305051122966124700
819 32954385699292086193013096
820 34270530796181010090638498
821 35638409532488630409499768
822 37060023296929321054611134
823 38537449684539612041241698
824 40072845352727818962128969
825 41668448982675601129095375
826 43326584349930329169657462
827 45049663508137432238826299
828 46840190090030431493340590
829 48700762729915417837348368
830 50634078612066446891683056
831 52642937149576787612525252
832 54730243798402607408766742
833 56899014011474250089004257
834 59152377337954643586888797
835 61493581672873805187257414
836 63925997662586385198048965
837 66453123271660277190578040
838 69078588517036804864766013
839 71806160375476596460619167
840 74639747870553224948172235
841 77583407345643724432825105
842 80641347929629590061054896
843 83817937202223313381057196
844 87117707066117645802989828
845 90545359833371691879414403
846 94105774533748906720493264
847 97804013452955571005896823
848 101645328909049391404502118
849 105635170275539166743522493
850 109779191260038991468428992
851 114083257447610843328496241
852 118553454118294835142190659
853 123196094348617248191916729
854 128017727407256343409782922
855 133025147455358720831747184
856 138225402562414969625613404
857 143625804048939641056193232
858 149233936167644398519144108
859 155057666135154693372856404
860 161105154526793863798907118
861 167384866047347057681393472
862 173905580691222658256126173
863 180676405305846336227688263
864 187706785572661994351010027
865 195006518420562322247846436
866 202585764887146966788215400
867 210455063443687988858190792
868 218625343800296143482574543
869 227107941208298761177653304
870 235914611277495047757316333
871 245057545326509960484470892
872 254549386285166801770237754
873 264403245168394808509929973
874 274632718141933898313449629
875 285251904200738551454892989
876 296275423481778742131299706
877 307718436233622413184208883
878 319596662466033339821560740
879 331926402303554863275498188
880 344724557067956332856059574
881 358008651115209305149247952
882 371796854453627739962943000
883 386108006170653978360538555
884 400961638696804397678972352
885 416378002936197535031698152
886 432378094294188856541017175
887 448983679633610889320832514
888 466217325192292740913094075
889 484102425495577798282912231
890 502663233298812586290448206
891 521924890595899654800532701
892 541913460731345719405929154
893 562655961654436521807340332
894 584180400355598037026436131
895 606515808526289832143074415
896 629692279485300363004701498
897 653741006415692070155407480
898 678694321958270352157334766
899 704585739208926834355065110
900 731449994168942641153907240
901 759323089698918782860798404
902 788242341028852426318524825
903 818246422878571539242049618
904 849375418244716202833311361
905 881670868912268673225721892
906 915175827750742514477736395
907 949934912857083246291071562
908 985994363609582472989099127
909 1023402098699186738142876880
910 1062207776206982582164676129
911 1102462855798865135265759873
912 1144220663110958569576121718
913 1187536456401739218319896166
914 1232467495549544636646808866
915 1279073113476701714719123719
916 1327414790084422319590323611
917 1377556228785343575576548211
918 1429563435723700332543113778
919 1483504801776037012350245142
920 1539451187428684518710111494
921 1597476010631351567474261116
922 1657655337729720180883192262
923 1720067977583276689072672073
924 1784795578978386603932171414
925 1851922731450196081273371609
926 1921537069630972062653388285
927 1993729381246316097054655613
928 2068593718884985322586411096
929 2146227515672142418464572937
930 2226731704980441769815869803
931 2310210844317730822437327516
932 2396773243535037013427168218
933 2486531097503184975969530664
934 2579600623411606373162746527
935 2676102202847902055644941794
936 2776160528822281738259591073
937 2879904757906348561931565933
938 2987468667661632266949356013
939 3098990819538984948030374856
940 3214614727436285102230711024
941 3334489032107998781987724355
942 3458767681626899907354230069
943 3587610118104774169123101705
944 3721181470886133530171143232
945 3859652756435938143904280831
946 4003201085150004067398730861
947 4152009875324222410729368865
948 4306269074526907684834053401
949 4466175388626549819782354128
950 4631932518735980652009284734
951 4803751406342465926276386448
952 4981850486902550225004670217
953 5166455952189562359867622360
954 5357802021691623329521194414
955 5556131223367697665197649643
956 5761694684079822407255269414
957 5974752430030006522635436808
958 6195573697541589137961192210
959 6424437254535907340004148896
960 6661631733067168100388984865
961 6907455973290231904135307808
962 7162219379248856801872321360
963 7426242286884565164606351240
964 7699856344679986171891947799
965 7983404907363994313983644631
966 8277243443120560209828439146
967 8581739954757607602739540871
968 8897275415307730953773444172
969 9224244218547976225396243294
970 9563054644942475642884768280
971 9914129343528110240525684061
972 10277905830281057002884984062
973 10654837003519563687746210045
974 11045391676917143745965949994
975 11450055130719046133362912948
976 11869329681774946594228866105
977 12303735273020723061378075432
978 12753810083063593090087289607
979 13220111156546143604047055936
980 13703215055987608252411336351
981 14203718535823424286588671139
982 14722239239388427446573237349
983 15259416419613237857559259996
984 15815911684229315788601824420
985 16392409766303978242156066796
986 16989619320954296462072661511
987 17608273749116330306861193998
988 18249132049275598495900249847
989 18912979698094056330222807827
990 19600629560900227260373966158
991 20312922833040464276216751048
992 21050730013122748901839902023
993 21814951909217850200097698247
994 22606520679118288390971640658
995 23426400905791183583743507778
996 24275590709199024595338258234
997 25155122895700395008349674004
998 26066066146283131332701871648
999 27009526244922910915121653754
1000 27986647348403348799755560496