0 1
1 1
2 1
3 3
4 3
5 5
6 9
7 11
8 15
9 21
10 33
11 39
12 55
13 69
14 93
15 127
16 159
17 201
18 261
19 327
20 411
21 537
22 653
23 819
24 1011
25 1257
26 1529
27 1899
28 2331
29 2829
30 3441
31 4179
32 5031
33 6093
34 7305
35 8767
36 10575
37 12573
38 14997
39 17847
40 21223
41 25089
42 29757
43 35055
44 41379
45 48801
46 57285
47 67131
48 78795
49 92049
50 107553
51 125459
52 146163
53 169893
54 197529
55 229323
56 265599
57 307589
58 355521
59 410583
60 473751
61 545973
62 628173
63 722751
64 829935
65 952617
66 1092597
67 1251351
68 1431675
69 1637481
70 1870189
71 2134659
72 2434275
73 2773833
74 3157257
75 3592491
76 4082571
77 4637053
78 5263761
79 5968707
80 6763527
81 7660029
82 8667705
83 9801279
84 11076831
85 12508221
86 14116101
87 15920583
88 17943495
89 20209617
90 22751901
91 25595583
92 28776083
93 32335041
94 36312405
95 40753467
96 45716475
97 51250113
98 57425409
99 64309059
100 71980115
101 80519829
102 90034377
103 100613067
104 112382223
105 125469861
106 140007345
107 156151335
108 174082935
109 193973829
110 216040557
111 240510543
112 267625503
113 297664521
114 330936837
115 367760727
116 408503979
117 453580057
118 503406285
119 558478899
120 619336515
121 686528505
122 760708281
123 842586987
124 932894427
125 1032492381
126 1142293825
127 1263286227
128 1396566759
129 1543367757
130 1704945753
131 1882777935
132 2078419215
133 2293577757
134 2530106517
135 2790114375
136 3075754743
137 3389492289
138 3734001213
139 4112157615
140 4527115059
141 4982375217
142 5481608325
143 6028972731
144 6628929867
145 7286303777
146 8006381361
147 8794995795
148 9658324275
149 10603224741
150 11637169257
151 12768144411
152 14004970239
153 15357262917
154 16835230209
155 18450256103
156 20214622119
157 22141502325
158 24245399949
159 26542060095
160 29048392383
161 31782874233
162 34765661109
163 38018300439
164 41564484603
165 45429781305
166 49641789501
167 54230519427
168 59228745315
169 64671320265
170 70596695769
171 77046216699
172 84064411083
173 91699800957
174 100005052689
175 109036487955
176 118855774231
177 129529246269
178 141128556537
179 153731310975
180 167421782895
181 182290061901
182 198434519301
183 215961090375
184 234983830599
185 255626353953
186 278022366765
187 302315276287
188 328660904019
189 357227111169
190 388194611493
191 421758588555
192 458130355515
193 497536285185
194 540221815617
195 586451335635
196 636508975779
197 690701803605
198 749361058185
199 812842179723
200 881529402207
201 955836565749
202 1036207954929
203 1123123447911
204 1217099433975
205 1318690724373
206 1428495230205
207 1547157187023
208 1675367252127
209 1813870895625
210 1963469335829
211 2125022415399
212 2299456600299
213 2487768633561
214 2691026508237
215 2910381587715
216 3147069891027
217 3402418413945
218 3677853738105
219 3974909751723
220 4295229602859
221 4640581989357
222 5012864574017
223 5414112921555
224 5846513479335
225 6312414901149
226 6814331685609
227 7354967319375
228 7937220578895
229 8564198429277
230 9239235626469
231 9965909928663
232 10748050021431
233 11589769420161
234 12495473804349
235 13469882703807
236 14518056562563
237 15645420778353
238 16857779277189
239 18161357861499
240 19562822954139
241 21069309675825
242 22688463408369
243 24428471828115
244 26298091129395
245 28306704449205
246 30464352242937
247 32781772380571
248 35270463707967
249 37942728574917
250 40811719554321
251 43891513164855
252 47197167058983
253 50744772801333
254 54551546344077
255 58635896203215
256 63017489618895
257 67717360182009
258 72757990899189
259 78163392063639
260 83959237157707
261 90172952826825
262 96833828822013
263 103973161777923
264 111624384358947
265 119823180711321
266 128607675630249
267 138018570486267
268 148099307951883
269 158896272406653
270 170458981876449
271 182840256363939
272 196096490045655
273 210287852233149
274 225478521646329
275 241736980034703
276 259136286977151
277 277754327208717
278 297674205712389
279 318984525774471
280 341779749724119
281 366160599771441
282 392234466125805
283 420115773724671
284 449926524069075
285 481796724228369
286 515864890194741
287 552278630164043
288 591195224898171
289 632782168906113
290 677217931780113
291 724692583455651
292 775408519034403
293 829581295619733
294 887440446176457
295 949230293851419
296 1015210994947695
297 1085659474747701
298 1160870442071217
299 1241157595153383
300 1326854776783047
301 1418317146460133
302 1515922668278973
303 1620073442544207
304 1731197157463071
305 1849748807581017
306 1976212324483557
307 2111102297129895
308 2254966018044267
309 2408385426792153
310 2571979172515485
311 2746405040143443
312 2932362264704787
313 3130594011171321
314 3341890225735929
315 3567090439821819
316 3807086670377019
317 4062826864222125
318 4335318177120513
319 4625630502369939
320 4934900479374903
321 5264335463022381
322 5615217668988393
323 5988908993008719
324 6386855650908111
325 6810593211712557
326 7261752157774197
327 7742063608757655
328 8253365082714615
329 8797607304983361
330 9376860753065485
331 9993322775750799
332 10649325392336067
333 11347343306317617
334 12090002107206597
335 12880087770333579
336 13720555857496299
337 14614541572485489
338 15565370649135537
339 16576570627769811
340 17651882405120643
341 18795273438569349
342 20010950770167609
343 21303375076185435
344 22677275883894975
345 24137667349765141
346 25689864523740321
347 27339501701577783
348 29092550711359911
349 30955340496611253
350 32934578444219037
351 35037372324525855
352 37271253111060495
353 39644200484507193
354 42164668369613301
355 44841612330601191
356 47684519138196699
357 50703437392925385
358 53909009463449277
359 57312506693270211
360 60925865177663091
361 64761723729296553
362 68833465093831593
363 73155258391613307
364 77742103640860875
365 82609880449239885
366 87775397824682865
367 93256446903077667
368 99071857964962839
369 105241559283963261
370 111786639090146121
371 118729412695929759
372 126093491698121151
373 133903856926025421
374 142186937319311877
375 150970691338942743
376 160284692749021223
377 170160223238180337
378 180630368211015405
379 191730117437920575
380 203496474125883171
381 215968566944476833
382 229187768940188661
383 243197824758042891
384 258044982950398587
385 273778134861137937
386 290448964518559137
387 308112103204583331
388 326825293272949347
389 346649562820362645
390 367649408138286297
391 389892984598425579
392 413452312637197295
393 438403490195996277
394 464826917990867121
395 492807539206647543
396 522435089864862423
397 553804361271417573
398 587015482095314685
399 622174209952073295
400 659392240433572719
401 698787535204389225
402 740484665239041957
403 784615170598765479
404 831317945871419691
405 880739639924594985
406 933035078522796909
407 988367712812888787
408 1046910088987327059
409 1108844339993900409
410 1174362711909840585
411 1243668110054000907
412 1316974676439244539
413 1394508401630428077
414 1476507765156122625
415 1563224407530072867
416 1654923846592101447
417 1751886222952872045
418 1854407086770762729
419 1962798230881989135
420 2077388563282840671
421 2198525022409118397
422 2326573551205679157
423 2461920112141480983
424 2604971757090513015
425 2756157760223953105
426 2915930803347192093
427 3084768221003754447
428 3263173322212247811
429 3451676769567236145
430 3650838032069264277
431 3861246921636074715
432 4083525201842653035
433 4318328277470879793
434 4566346984871979249
435 4828309462817791971
436 5104983120345032595
437 5397176719112175429
438 5705742550470211065
439 6031578724777472091
440 6375631592606053263
441 6738898277229980517
442 7122429336467978593
443 7527331577339979063
444 7954770999300761895
445 8405975889817667973
446 8882240092332220269
447 9384926428668610335
448 9915470293071954063
449 10475383450301351097
450 11066258007579145413
451 11689770591392647095
452 12347686753234992411
453 13041865584898038729
454 13774264562442977853
455 14546944663164175251
456 15362075715830412675
457 16221942027763448553
458 17128948313084606313
459 18085625905124633787
460 19094639276296380507
461 20158792917818340957
462 21281038536241107825
463 22464482618372754339
464 23712394397400662679
465 25028214201284332749
466 26415562209751484889
467 27878247692934574047
468 29420278671775296639
469 31045872073522269453
470 32759464416846785493
471 34565723010702464871
472 36469557701515602279
473 38476133252957984049
474 40590882296366850861
475 42819518939156985807
476 45168053075155313523
477 47642805383499314273
478 50250423057219810741
479 52997896368698236107
480 55892576002405316811
481 58942191258881479521
482 62154869191364156385
483 65539154658947998179
484 69104031354902498787
485 72858943938207476325
486 76813821190775207529
487 80979100333346341227
488 85365752574557148783
489 89985309880210539381
490 94849893041299276737
491 99972241193887823559
492 105365742714783735831
493 111044467646472911013
494 117023201754005191677
495 123317482206179931935
496 129943634980252334847
497 136918814178491525097
498 144261043182258185061
499 151989257821146991335
500 160123351709377244283
501 168684223724818339257
502 177693827785234513773
503 187175225131447392723
504 197152639060407435027
505 207651512318934165705
506 218698567354581957465
507 230321869407972997131
508 242550892645528391739
509 255416589586402211565
510 268951463786113453137
511 283189646023341616563
512 298166974261792863111
513 313921077359813754285
514 330491462804971960041
515 347919608773550986527
516 366249060507194922159
517 385525531304159854077
518 405797008477564989237
519 427113864262877471703
520 449528972041450331847
521 473097828233917589217
522 497878679907851832285
523 523932658454864492559
524 551323919796833584131
525 580119791123064946497
526 610390924620670552101
527 642211458654077120859
528 675659186476958870187
529 710815732919980194225
530 747766739665354257921
531 786602059097282512179
532 827415957374296826131
533 870307327246534948869
534 915379910802011739897
535 962742532689299374827
536 1012509344582508314271
537 1064800080945738777573
538 1119740326889311039137
539 1177461798792559947447
540 1238102637984885111159
541 1301807718159272302101
542 1368728967515621074221
543 1439025705734231375007
544 1512864996806517309519
545 1590422018573517883017
546 1671880449390840596373
547 1757432872800613462455
548 1847281201450760090715
549 1941637120472033464521
550 2040722551616881534221
551 2144770139228725628707
552 2254023758662247611971
553 2368739048261720014185
554 2489183966477059456617
555 2615639374473710102475
556 2748399645871196990571
557 2887773305003290522653
558 3034083694542128884593
559 3187669673913837514467
560 3348886350514418986023
561 3518105844261173414877
562 3695718087570851126169
563 3882131662556129806047
564 4077774676540548818943
565 4283095677832025441565
566 4498564614176421252069
567 4724673834809118135591
568 4961939138663959642023
569 5210900871085748357553
570 5472125070555749950461
571 5746204667885241696927
572 6033760740971355577587
573 6335443826430387521697
574 6651935291328967513077
575 6983948768082549985371
576 7332231654459483639003
577 7697566681977685099425
578 8080773556491378600609
579 8482710672909012275811
580 8904276908069890464435
581 9346413495748401408309
582 9810105986386139160873
583 10296386295789018373611
584 10806334847546776119279
585 11341082811950108178117
586 11901814446424146811281
587 12489769542650329118535
588 13106245983771948867735
589 13752602417193737121189
590 14430261048987174063821
591 15140710563667014563439
592 15885509175726921069375
593 16666287819572157428073
594 17484753482343977391333
595 18342692686773617763639
596 19241975131552777568907
597 20184557494526939085945
598 21172487406598860298797
599 22207907605014129590163
600 23293060271894387645859
601 24430291567216837044825
602 25622056365751883051097
603 26870923205010701148939
604 28179579454260518437563
605 29550836715748868207037
606 30987636465787692691425
607 32493055947622460612979
608 34070314328005319527239
609 35722779126989386102125
610 37453972933703345754041
611 39267580422290044447983
612 41167455678175718623983
613 43157629849885885371837
614 45242319141569094786933
615 47425933158847692178407
616 49713083624117321848599
617 52108593479585651076129
618 54617506391277810226077
619 57245096673506472244047
620 59996879653088389923411
621 62878622489891620931601
622 65896355474309097267045
623 69056383824895929047067
624 72365300003547292725291
625 75829996573197653887233
626 79457679622453727336337
627 83255882778987831007539
628 87232481837815678260627
629 91395710034184113556869
630 95754173983802022540297
631 100316870322103025969211
632 105093203073931539034335
633 110093001781733924177445
634 115326540425926544040609
635 120804557175026783184903
636 126538274995305638867463
637 132539423160392086767381
638 138820259700696812697069
639 145393594829230034094687
640 152272815386770594666911
641 159471910354023681240729
642 167005497469868596876437
643 174888851006691891455031
644 183137930753987804651547
645 191769412257378417607065
646 200800718367956361347229
647 210250052162424908150691
648 220136431284818360300163
649 230479723774646742294825
650 241300685446850865343161
651 252620998884096079081435
652 264463314111857226088875
653 276851291032682323167453
654 289809643685822582072433
655 303364186414330401728883
656 317541882023052641159799
657 332370892005523693721757
658 347880628929552919917465
659 364101811078333124299551
660 381066519432914880633423
661 398808257099944651874733
662 417362011291360027203237
663 436764317955825830984679
664 457053329176709974833831
665 478268883459253918836033
666 500452579017714632802957
667 523647850194339954628767
668 547900047146067338834739
669 573256518926645149832865
670 599766700111021583269893
671 627482201116661493999147
672 656456902365291662391643
673 686747052451544396069601
674 718411370491911421680801
675 751511152817386284834675
676 786110384196580389491139
677 822275853785481671196981
678 860077275988126546895721
679 899587416439180534137579
680 940882223329098135916863
681 984040964280396714255573
682 1029146369013201513236049
683 1076284778047759185714759
684 1125546297680904593755479
685 1177024961503517039575029
686 1230818898739266958210461
687 1287030509671177001171439
688 1345766648458397070978687
689 1407138813656766883781097
690 1471263346746898198027701
691 1538261639007433934049351
692 1608260347089837913575243
693 1681391617634103320063097
694 1757793321309672880455213
695 1837609296678282011279139
696 1920989604266752093036467
697 2008090791277441697957529
698 2099076167387970504402009
699 2194116092072715204585675
700 2293388273933765470634571
701 2397078082542403129946445
702 2505378873287219510334369
703 2618492325769151892141555
704 2736628796315889339079623
705 2860007685166758910063101
706 2988857818944527058470601
707 3123417849049460954510127
708 3263936666606054132366895
709 3410673834646865527557309
710 3563900038257433343603013
711 3723897553382916260531511
712 3890960735077473598397079
713 4065396525998464477680609
714 4247524985947707264349917
715 4437679843325462580380255
716 4636209069411577207212387
717 4843475476365259555182033
718 5059857339929396171564325
719 5285749047854159473823259
720 5521561775058144231907323
721 5767724186620861559516241
722 6024683169761918893281873
723 6292904595938369355787059
724 6572874114305311405585683
725 6865097977822011517847637
726 7170103903293505079893977
727 7488441966730983571529787
728 7820685535487401760248671
729 8167432238604227668531365
730 8529304976940049610385009
731 8906952974699628268193751
732 9301052873997661997604423
733 9712309874202899051493141
734 10141458917898893294607213
735 10589265925281710148233007
736 11056529078973387223077807
737 11544080161294894430435801
738 12052785946064121359964501
739 12583549647122242207287159
740 13137312425902358958335403
741 13715054960342894489419689
742 14317799077639807189526685
743 14946609453414492028215075
744 15602595379905760863485955
745 16286912605966387907949177
746 17000765251773670258943817
747 17745407801169333879817755
748 18522147174765125790689643
749 19332344887062328744422429
750 20177419290877634185263681
751 21058847912577408490343619
752 21978169881782068663768503
753 22936988459221511219918301
754 23936973666686989209084633
755 24979865023170865935408303
756 26067474391343289135170463
757 27201688938777233424856941
758 28384474218522750795856485
759 29617877373677106283543719
760 30904030470909925598437623
761 32245153968090099937386897
762 33643560321242090146645965
763 35101657736381095992186591
764 36621954072006677900916915
765 38207060898113675961841521
766 39859697717947184977440405
767 41582696358975840063997611
768 43379005539660229183688667
769 45251695618993064756679393
770 47203963536067813357596081
771 49239137947052931802380099
772 51360684567390217731288579
773 53572211727348775821433845
774 55877476149204731506838889
775 58280388954813123527499195
776 60785021912672223412858575
777 63395613933765625349874261
778 66116577825986625537938961
779 68952507317355407063464071
780 71908184358419848673423271
781 74988586714839428331799173
782 78198895861568182559411101
783 81544505190301228423068399
784 85031028542482040690758719
785 88664309080675070602735161
786 92450428511348306066072133
787 96395716672863189192607815
788 100506761502973771255253643
789 104790419400483873371075001
790 109253825996469770911039869
791 113904407351114672978338995
792 118749891592523729482163187
793 123798321014803765148571609
794 129058064653321312787097945
795 134537831355515866712309979
796 140246683366559677867195035
797 146194050449960690599756173
798 152389744563625991259817377
799 158843975113028058480553395
800 165567364803896249986739223
801 172570966117460062603111437
802 179866278432391159702950537
803 187465265818588034537796207
804 195380375528505976825359663
805 203624557213109031077107405
806 212211282890487244147379157
807 221154567695977532918027703
808 230468991443983495920729303
809 240169721032933409673655905
810 250272533725551709543757037
811 260793841338289015658982831
812 271750715374971561506812131
813 283160913140743553086302609
814 295042904874043945031360037
815 307415901935902214881337259
816 320299886096791086474835467
817 333715639963323632694119121
818 347684778588584374154042769
819 362229782311196295471325875
820 377374030870261421030303331
821 393141838845218203766426085
822 409558492470917741729380761
823 426650287880692803025625787
824 444444570832099778732907807
825 462969777971660536271646837
826 482255479697441728225801281
827 502332424680665621778175191
828 523232586109168169566471815
829 544989209718542377895365653
830 567636863679181005915044925
831 591211490409519172716059583
832 615750460388873280553596015
833 641292628046164945414057305
834 667878389802928622536525653
835 695549744352674081895894663
836 724350355261645293673890747
837 754325615978656558492335465
838 785522717345489287561867677
839 817990717702904460424721763
840 851780615690042332740568467
841 886945425839437806972768393
842 923540257073616133091027721
843 961622394212529444786738459
844 1001251382605798712820194283
845 1042489116008115513286818093
846 1085399927819635303903123281
847 1130050685818634675300684931
848 1176510890518356409819888119
849 1224852777284113310050209117
850 1275151422352517894275814313
851 1327484852900098144249860735
852 1381934161313024124706914335
853 1438583623816262572425299373
854 1497520823626317372756945573
855 1558836778796883862969190967
856 1622626074933896670970979847
857 1688987002963094710686034641
858 1758021702138890464824657549
859 1829836308491379661131403359
860 1904541108915606516257573763
861 1982250701113648777415535681
862 2063084159608927159954110549
863 2147165208060296683195699755
864 2234622398110666130808115803
865 2325589295014716583999076913
866 2420204670299331004437325185
867 2518612701718429633671251139
868 2620963180774764184827911811
869 2727411728091285565131292149
870 2838120016923777020166015801
871 2953256005118415392466340107
872 3072994175829197114653076751
873 3197515787320217081981519829
874 3327009132191178049693193361
875 3461669806376897459484346839
876 3601700988282986947638262199
877 3747313728434538936461534277
878 3898727250028612535533900893
879 4056169260793867519043812527
880 4219876276577162693615925711
881 4390093957092184601839276233
882 4567077454279520001941425221
883 4751091773745477235791197511
884 4942412149764286420218094347
885 5141324434343950666309391241
886 5348125500876241284389601549
887 5563123662910166849499991923
888 5786639108606150369794387635
889 6019004351450093434419111321
890 6260564697827924835758829609
891 6511678732080697771173963435
892 6772718819685171039337447899
893 7044071629227991837510959693
894 7326138673863990008081055201
895 7619336872975944839953470147
896 7924099134779656161611575911
897 8240874960642402024782609229
898 8570131071913358862435269961
899 8912352060093171645257910447
900 9268041061197744378596670591
901 9637720455204215179927689117
902 10021932591499793518714855701
903 10421240541284233367967341943
904 10836228877914166983250595415
905 11267504486212817504175469233
906 11715697401803195201184568701
907 12181461681563318636287375791
908 12665476306342229115532837731
909 13168446117113047948061523729
910 13691102785785205562481912885
911 14234205821941462163296772091
912 14798543616808329990317995083
913 15384934525818018423894584337
914 15994227991169633435875156881
915 16627305705843880141280348163
916 17285082820581697021284313587
917 17968509195390953912499922917
918 18678570697198500809166033753
919 19416290545325670870707517051
920 20182730706526355080151786607
921 20978993341384465685011823493
922 21806222303936455005556193601
923 22665604696450680095667423831
924 23558372481361204785335141703
925 24485804152428257516679667429
926 25449226467272523070735560141
927 26450016243502037772410030655
928 27489602220734658423742081455
929 28569466990900637120815918617
930 29691148999291070395570198437
931 30856244618909536466424821655
932 32066410300776392704477181691
933 33323364802923796976561348649
934 34628891500922590574474439069
935 35984840782882633922554572531
936 37393132531968368655539295459
937 38855758699583810864866665801
938 40374785972494181707019424009
939 41952358537261093498644158043
940 43590700945494255337339892283
941 45292121083546317498654267069
942 47059013250401011134555718929
943 48893861347642567031727396675
944 50799242185533098670599762679
945 52777828909360286044345249005
946 54832394550371706074626330425
947 56965815705764457188593637247
948 59181076352350725549592295007
949 61481271798689007903611974317
950 63869612780640862624299310261
951 66349429705480389368317872135
952 68924177049872140357494134151
953 71597437917220265680891599633
954 74372928760078821006708467085
955 77254504273520406227690198895
956 80246162465568767736545409171
957 83352049911007604644277082945
958 86576467195108033633480961685
959 89923874554047184389379762731
960 93398897719020477553289888427
961 97006333971303985764340635201
962 100751158415778835091066850369
963 104638530480684034987798019523
964 108673800651645605515214394435
965 112862517448312299228026145093
966 117210434652210842224007619081
967 121723518794744598503861574027
968 126407956914572476795672845903
969 131270164593918195206376806997
970 136316794283703957131819390049
971 141554743927749026002561113063
972 146991165896620939241964382071
973 152633476242107572617322690629
974 158489364283661497944270979677
975 164566802538553373680345232703
976 170874057007891166860622303199
977 177419697831087020508907823625
978 184212610321779520966242752325
979 191262006398684681306364189447
980 198577436425318049912116572315
981 206168801473003618289881466649
982 214046366022098487015358910925
983 222220771116882765410949957363
984 230703047990086791974084171571
985 239504632173597041876314617129
986 248637378112455816655152324921
987 258113574299851039992606316779
988 267945958951418998272350650395
989 278147736237820471433690977869
990 288732593095191244195712366769
991 299714716633763539282414172691
992 311108812165656957928788926439
993 322930121873549948720536977933
994 335194444142708085889038444681
995 347918153579625423569064965823
996 361118221741319969633458049679
997 374812238600174069401590599517
998 389018434770068528612897160405
999 403755704520432555465406445943
1000 419043629605765570865356054311