0 1
1 1
2 2
3 3
4 4
5 6
6 8
7 11
8 13
9 21
10 23
11 33
12 39
13 54
14 63
15 88
16 98
17 132
18 157
19 200
20 237
21 303
22 356
23 440
24 526
25 643
26 767
27 931
28 1103
29 1317
30 1581
31 1860
32 2215
33 2615
34 3100
35 3631
36 4302
37 4999
38 5907
39 6865
40 8059
41 9322
42 10950
43 12613
44 14744
45 16988
46 19756
47 22694
48 26344
49 30192
50 34923
51 40001
52 46091
53 52672
54 60595
55 69116
56 79231
57 90305
58 103224
59 117447
60 134016
61 152186
62 173213
63 196578
64 223162
65 252852
66 286604
67 324193
68 366728
69 414393
70 467843
71 527874
72 595144
73 670477
74 754634
75 849333
76 954364
77 1072607
78 1203778
79 1351045
80 1514148
81 1697553
82 1899822
83 2127255
84 2378196
85 2659489
86 2969473
87 3317262
88 3699631
89 4127988
90 4599290
91 5125838
92 5704863
93 6351635
94 7061657
95 7853819
96 8723885
97 9692090
98 10755293
99 11937839
100 13234933
101 14675392
102 16256232
103 18008006
104 19930302
105 22058701
106 24391931
107 26972216
108 29802005
109 32925138
110 36349636
111 40126170
112 44264303
113 48822303
114 53817320
115 59310466
116 65328945
117 71942653
118 79183641
119 87132951
120 95836265
121 105377667
122 115820787
123 127262092
124 139776757
125 153475508
126 168456484
127 184836891
128 202744324
129 222312511
130 243690959
131 267034488
132 292531272
133 320346426
134 350713166
135 383823970
136 419949479
137 459313933
138 502247724
139 548995005
140 599957418
141 655420059
142 715845692
143 781571150
144 853149884
145 930955981
146 1015648642
147 1107670799
148 1207777951
149 1316495435
150 1434714536
151 1563027973
152 1702487588
153 1853796185
154 2018152381
155 2196394443
156 2389922438
157 2599695671
158 2827347214
159 3074017396
160 3341564272
161 3631344623
162 3945512443
163 4285632813
164 4654203092
165 5053081593
166 5485098198
167 5952461671
168 6458438648
169 7005582604
170 7597662782
171 8237696994
172 8929958282
173 9678018536
174 10486785695
175 11360396425
176 12304494342
177 13323950683
178 14425158737
179 15613848696
180 16897354172
181 18282304603
182 19777113718
183 21389545889
184 23129137684
185 25004980318
186 27027990952
187 29208668613
188 31559519559
189 34092787494
190 36822651411
191 39763369266
192 42931167592
193 46342473535
194 50015855652
195 53970375914
196 58227105383
197 62808154103
198 67737612231
199 73040877884
200 78745508944
201 84880855639
202 91478219796
203 98571487525
204 106196429124
205 114391886586
206 123198749121
207 132661730207
208 142827296661
209 153746891959
210 165473596720
211 178066209321
212 191585384373
213 206098593463
214 221674786969
215 238391321649
216 256326912518
217 275569807270
218 296209884184
219 318348085706
220 342086597215
221 367540832865
222 394827373899
223 424077590916
224 455424484055
225 489017959706
226 525009196497
227 563569147515
228 604870132110
229 649106400571
230 696474365769
231 747195145219
232 801491903081
233 859616270656
234 921822361170
235 988395609772
236 1059625316440
237 1135835807457
238 1217355565780
239 1304552912568
240 1397801454689
241 1497518416157
242 1604128648817
243 1718105352536
244 1839930477600
245 1970140564062
246 2109283081014
247 2257964996724
248 2416808022911
249 2586499543849
250 2767744166753
251 2961320032142
252 3168026488912
253 3388742816882
254 3624375554241
255 3875919078078
256 4144399604650
257 4430941367571
258 4736707008748
259 5062965455707
260 5411033411034
261 5782344142227
262 6178386517067
263 6600778919862
264 7051205784398
265 7531492019500
266 8043542658406
267 8589416556659
268 9171265199204
269 9791410761291
270 10452284098426
271 11156501141430
272 11906807317851
273 12706150806735
274 13557628482508
275 14464562030397
276 15430445670012
277 16459017968317
278 17554220098802
279 18720261098803
280 19961581289652
281 21282918151013
282 22689275329224
283 24185980086397
284 25778668641561
285 27473332885572
286 29276315416196
287 31194353846718
288 33234586303336
289 35404582595826
290 37712373336790
291 40166464581528
292 42775882981903
293 45550184161541
294 48499514696523
295 51634601218988
296 54966845048216
297 58508288438298
298 62271732560335
299 66270693000039
300 70519542309253
301 75033439315511
302 79828515456205
303 84921773216885
304 90331305022358
305 96076176141943
306 102176677276268
307 108654173545546
308 115531413432688
309 122832338890193
310 130582437493342
311 138808531626890
312 147539175089926
313 156804400198071
314 166636185624970
315 177068156036311
316 188136104529626
317 199877667586022
318 212332903335605
319 225543916628090
320 239555524839030
321 254414827485911
322 270171939802731
323 286879534322828
324 304593642729250
325 323373141183316
326 343280657595773
327 364381995134255
328 386747119814929
329 410449556560212
330 435567457817296
331 462182939173580
332 490383272035304
333 520260153708561
334 551910994118253
335 585438162973818
336 620950368965933
337 658561847304605
338 698393882103423
339 740573929893460
340 785237247687614
341 832526004984116
342 882591015974588
343 935590798264694
344 991693466535370
345 1051075736168092
346 1113924933099415
347 1180438007670946
348 1250823655620984
349 1325301295101697
350 1404103367936885
351 1487474279659261
352 1575672824555741
353 1668971169296257
354 1767657395238684
355 1872034474753548
356 1982423007983494
357 2099160195575649
358 2222602703352683
359 2353125730408589
360 2491125991151349
361 2637020821214986
362 2791251369382641
363 2954281750308057
364 3126602362997273
365 3308729212058648
366 3501207340769317
367 3704610258706487
368 3919543593739921
369 4146644640609641
370 4386586136141188
371 4640076077571946
372 4907861602848856
373 5190729009102289
374 5489507863685538
375 5805071247445511
376 6138339977751442
377 6490283257846571
378 6861922992684420
379 7254334769550590
380 7668652412169640
381 8106069324017295
382 8567843146632019
383 9055297686647721
384 9569827651137865
385 10112901076718312
386 10686064316474550
387 11290945018880325
388 11929257204653880
389 12602805058669871
390 13313488074451341
391 14063305570823381
392 14854362108074232
393 15688872789247233
394 16569168766180342
395 17497703647711123
396 18477059066088896
397 19509952093641002
398 20599241120634474
399 21747934360936965
400 22959195830414974
401 24236355322431737
402 25582914467123058
403 27002558073393608
404 28499160564770623
405 30076798788926686
406 31739758598344199
407 33492549587828386
408 35339911802079730
409 37286832282798547
410 39338552272965962
411 41500585704350898
412 43778726637120910
413 46179070229662606
414 48708020416788194
415 51372313242407933
416 54179025218740722
417 57135599180299617
418 60249853047426712
419 63530008852250584
420 66984701931113638
421 70623012982383234
422 74454478244450416
423 78489124788545630
424 82737481379773494
425 87210617774336663
426 91920156330444044
427 96878315171161986
428 102097921223425456
429 107592457486445869
430 113376077201821443
431 119463656144833915
432 125870808044095093
433 132613941738381571
434 139710278695361858
435 147177915345901774
436 155035842397569968
437 163304013427552783
438 172003366196763676
439 181155897347844439
440 190784686772763614
441 200913978785921044
442 211569209273889378
443 222777094638717810
444 234565662038781310
445 246964345942259731
446 260004022774916813
447 273717115560659399
448 288137632743627012
449 303301282441385067
450 319245515915016903
451 336009651294925102
452 353634923334984024
453 372164617190381895
454 391644124309455171
455 412121088104818104
456 433645466647785706
457 456269690112028161
458 480048732314089357
459 505040280673174155
460 531304816578982407
461 558905800048987056
462 587909759867527415
463 618386492882890687
464 650409166461131202
465 684054533358183110
466 719403046647352858
467 756539092813569825
468 795551120444351612
469 836531891560942351
470 879578627252713395
471 924793278449993889
472 972282688925810113
473 1022158888685387137
474 1074539276079257060
475 1129546933994793248
476 1187310835028757298
477 1247966182021710991
478 1311654637068876774
479 1378524690263645996
480 1448731914893354783
481 1522439364774330576
482 1599817860543351055
483 1681046417598185782
484 1766312564750065262
485 1855812807480607420
486 1949752982041910908
487 2048348754760827838
488 2151826017694703018
489 2260421426587648719
490 2374382839993957709
491 2493969901668709554
492 2619454527232913642
493 2751121532184208385
494 2889269173663990649
495 3034209827531678240
496 3186270588003110495
497 3345794000910229007
498 3513138726490487302
499 3688680330700380530
500 3872812020573683800
501 4065945498075240881
502 4268511771904471616
503 4480962082715079620
504 4703768798225728393
505 4937426412624042290
506 5182452536608855491
507 5439388976898950501
508 5708802826565963694
509 5991287635612337167
510 6287464610418231621
511 6597983879499613742
512 6923525816525540665
513 7264802409027713496
514 7622558712190642015
515 7997574334227406439
516 8390665032297345898
517 8802684320443663491
518 9234525225490151439
519 9687122027744982392
520 10161452186594024714
521 10658538231130815653
522 11179449869922346246
523 11725306039852104442
524 12297277222234017888
525 12896587663293486567
526 13524517909401305526
527 14182407220760934911
528 14871656344300876891
529 15593730132065180431
530 16350160579195725752
531 17142549664570932783
532 17972572670785747943
533 18841981274190161572
534 19752607170375915505
535 20706365429389178048
536 21705258460793255844
537 22751379657046751445
538 23846917720131498829
539 24994160627283699396
540 26195500349221010360
541 27453437159636073234
542 28770584787196328326
543 30149675098730325238
544 31593563713731176342
545 33105235104463854559
546 34687808710944683368
547 36344544486741600933
548 38078849566916969264
549 39894284298495843725
550 41794569498507048964
551 43783593023622278749
552 45865417666647972138
553 48044288303790736019
554 50324640494653246092
555 52711108257658478256
556 55208533421667656193
557 57821974098523717385
558 60556714847413713633
559 63418275895394503932
560 66412424195658821292
561 69545183461461020713
562 72822846180148123554
563 76251984547495121008
564 79839463515143161892
565 83592452692525148107
566 87518440528506256413
567 91625247265222890205
568 95921040333697671437
569 100414348469592849720
570 105114078421012786334
571 110029530313982698146
572 115170415798358019056
573 120546874771664731937
574 126169495065266937205
575 132049330665355982638
576 138197923063975698829
577 144627321091849037959
578 151350104091103345732
579 158379403499171150519
580 165728927974502686228
581 173412986906789858330
582 181446517653220524890
583 189845111123656783288
584 198625041323602990899
585 207803293192901176187
586 217397594623090033334
587 227426446770425357136
588 237909158747421056831
589 248865880602521514257
590 260317640930850689484
591 272286382748319598323
592 284795004236305162344
593 297867397788647318284
594 311528494142837840090
595 325804304847416983034
596 340721970086508041225
597 356309804858317795589
598 372597350766772284370
599 389615426261380182454
600 407396182716110784254
601 425973159048569543844
602 445381342470015529102
603 465657227853245897976
604 486838883503240108422
605 508966015714846574444
606 532080039968596139573
607 556224151084850913843
608 581443400326117239780
609 607784771616966304178
610 635297264997746932900
611 664031979464234804004
612 694042203284901290228
613 725383503979717302531
614 758113826103835150286
615 792293588960013693854
616 827985792415092705941
617 865256123042331902353
618 904173068617716307154
619 944808033353043482144
620 987235461828518389900
621 1031532964069066434334
622 1077781449632676016167
623 1126065263403285560869
624 1176472330652853771246
625 1229094304391003077102
626 1284026722348920567383
627 1341369166835854899347
628 1401225434558589194803
629 1463703710080565467866
630 1528916749509603305835
631 1596982068624124764318
632 1668022141618778905131
633 1742164605096741616047
634 1819542473031415333953
635 1900294357997560240221
636 1984564703652606801462
637 2072504024554418573413
638 2164269157653633644717
639 2260023522207810590963
640 2359937391752324067120
641 2464188175830418147936
642 2572960714086309100820
643 2686447581513054410140
644 2804849406538364155468
645 2928375201690723833568
646 3057242707533790965384
647 3191678750902160979195
648 3331919616755938809842
649 3478211436133447347157
650 3630810588270660576071
651 3789984120658246603645
652 3956010183771465064420
653 4129178485922869669272
654 4309790763210618868232
655 4498161271870879308903
656 4694617296382916858907
657 4899499682319221354593
658 5113163385567390194260
659 5335978049040897363636
660 5568328596299322434280
661 5810615855521609548562
662 6063257201205068473165
663 6326687229160166844391
664 6601358450019939110507
665 6887742019458142085806
666 7186328487633297654448
667 7497628588903275321468
668 7822174051811924171685
669 8160518453010678350533
670 8513238092486539438903
671 8880932916935212320651
672 9264227465409997185959
673 9663771867509235454209
674 10080242865211756797730
675 10514344891774940555295
676 10966811175665980749626
677 11438404906715246699943
678 11929920428641637794997
679 12442184499182635281416
680 12976057578424032955868
681 13532435190282029047309
682 14112249314061084265228
683 14716469855448313157309
684 15346106149444573057734
685 16002208549289213599055
686 16685870049774734411742
687 17398228003318670760996
688 18140465872976772047065
689 18913815085833071575821
690 19719556925912215407054
691 20559024535417797524709
692 21433604958796118586639
693 22344741303333091236415
694 23293934946044958666461
695 24282747866303200004601
696 25312805028313033365302
697 26385796898928778201235
698 27503482019762864573740
699 28667689724553601087443
700 29880322915522423171170
701 31143360996067487986098
702 32458862867320028903645
703 33828970092600247472148
704 35255910131683348953398
705 36741999754926893517390
706 38289648533528856469663
707 39901362522953294038450
708 41579748029097345768172
709 43327515581524070993061
710 45147483997360041763821
711 47042584666649359200943
712 49015865936821809608661
713 51070497734576851400524
714 53209776295771342162598
715 55437129149402405618435
716 57756120220084046388904
717 60170455201913498276961
718 62683987062043561426507
719 65300721834771144052334
720 68024824557176422876615
721 70860625515284686300884
722 73812626645579386016398
723 76885508267808276106813
724 80084135987910175602842
725 83413567955154840599587
726 86879062305053080192608
727 90486084980477571452482
728 94240317756585079138870
729 98147666668903313759035
730 102214270664536151151963
731 106446510684010068669774
732 110851018986747887778136
733 115434688935986928886516
734 120204685050737683409103
735 125168453547186375848582
736 130333733172224201399229
737 135708566559398443114442
738 141301311903666497555834
739 147120655193183409956368
740 153175622790099621333468
741 159475594604505684284285
742 166030317649761544111191
743 172849920230607409472889
744 179944926547113146923050
745 187326271973069700920469
746 195005318788968093216255
747 202993872632968054002042
748 211304199447969977923284
749 219949043194408180966759
750 228941644103365585616313
751 238295757745650697779290
752 248025674690622904332039
753 258146241033599711614345
754 268672879565960871739634
755 279621611871438711364310
756 291009081121510710426498
757 302852575857709437188862
758 315170054535762787429448
759 327980171120379242648236
760 341302301509027807190380
761 355156571076052505534977
762 369563883117356056013614
763 384545948489000964496878
764 400125316225602630975189
765 416325405430009399715463
766 433170538227571331555739
767 450685974076218277549196
768 468897945231483835699816
769 487833693656725104530011
770 507521509187913177032082
771 527990769237779221332735
772 549271979861106702268279
773 571396818462150396612917
774 594398177976775123182663
775 618310212805571194603761
776 643168386346449456249235
777 669009520393093851370778
778 695871846266309074589682
779 723795057936498063555166
780 752820367021185734330682
781 782990559906546952057435
782 814350056899661352461153
783 846944973645250113382957
784 880823184739528597046989
785 916034389761599827066640
786 952630181679240942028966
787 990664117834797824721029
788 1030191793499060671795885
789 1071270918177402965050187
790 1113961394690737623474053
791 1158325401196144288885752
792 1204427476202638607167701
793 1252334606725913468900173
794 1302116319678243464728827
795 1353844776608733495211056
796 1407594871935048941095394
797 1463444334755402939521354
798 1521473834425042559134305
799 1581767089957768461743739
800 1644410983488701483020438
801 1709495677822036229001793
802 1777114738356850298502885
803 1847365259380413749843305
804 1920347995076934035830392
805 1996167495204885583283041
806 2074932245855780488585821
807 2156754815201664816089616
808 2241752004714645619328714
809 2330045005722776762814797
810 2421759561853912504646328
811 2517026137186716850470638
812 2615980090740054710688218
813 2718761857064220489713297
814 2825517133651106304558234
815 2936397074874423081746899
816 3051558493260518592214620
817 3171164067746339265007157
818 3295382559821223452269746
819 3424389037142811102304845
820 3558365105626867302911220
821 3697499149539117681417388
822 3841986580689260904440854
823 3992030096190822405777441
824 4147839946001522123173299
825 4309634209630635311137204
826 4477639083350261763204181
827 4652089177224709621603637
828 4833227823413909099266180
829 5021307394990723098668516
830 5216589636862804091593609
831 5419346007950645097182331
832 5629858036355671382823217
833 5848417686587842538241556
834 6075327740726002869074612
835 6310902192496485420650835
836 6555466656299932343035640
837 6809358790072987554098817
838 7072928734180785277441860
839 7346539565135446902148508
840 7630567766497856621331720
841 7925403715665247031544585
842 8231452189082335144290710
843 8549132884469934447938996
844 8878880962799172239307135
845 9221147608505838298832006
846 9576400610857821207770997
847 9945124964870286280808806
848 10327823494887264714298772
849 10725017499107663637377165
850 11137247418390733976020419
851 11565073527513696366942370
852 12009076652426121497810942
853 12469858911569127083061001
854 12948044485036386351933467
855 13444280409522817205091789
856 13959237403081565097043338
857 14493610717527038714009109
858 15048121022739971221780360
859 15623515320606302309529133
860 16220567893105989475801730
861 16840081282159490906694532
862 17482887306020019448399195
863 18149848109712578087936762
864 18841857254569753541604076
865 19559840844262728325667192
866 20304758692666247122580687
867 21077605530835025753948102
868 21879412258731367964125963
869 22711247238881865196535443
870 23574217637891773135759879
871 24469470812901998291617127
872 25398195749235118995152004
873 26361624546204039921135679
874 27361033957660269622463837
875 28397746984170221956237293
876 29473134523712269891662058
877 30588617077707702558607004
878 31745666519625369300803700
879 32945807922879873316489426
880 34190621455623142558482468
881 35481744339087857041244560
882 36820872877424906635878975
883 38209764555645855784256175
884 39650240213988592355067106
885 41144186295252496319666930
886 42693557173810565515008636
887 44300377562818930048807338
888 45966745008699255866446396
889 47694832469407378335386452
890 49486890985968035026635318
891 51345252443766159345339562
892 53272332433492345369883824
893 55270633208256903194667639
894 57342746747162861888487851
895 59491357921901015533677545
896 61719247777089116287613775
897 64029296920953320101369765
898 66424489037519286345970707
899 68907914517002371398681346
900 71482774215980208919742700
901 74152383344160285174103764
902 76920175489783889631999056
903 79789706780591332137374040
904 82764660192861525209771938
905 85848850005630590699098577
906 89046226413040130870917218
907 92360880292139913580470641
908 95797048139578742861671372
909 99359117174721212230737643
910 103051630623121205201304837
911 106879293178183174952419253
912 110846976655399710144316098
913 114959725837340077657640715
914 119222764524285590065327980
915 123641501789027750833077732
916 128221538451246667997300996
917 132968673770422400409898994
918 137888912373173358556177881
919 142988471414473233888258241
920 148273787989171590544011280
921 153751526793771870849981527
922 159428588055438186933431092
923 165312115728799693739190213
924 171409505978019210197354552
925 177728415945385775657751048
926 184276772824453185504371289
927 191062783239685848743802961
928 198094942951205885504316907
929 205382046887437179917738841
930 212933199524755322362104192
931 220757825617865324114401291
932 228865681300598020888942676
933 237266865561792669708078573
934 245971832116557394283113068
935 254991401678676267931126961
936 264336774654992547214663511
937 274019544268748405278854605
938 284051710133324004243608808
939 294445692284597803186397538
940 305214345694006328927742863
941 316370975271948594934723000
942 327929351384180435925871125
943 339903725892398818125139986
944 352308848742314383087656266
945 365159985112009528292413651
946 378472933144560220928766870
947 392264042279527851263962701
948 406550232207905952885724020
949 421349012467093078209721198
950 436678502701182399536378838
951 452557453605161334259913998
952 469005268579051490454318789
953 486042026112849879504204014
954 503688502928964422701799606
955 521966197905456499944959304
956 540897356807561676134336237
957 560504997853327286204660833
958 580812938141659805961469383
959 601845820971431088453732597
960 623629144080679201785583158
961 646189288837579363860547724
962 669553550413099398401097677
963 693750168970135873851618278
964 718808361899981005951684809
965 744758357144365423941206796
966 771631427634783893928652075
967 799459926891050925738556973
968 828277325811811720566151804
969 858118250702774603108684919
970 889018522576483483581295300
971 921015197773593969266699416
972 954146609940489963374647077
973 988452413417696277202201729
974 1023973628075135472833237985
975 1060752685653321102939250165
976 1098833477647845056007250427
977 1138261404801322506915922699
978 1179083428241394866995832630
979 1221348122334367984162132609
980 1265105729294561321106645759
981 1310408215624534956193522561
982 1357309330427874075519128999
983 1405864665675786506859996531
984 1456131718470744044906128772
985 1508169955394908475334589935
986 1562040878988405395188393852
987 1617808096451884919335765597
988 1675537390620432592508861390
989 1735296793310539545045436863
990 1797156661089163582349797964
991 1861189753574319347217778263
992 1927471314318539401301473557
993 1996079154392628386392271503
994 2067093738723579970188258124
995 2140598275312717927788244343
996 2216678807390457429950053742
997 2295424308642917240671574144
998 2376926781569720810877035942
999 2461281359117691287105459325
1000 2548586409653001404693278177