0 1
1 1
2 1
3 3
4 3
5 6
6 8
7 12
8 16
9 23
10 32
11 42
12 58
13 75
14 102
15 131
16 173
17 220
18 288
19 363
20 466
21 587
22 743
23 929
24 1164
25 1448
26 1797
27 2224
28 2738
29 3368
30 4122
31 5042
32 6133
33 7466
34 9035
35 10941
36 13184
37 15888
38 19064
39 22876
40 27343
41 32671
42 38915
43 46317
44 54981
45 65208
46 77156
47 91195
48 107586
49 126758
50 149106
51 175163
52 205479
53 240709
54 281635
55 329055
56 384034
57 447586
58 521115
59 605915
60 703850
61 816547
62 946437
63 1095643
64 1267260
65 1464041
66 1689962
67 1948565
68 2244904
69 2583592
70 2970979
71 3413058
72 3917838
73 4493027
74 5148680
75 5894771
76 6743834
77 7708687
78 8805029
79 10049214
80 11460844
81 13060794
82 14873450
83 16925335
84 19246863
85 21871513
86 24837162
87 28186050
88 31965223
89 36227737
90 41032126
91 46444728
92 52538256
93 59395554
94 67106766
95 75775013
96 85512096
97 96445915
98 108714942
99 122477608
100 137905076
101 155193101
102 174553190
103 196226574
104 220474192
105 247592966
106 277904213
107 311772669
108 349593685
109 391814362
110 438920349
111 491459112
112 550026131
113 615290691
114 687982138
115 768917286
116 858988013
117 959190153
118 1070612477
119 1194467358
120 1332082323
121 1484931253
122 1654630312
123 1842969467
124 2051913172
125 2283632560
126 2540512494
127 2825183009
128 3140535255
129 3489751990
130 3876333057
131 4304125570
132 4777361179
133 5300684516
134 5879205329
135 6518525460
136 7224806879
137 8004798444
138 8865922590
139 9816300852
140 10864863201
141 12021373416
142 13296562260
143 14702155329
144 16251033535
145 17957263432
146 19836289685
147 21904970669
148 24181804678
149 26686975428
150 29442616209
151 32472867242
152 35804183770
153 39465410689
154 43488136750
155 47906794605
156 52759066750
157 58086015947
158 63932550524
159 70347594746
160 77384617263
161 85101854338
162 93562909132
163 102837037677
164 112999829766
165 124133573190
166 136328022527
167 149680861800
168 164298573125
169 180297014499
170 197802404180
171 216952037893
172 237895400646
173 260795053517
174 285827891708
175 313186228103
176 343079222507
177 375734198490
178 411398264779
179 450339909975
180 492850847330
181 539247929244
182 589875255006
183 645106459589
184 705347121506
185 771037491064
186 842655249343
187 920718739809
188 1005790142217
189 1098479287742
190 1199447311324
191 1309411145540
192 1429147734627
193 1559499303202
194 1701378233430
195 1855773227171
196 2023754951907
197 2206483235589
198 2405213614598
199 2621305705869
200 2856230817127
201 3111581671579
202 3389081251314
203 3690594079885
204 4018136508931
205 4373889776369
206 4760211985511
207 5179653199790
208 5634969385124
209 6129139845257
210 6665383453805
211 7247178758803
212 7878282887635
213 8562754710983
214 9304976841614
215 10109682311355
216 10981980163932
217 11927386141767
218 12951852455898
219 14061803068069
220 15264168283163
221 16566425305401
222 17976638412037
223 19503505535379
224 21156404896025
225 22945448491200
226 24881536166045
227 26976417026229
228 29242752087631
229 31694184749301
230 34345413336250
231 37212271956223
232 40311814405326
233 43662406935344
234 47283825225072
235 51197360771232
236 55425932880572
237 59994210670906
238 64928742277759
239 70258094750742
240 76013003003180
241 82226530177951
242 88934239235812
243 96174376763259
244 103988070454735
245 112419539774568
246 121516323072493
247 131329518950884
248 141914047285217
249 153328925728444
250 165637569448626
251 178908107845052
252 193213728512461
253 208633039905463
254 225250465813186
255 243156660551609
256 262448961034569
257 283231862012155
258 305617533833922
259 329726366235822
260 355687561013052
261 383639754081721
262 413731693466295
263 446122950725953
264 480984696117884
265 518500511933586
266 558867278327279
267 602296102875545
268 649013332303239
269 699261614557741
270 753301053769950
271 811410423267063
272 873888483458538
273 941055366764315
274 1013254080667493
275 1090852088391158
276 1174243022391720
277 1263848487728031
278 1360120014669279
279 1463541115372048
280 1574629507988664
281 1693939461384654
282 1822064327500188
283 1959639213350496
284 2107343863287277
285 2265905702798809
286 2436103117702375
287 2618768920172161
288 2814794078162529
289 3025131660606443
290 3250801077406351
291 3492892568297521
292 3752572021512306
293 4031086079275152
294 4329767612231935
295 4650041523911644
296 4993430968095004
297 5361563945370194
298 5756180361792184
299 6179139522764253
300 6632428144181389
301 7118168862299068
302 7638629322969299
303 8196231841541147
304 8793563711810849
305 9433388167255959
306 10118656069635389
307 10852518342041011
308 11638339217630217
309 12479710336859765
310 13380465759704980
311 14344697943977754
312 15376774750429475
313 16481357546377240
314 17663420462301886
315 18928270896053153
316 20281571312107642
317 21729362456432976
318 23278088026517736
319 24934620945771048
320 26706291273857609
321 28600915933466300
322 30626830276680744
323 32792921706209744
324 35108665365799061
325 37584162152961809
326 40230179060018137
327 43058192137450222
328 46080432077519095
329 49309932756916425
330 52760582728692129
331 56447180050478156
332 60385490433092505
333 64592309148110703
334 69085526673734274
335 73884198573443972
336 79008619583603687
337 84480402464256102
338 90322561589206005
339 96559601893048840
340 103217613154246291
341 110324370300138363
342 117909439719433962
343 126004292340588102
344 134642423473339119
345 143859480248433010
346 153693396669971865
347 164184537197471312
348 175375848895243806
349 187313023153141043
350 200044667047747660
351 213622485439757068
352 228101473916744222
353 243540123775113299
354 260000639200059498
355 277549167941216843
356 296256045704740181
357 316196055669204599
358 337448703420884359
359 360098508833291404
360 384235315275455084
361 409954617798724874
362 437357910792985307
363 466553056894574118
364 497654677761644095
365 530784568641855999
366 566072137493065732
367 603654870734460575
368 643678826557907849
369 686299158040077887
370 731680667179777141
371 779998392277901915
372 831438230006858641
373 886197594777772503
374 944486117007458898
375 1006526383099626645
376 1072554719032089078
377 1142822020590009035
378 1217594632464293569
379 1297155279501159574
380 1381804052692923936
381 1471859453464512007
382 1567659499262976624
383 1669562894301005393
384 1777950268929007449
385 1893225491813311481
386 2015817058919843796
387 2146179563840767123
388 2284795254049404766
389 2432175678021595124
390 2588863428460906341
391 2755433987010813723
392 2932497676418659713
393 3120701726028844868
394 3320732457377809286
395 3533317596321749746
396 3759228719364297253
397 3999283841233412992
398 4254350152367708690
399 4525346914052153144
400 4813248520961599407
401 5119087739628133109
402 5443959133802940600
403 5789022686098674189
404 6155507628223633279
405 6544716490168556687
406 6958029382135856078
407 7396908520668945953
408 7862903014399703595
409 8357653922103141832
410 8882899600273483351
411 9440481354292153628
412 10032349412379107349
413 10660569237952179971
414 11327328201760150785
415 12034942631159013489
416 12785865260291949911
417 13582693100499366592
418 14428175757352980331
419 15325224215839279644
420 16276920122980216196
421 17286525591882501142
422 18357493559688188473
423 19493478726180529954
424 20698349109018614357
425 21976198245453488318
426 23331358080345713135
427 24768412573806368259
428 26292212072513615603
429 27907888481906798811
430 29620871287962700144
431 31436904470098581489
432 33362064359019900126
433 35402778485909720536
434 37565845482404738884
435 39858456083171214445
436 42288215296714239727
437 44863165802282092961
438 47591812645304350417
439 50483149295969901038
440 53546685150875845550
441 56792474549866411175
442 60231147396237929376
443 63873941460800288625
444 67732736467044073411
445 71820090047219201103
446 76149275676569221176
447 80734322685883803284
448 85590058470620398506
449 90732153008273283078
450 96177165814362301751
451 101942595461509287004
452 108046931805335277988
453 114509711055839921905
454 121351573852719576598
455 128594326499037030615
456 136261005527924726251
457 144375945774197852460
458 152964852143453410982
459 162054875269879421028
460 171674691275080984765
461 181854585840582338585
462 192626542828067429677
463 204024337683745392574
464 216083635884907174989
465 228842096691308285517
466 242339482485922720427
467 256617773996739555029
468 271721291713355992474
469 287696823822135781132
470 304593761005922503151
471 322464238467539066264
472 341363285558632403369
473 361348983412272641051
474 382482631000111951306
475 404828920055768810031
476 428456119328561389684
477 453436268656994072721
478 479845383373924537355
479 507763669585496790911
480 537275750888516447760
481 568470907126460273579
482 601443325807016392605
483 636292366845413709881
484 673122841320681910271
485 712045304979734470182
486 753176367247300898774
487 796639016554441781568
488 842562962821896077343
489 891084997996750895210
490 942349375564984800641
491 996508210032847423894
492 1053721897394826393350
493 1114159557685201352688
494 1177999500735960211938
495 1245429716352616725530
496 1316648390146538867810
497 1391864446361423538747
498 1471298119060262125776
499 1555181553149210380351
500 1643759436745567810063
501 1737289666518980601541
502 1836044047668370016435
503 1940309030331713651645
504 2050386484262360992330
505 2166594513753825424168
506 2289268314835414397743
507 2418761076923897401266
508 2555444931161491727415
509 2699711947848897853873
510 2851975185432735736456
511 3012669793701889603076
512 3182254173904470862541
513 3361211198710094805372
514 3550049495007124027689
515 3749304792756588029827
516 3959541343198489955147
517 4181353409958651018228
518 4415366836688786773338
519 4662240695146697093472
520 4922669017720206007363
521 5197382618695932404618
522 5487151008684764302602
523 5792784406938218552743
524 6115135856416785950538
525 6455103446820221699509
526 6813632650935096807048
527 7191718780032206568211
528 7590409564212746940841
529 8010807864009876437164
530 8454074519742404119559
531 8921431345557601395435
532 9414164275317201768793
533 9933626667955821529046
534 10481242780188454904972
535 11058511414956328192599
536 11667009754281990872236
537 12308397385757339626266
538 12984420532208221538665
539 13696916494675303059867
540 14447818319213739427810
541 15239159698656740244975
542 16073080120898921063074
543 16951830275947963278065
544 17877777734457356934475
545 18853412911199665438184
546 19881355327463432905191
547 20964360187161875408509
548 22105325282031210369171
549 23307298242164539099446
550 24573484148790131062623
551 25907253527139285339625
552 27312150737992876688415
553 28791902787506012704872
554 30350428575743720408800
555 31991848605451123454002
556 33720495173513928111685
557 35540923068742751369293
558 37457920800656104017258
559 39476522385209359790498
560 41602019714578277904858
561 43839975539481298814052
562 46196237093818001574536
563 48676950392889176479378
564 51288575237902004493410
565 54037900961074514902335
566 56932062947250556887733
567 59978559969680976118126
568 63185272379398129343547
569 66560481189501509783769
570 70112888097634656239532
571 73851636491983991734452
572 77786333488301706623635
573 81927073047680054775995
574 86284460227204597654290
575 90869636618030551998570
576 95694307028076463275880
577 100770767469155654212615
578 106111934511288993405907
579 111731376069798344059337
580 117643343694001240975377
581 123862806429434872328700
582 130405486329083807494153
583 137287895692469467361012
584 144527376115360393554153
585 152142139436548586861572
586 160151310672424930641749
587 168574973034105013522252
588 177434215126565686500264
589 186751180433635377963871
590 196549119197849164578312
591 206852442808962041712462
592 217686780820581611430382
593 229079040719602605227133
594 241057470579337428515894
595 253651724732939630948208
596 266892932610521100796740
597 280813770889594800916692
598 295448539115923080496754
599 310833238958662399263821
600 327005657271844361838348
601 344005453141679935514102
602 361874249108085175859921
603 380655726756971571657249
604 400395726889584746327612
605 421142354484085551599388
606 442946088675209761033732
607 465859897987592449615680
608 489939361069965670333110
609 515242793188108387732350
610 541831378747116065790984
611 569769310125236819710272
612 599123933115368178985198
613 629965899283094111144798
614 662369325565248838720534
615 696411961446991433844730
616 732175364071851563987436
617 769745081654531844955290
618 809210845584217265992756
619 850666771622921260117005
620 894211570622981347165436
621 939948769206188207961843
622 987986940868374726810795
623 1038439947993404936253538
624 1091427195283757884635524
625 1147073895136921602137610
626 1205511345522146568339669
627 1266877220936213969274111
628 1331315877044468664793188
629 1398978669639753816036931
630 1470024288581936083993494
631 1544619107409591414978099
632 1622937549348145206192301
633 1705162470470367614248835
634 1791485560800753609505755
635 1882107764189903022851810
636 1977239717823803223522311
637 2077102212270756639331656
638 2181926673010917365286640
639 2291955664434794045515299
640 2407443417343033183805283
641 2528656381025069625318732
642 2655873801044249294945939
643 2789388323906536517897429
644 2929506629844353473205257
645 3076550095001227195964077
646 3230855484362158358117322
647 3392775676833794776456006
648 3562680423942955433903956
649 3740957143686717316869261
650 3928011751137422039087442
651 4124269527476620091771212
652 4330176029208295037153692
653 4546198039378905426592774
654 4772824562714827945023555
655 5010567866672102476683623
656 5259964570483736186727839
657 5521576784381900388605441
658 5795993301270662148283825
659 6083830843225422172124326
660 6385735365302187501332099
661 6702383419249543337987186
662 7034483579832552704124226
663 7382777936597572564362646
664 7748043654033571790682245
665 8131094603216209273581324
666 8532783068158656408315301
667 8954001530235699312503608
668 9395684534197486981846733
669 9858810639444768601372870
670 10344404460400459887278090
671 10853538799981919272066911
672 11387336880355630250605526
673 11946974675340826427830860
674 12533683349021484268482077
675 13148751805327588594696165
676 13793529353556400456684157
677 14469428495024032455180090
678 15177927836265878522108611
679 15920575134443695610508205
680 16698990480865404487342747
681 17514869628784315896556265
682 18369987471914535902369362
683 19266201680383191991552676
684 20205456501133847879561797
685 21189786730104629416323494
686 22221321863824055262172416
687 23302290438404175891874992
688 24435024564258085008302034
689 25621964665235307822979988
690 26865664431246457731228187
691 28168795993847399853896050
692 29534155334664121402980013
693 30964667936973555837809614
694 32463394691202519001452230
695 34033538065579192927401822
696 35678448553657575479762806
697 37401631410949108182692816
698 39206753693424138147528632
699 41097651611204743746268066
700 43078338211345038022591933
701 45153011404202881166851679
702 47326062348531651937256971
703 49602084211081678146649299
704 51985881317180114050659245
705 54482478709476676749452495
706 57097132132781014546619550
707 59835338463698702364063504
708 62702846604575496495948219
709 65705668862108638246958240
710 68850092831856447018201564
711 72142693810800320164650059
712 75590347761061528491876520
713 79200244848878062929208504
714 82979903583977394300281387
715 86937185585570660184615182
716 91080311002313799977415040
717 95417874614764960192610192
718 99958862650084561782536635
719 104712670340010351392426724
720 109689120254462197368272967
721 114898481444528097569430732
722 120351489430019680600055268
723 126059367068302332203626834
724 132033846342666031561526895
725 138287191110150126575455900
726 144832220850430949314586916
727 151682335459169607210336246
728 158851541131059144833244673
729 166354477379751905854505423
730 174206445243848398006483765
731 182423436730236701247852656
732 191022165548244010004450218
733 200020099190349714507105040
734 209435492417568641884195582
735 219287422210096101795384263
736 229595824246368063877107946
737 240381530976384418220045119
738 251666311357924534110746660
739 263472912327208303709263132
740 275825102078575240136204846
741 288747715230926734119423301
742 302266699961954148972942894
743 316409167194617338135313300
744 331203441923895673000638016
745 346679116775567468338772270
746 362867107892634658036591449
747 379799713249059651935156230
748 397510673494671209121355323
749 416035235439488915298229621
750 435410218290262272702936977
751 455674082756784407346667551
752 476867003150473185768345366
753 499030942602878693433301307
754 522209731537127486313003073
755 546449149530915814141118276
756 571797010715469103243319687
757 598303252860958612054878730
758 626020030305162720100009291
759 655001810888744955262428063
760 685305477067349797874258269
761 716990431377855356752722674
762 750118706443527608028055647
763 784755079710558220841436704
764 820967193116498149150982758
765 858825677899485392172677741
766 898404284765871848186535987
767 939780019642942968699920844
768 983033285252862839864405829
769 1028248028753826707679374854
770 1075511895704634877755148306
771 1124916390619574696324927944
772 1176557044391587753655713634
773 1230533588873263506912740461
774 1286950138917220322737586050
775 1345915382189963691848060221
776 1407542777086337141236055145
777 1471950759085254197648204631
778 1539262955901514310195035491
779 1609608411803208369895993237
780 1683121821479512313584528196
781 1759943773859592715514212067
782 1840221006299916172722341564
783 1924106669574502688867440147
784 2011760604120610791526828237
785 2103349628011021913288876983
786 2199047837143531736526902391
787 2299036918158484568481902324
788 2403506474616241747031214995
789 2512654366988378646947182909
790 2626687067039206512680344872
791 2745820027197930961144970577
792 2870278065546449946721553084
793 3000295767073469513167407467
794 3136117901872349926776255312
795 3277999860987889994042339346
796 3426208110646201347748080364
797 3581020665631911975098885564
798 3742727582608271680801104591
799 3911631474208298408467058299
800 4088048044759021326609844214
801 4272306648536122966073406884
802 4464750871482992896809707454
803 4665739137366349508413319594
804 4875645339380316284667200020
805 5094859498252115685877794939
806 5323788447945537688181994089
807 5562856550103003125540392363
808 5812506438413564006056308137
809 6073199794142506429608526179
810 6345418154108556857695752147
811 6629663752446972134596678911
812 6926460397551249573221973739
813 7236354385642748656201744681
814 7559915452476424759335091708
815 7897737764752050945112126796
816 8250440952864024198877279056
817 8618671186689020744062075605
818 9003102296179683838709857527
819 9404436938604090110990586837
820 9823407814345275336940548064
821 10260778933252491246643340834
822 10717346933616466568651797615
823 11193942455924632220321253663
824 11691431573639425300053894895
825 12210717283333274267041209075
826 12752741056608100336050126423
827 13318484456325003817844861190
828 13908970819771680852494331838
829 14525267011500883628852906132
830 15168485248683368799903998537
831 15839785001933114734029922851
832 16540374974681633691583784008
833 17271515164301793556958098758
834 18034519008310233812754606341
835 18830755619111039778127662651
836 19661652110882400443973445378
837 20528696022352341582991180034
838 21433437839359905220810991967
839 22377493621254158661400811708
840 23362547735345805462600220133
841 24390355703794754746416410113
842 25462747167492465803295245785
843 26581628971680039512445858209
844 27748988378232596896914563191
845 28966896409737287148739488092
846 30237511330697062407522683349
847 31563082271404967136617554257
848 32945953000254916313166994760
849 34388565850484607539791337920
850 35893465807585169318118592503
851 37463304763860228423083587817
852 39100845946875167844590506867
853 40808968528805291939382246410
854 42590672423970345093122449100
855 44449083282132207787643951369
856 46387457685433591958880389622
857 48409188557168057462772882137
858 50517810790896691472696032803
859 52717007108764236137853539491
860 55010614158218381723125586084
861 57402628856700292140287228835
862 59897214994253310030920330874
863 62498710104390159246740100770
864 65211632613967985473034603251
865 68040689283245246061238487543
866 70990782947735989867419177348
867 74067020573935492818619207076
868 77274721641467798522586296319
869 80619426864700537533664866111
870 84106907267386780167558657589
871 87743173624427750444258064888
872 91534486285405363330049471163
873 95487365395109937336824718856
874 99608601526887505977882341317
875 103905266745253164006092012304
876 108384726114863321425865725186
877 113054649673610933061751804580
878 117923024888305266816969571647
879 122998169612121984533993428096
880 128288745563761839564571185257
881 133803772349037650123180758841
882 139552642046421054515610968986
883 145545134378923498569981382194
884 151791432495561679985082572572
885 158302139386566993753100753380
886 165088294957443188537451478285
887 172161393787957291120203090594
888 179533403603167757187808365950
889 187216784484651728662200964688
890 195224508851192167319601465308
891 203570082239326602072645787382
892 212267564915344297846266865193
893 221331594351549094365258234519
894 230777408600883080205279576978
895 240620870605333098062798325932
896 250878493474920014617852691418
897 261567466775501353939691143529
898 272705683865103571772374411032
899 284311770320042760296238037167
900 296405113493694300655787937434
901 309005893252434960710987961236
902 322135113935007652717671156714
903 335814637583351790177637620052
904 350067218494803509436365976596
905 364916539147502471344069686933
906 380387247552848243438063760737
907 396504996090932175981164134433
908 413296481887033063725306053399
909 430789488789509812953723258990
910 449012931011754783422799746505
911 467996898503290843562964661271
912 487772704117606583614009870577
913 508372932646931307272857044367
914 529831491796857643986324316892
915 552183665176528983165603366256
916 575466167383024874295540027453
917 599717201261604540642093246270
918 624976517426610348906217370952
919 651285476131094352887461992547
920 678687111576615715285417355921
921 707226198758170239650041662847
922 736949322942859459971987277329
923 767904951884691541559063978193
924 800143510881833924719758559997
925 833717460786714499138080223751
926 868681379083598668629565962373
927 905092044152660797547919333189
928 943008522844125037039631801003
929 982492261490779829352286944286
930 1023607180492077600535691087916
931 1066419772608124305220608436039
932 1110999205107148031470490942216
933 1157417425915520489513027682524
934 1205749273925095705786638395006
935 1256072593618535997606666571150
936 1308468354179422517317633222237
937 1363020773260306441333714437974
938 1419817445588453871147095712893
939 1478949476595883609886211796743
940 1540511621267399279085087649650
941 1604602428407687482428343219997
942 1671324390536199515988127820981
943 1740784099626468094486389815725
944 1813092408914740875950584923945
945 1888364601011352796093282576964
946 1966720562557118140467540006350
947 2048284965676215466868762206306
948 2133187456486573374706271376215
949 2221562850938658352339625609127
950 2313551338263827669417336213456
951 2409298692324057306919427013460
952 2508956491165898168443392834480
953 2612682345092971289371239365996
954 2720640133583196244762497454158
955 2833000251389275734511904295621
956 2949939864173746112923201074923
957 3071643174043169077760424214409
958 3198301695359797568607675911401
959 3330114541223321246166663406608
960 3467288721030098558744527646787
961 3610039449532636992872596685923
962 3758590467838006671013530261858
963 3913174376800390283973840202250
964 4074032983280101744592966010066
965 4241417659759173949163206569661
966 4415589717822041356871167074292
967 4596820796028954625287954475415
968 4785393262729582521695373440502
969 4981600634384811616134742381490
970 5185748009986068758858844563160
971 5398152522183597997793439955183
972 5619143805758046102273563541273
973 5849064484093484401339003550229
974 6088270674334644864798385871371
975 6337132511936712796728466174421
976 6596034695342524926731878334905
977 6865377051549510139077730962765
978 7145575123357210605832965121982
979 7437060779115776435115683769395
980 7740282845826469607348338260228
981 8055707766476988554054944864533
982 8383820282527368398911642313907
983 8725124142496372272158079609422
984 9080142837633704271546596963280
985 9449420365700096454929392501773
986 9833522023915391867470498281566
987 10233035232174218356298847882520
988 10648570387669768322768806057964
989 11080761752108626605075190747556
990 11530268372743570512524899532182
991 11997775038496865557409915671615
992 12483993272493849702018530768380
993 12989662362375605036727292499884
994 13515550429810314996882546444865
995 14062455540675569036344423969849
996 14631206857438465913677481193458
997 15222665835316957678154204744224
998 15837727463864534770225281530658
999 16477321555681159695713534655500
1000 17142414084016383467309667054958