0 1
1 1
2 2
3 3
4 5
5 7
6 9
7 13
8 18
9 24
10 32
11 42
12 55
13 71
14 91
15 116
16 147
17 185
18 231
19 288
20 357
21 440
22 540
23 661
24 807
25 980
26 1186
27 1432
28 1724
29 2069
30 2476
31 2956
32 3521
33 4183
34 4958
35 5865
36 6923
37 8155
38 9587
39 11251
40 13180
41 15411
42 17990
43 20967
44 24399
45 28348
46 32886
47 38098
48 44075
49 50919
50 58748
51 67695
52 77909
53 89553
54 102815
55 117908
56 135065
57 154548
58 176652
59 201710
60 230089
61 262197
62 298496
63 339501
64 385782
65 437972
66 496780
67 562999
68 637503
69 721263
70 815362
71 921003
72 1039519
73 1172381
74 1321228
75 1487876
76 1674329
77 1882805
78 2115758
79 2375908
80 2666250
81 2990087
82 3351077
83 3753253
84 4201058
85 4699383
86 5253624
87 5869731
88 6554239
89 7314337
90 8157939
91 9093749
92 10131323
93 11281151
94 12554762
95 13964813
96 15525178
97 17251070
98 19159176
99 21267787
100 23596928
101 26168520
102 29006575
103 32137370
104 35589637
105 39394787
106 43587168
107 48204325
108 53287250
109 58880704
110 65033564
111 71799175
112 79235724
113 87406654
114 96381159
115 106234659
116 117049312
117 128914610
118 141928015
119 156195641
120 171832948
121 188965547
122 207730090
123 228275169
124 250762298
125 275366994
126 302279972
127 331708399
128 363877204
129 399030564
130 437433510
131 479373618
132 525162819
133 575139376
134 629670065
135 689152458
136 754017358
137 824731492
138 901800411
139 985771581
140 1077237667
141 1176840130
142 1285273144
143 1403287713
144 1531696103
145 1671376653
146 1823278991
147 1988429576
148 2167937595
149 2363001414
150 2574915507
151 2805077844
152 3054997793
153 3326304660
154 3620756932
155 3940252079
156 4286837065
157 4662719709
158 5070280888
159 5512087579
160 5990906770
161 6509720491
162 7071741979
163 7680432878
164 8339521669
165 9053023493
166 9825261449
167 10660889322
168 11564915833
169 12542730769
170 13600132988
171 14743360286
172 15979121341
173 17314629977
174 18757641932
175 20316494046
176 22000146128
177 23818225899
178 25781077063
179 27899810628
180 30186359682
181 32653538099
182 35315103373
183 38185823567
184 41281548850
185 44619288027
186 48217290389
187 52095132986
188 56273813709
189 60775850913
190 65625389795
191 70848315822
192 76472375717
193 82527306711
194 89044974615
195 96059520885
196 103607519459
197 111728144246
198 120463347794
199 129858051679
200 139960349358
201 150821722667
202 162497272711
203 175045965669
204 188530894723
205 203019559336
206 218584162914
207 235301929700
208 253255442143
209 272533000525
210 293229005989
211 315444368137
212 339286938901
213 364871974592
214 392322627901
215 421770471201
216 453356053305
217 487229492184
218 523551105611
219 562492081823
220 604235192675
221 648975552439
222 696921424883
223 748295081049
224 803333711168
225 862290394337
226 925435129427
227 993055930422
228 1065459990234
229 1142974917811
230 1225950052628
231 1314757860838
232 1409795418185
233 1511485985387
234 1620280681501
235 1736660260437
236 1861136997144
237 1994256690603
238 2136600790279
239 2288788653001
240 2451479938093
241 2625377149708
242 2811228334891
243 3009829945808
244 3222029876349
245 3448730683862
246 3690893006810
247 3949539189230
248 4225757124232
249 4520704330401
250 4835612274243
251 5171790952455
252 5530633749513
253 5913622587232
254 6322333383289
255 6758441835622
256 7223729552084
257 7720090546193
258 8249538119692
259 8814212153671
260 9416386831908
261 10058478822383
262 10743055942926
263 11472846337777
264 12250748194932
265 13079840035942
266 13963391610691
267 14904875430646
268 15907978977242
269 16976617625035
270 18114948319613
271 19327384052196
272 20618609176403
273 21993595615763
274 23457620012108
275 25016281866521
276 26675522729295
277 28441646499033
278 30321340892506
279 32321700150003
280 34450249045462
281 36714968275717
282 39124321305352
283 41687282746727
284 44413368361461
285 47312666774429
286 50395872994945
287 53674323843885
288 57160035392446
289 60865742525457
290 64804940745506
291 68991930340034
292 73441863041936
293 78170791321851
294 83195720456271
295 88534663521564
296 94206699474733
297 100232034491056
298 106632066735378
299 113429454752743
300 120648189675468
301 128313671455851
302 136452789342119
303 145094006825454
304 154267451300903
305 164005008698252
306 174340423350423
307 185309403379550
308 196949731898023
309 209301384339169
310 222406652245252
311 236310273856893
312 251059571868539
313 266704598734637
314 283298289929014
315 300896625578632
316 319558800918439
317 339347406038290
318 360328615413890
319 382572387738572
320 406152676601523
321 431147652588495
322 457639937407098
323 485716850667898
324 515470669989241
325 546998905128417
326 580404586875201
327 615796571479494
328 653289861427464
329 693005943424760
330 735073144484311
331 779627007061087
332 826810684227543
333 876775355935445
334 929680667459740
335 985695191172753
336 1044996912859972
337 1107773743851466
338 1174224060302837
339 1244557271025672
340 1318994415341360
341 1397768792508986
342 1481126624351184
343 1569327752780933
344 1662646374023054
345 1761371811415091
346 1865809328762485
347 1976280986319140
348 2093126541572268
349 2216704397122171
350 2347392598055406
351 2485589881327588
352 2631716779801824
353 2786216783721938
354 2949557562533117
355 3122232250102811
356 3304760796552188
357 3497691390068979
358 3701601952232644
359 3917101710555284
360 4144832852128125
361 4385472262458519
362 4639733353776305
363 4908367987294873
364 5192168494139404
365 5491969799886480
366 5808651657895715
367 6143140996863311
368 6496414388298293
369 6869500639904053
370 7263483521130418
371 7679504627463906
372 8118766390349026
373 8582535239970367
374 9072144928469272
375 9589000021530426
376 10134579566665549
377 10710440946926225
378 11318223929190711
379 11959654916607650
380 12636551415246894
381 13350826725495217
382 14104494869232021
383 14899675764344896
384 15738600658708146
385 16623617836329555
386 17557198608970530
387 18541943607175430
388 19580589385318630
389 20676015355979327
390 21831251069671635
391 23049483856716624
392 24334066848848691
393 25688527398986868
394 27116575918466923
395 28622115151936867
396 30209249911085293
397 31882297289375594
398 33645797380994575
399 35504524528314833
400 37463499123322678
401 39527999989667073
402 41703577373225861
403 43996066570389455
404 46411602224644086
405 48956633323472068
406 51637938929075013
407 54462644677986149
408 57438240086286422
409 60572596698858850
410 63873987122892476
411 67351104987715260
412 71013085875003980
413 74869529265470554
414 78930521550252838
415 83206660157465986
416 87709078846722090
417 92449474226874915
418 97440133554786379
419 102693963875576140
420 108224522567616483
421 114046049358458269
422 120173499880906156
423 126622580841637453
424 133409786878102310
425 140552439182923795
426 148068725978636125
427 155977744929386728
428 164299547580207285
429 173055185918611051
430 182266761157583408
431 191957474843548514
432 202151682397632545
433 212874949203484469
434 224154109360054251
435 236017327223099926
436 248494161864835705
437 261615634587011411
438 275414299628827451
439 289924318217486846
440 305181536115887583
441 321223564828952470
442 338089866637365895
443 355821843635090797
444 374462930955009572
445 394058694375338564
446 414656932508114177
447 436307783780084882
448 459063838425806344
449 482980255722607940
450 508114886707367130
451 534528402625763035
452 562284429375913876
453 591449688220015545
454 622094143049795229
455 654291154504329382
456 688117641252104788
457 723654248763096763
458 760985525911104670
459 800200109761697625
460 841390918916921249
461 884655355804393619
462 930095518315571939
463 977818421215881791
464 1027936227768127797
465 1080566492030121736
466 1135832412307794625
467 1193863096266277963
468 1254793838223613005
469 1318766409174866494
470 1385929360118500881
471 1456438339281974812
472 1530456423869794327
473 1608154466984593542
474 1689711460400318819
475 1775314913896317015
476 1865161251892179462
477 1959456228155553587
478 2058415359388835754
479 2162264378535822253
480 2271239708686098915
481 2385588958493210460
482 2505571440062492059
483 2631458710306002198
484 2763535136805374247
485 2902098489268601982
486 3047460557713851857
487 3199947798562485632
488 3359902009874700310
489 3527681037014573937
490 3703659510086888667
491 3888229614546065015
492 4081801896438003176
493 4284806103798623185
494 4497692065798502910
495 4720930611291398639
496 4955014528495764992
497 5200459567612700873
498 5457805488261127217
499 5727617153691661583
500 6010485673824751269
501 6307029599246239826
502 6617896168384763291
503 6943762610190438934
504 7285337504733422883
505 7643362204244140286
506 8018612317224479376
507 8411899258371235047
508 8824071867169820967
509 9256018098137850224
510 9708666785824754768
511 10182989487805487228
512 10680002409043768836
513 11200768411143453374
514 11746399110155560665
515 12318057066763715186
516 12916958072832422287
517 13544373538470976028
518 14201632983941049418
519 14890126640918556425
520 15611308167810522140
521 16366697484025677350
522 17157883728303558131
523 17986528346421479088
524 18854368313822262714
525 19763219498938279429
526 20714980173229523010
527 21711634674205592284
528 22755257227964032171
529 23848015938050819284
530 24992176947733216672
531 26190108783071357066
532 27444286884483251388
533 28757298334818833458
534 30131846792292598727
535 31570757636971999719
536 33076983339880653737
537 34653609064152023891
538 36303858508061087652
539 38031100000169355294
540 39838852857243123155
541 41730794016046599316
542 43710764950571125367
543 45782778886739993177
544 47951028327126134310
545 50219892898737857234
546 52593947537466581301
547 55077971023351118929
548 57676954881396431018
549 60396112663291686136
550 63240889626003734396
551 66216972823878903180
552 69330301631569393340
553 72587078715811404892
554 75993781474821469566
555 79557173964846576037
556 83284319334203817394
557 87182592785977507134
558 91259695091407193795
559 95523666676900240203
560 99982902308539042041
561 104646166398926820986
562 109522608962228605920
563 114621782244317218276
564 119953658056029486134
565 125528645838676972491
566 131357611492139871973
567 137451896997104338651
568 143823340864284297121
569 150484299444800502306
570 157447669137274121182
571 164726909528631697932
572 172336067507115243525
573 180289802387547403735
574 188603412090519432303
575 197292860418851597837
576 206374805476424304729
577 215866629276295966378
578 225786468586913127901
579 236153247067182497712
580 246986708743216381220
581 258307452881685336666
582 270136970316917677919
583 282497681291178194031
584 295412974869941613651
585 308907249996453149181
586 323005958252442448561
587 337735648394532417245
588 353124012738664666706
589 369199935467752616452
590 385993542940775575626
591 403536256084647084554
592 421860844953433014013
593 441001485542863852089
594 460993818951586009907
595 481875012984234116457
596 503683826295185547098
597 526460675175784985968
598 550247703091906181335
599 575088853082956341702
600 601029943137832003718
601 628118744667909747767
602 656405064201907210266
603 685940828432386508673
604 716780172748800636320
605 748979533397310572922
606 782597743413134263494
607 817696132476936346558
608 854338630852737858697
609 892591877571026267964
610 932525333027186670001
611 974211396172064252061
612 1017725526478415728829
613 1063146370874222856301
614 1110555895841334332851
615 1160039524885684197342
616 1211686281593416336724
617 1265588938495636866817
618 1321844171973230530284
619 1380552723442226374541
620 1441819567069594570877
621 1505754084279113092963
622 1572470245317073448365
623 1642086798158113177424
624 1714727465042384167995
625 1790521146946604707009
626 1869602136303315147195
627 1952110338294878697535
628 2038191501061457196374
629 2127997455175363910077
630 2221686362747869311677
631 2319422976548730649314
632 2421378909533451536240
633 2527732915188573591108
634 2638671179121179081025
635 2754387622335263626383
636 2875084216654744056311
637 3000971312770621315412
638 3132267981408245897386
639 3269202368129759109148
640 3412012062306633677051
641 3560944480817838333474
642 3716257267050530705981
643 3878218705802370447064
644 4047108154707570291680
645 4223216492832697171626
646 4406846587113030676948
647 4598313777326015812521
648 4797946380325045972196
649 5006086214284515716112
650 5223089143735828141301
651 5449325646203867403526
652 5685181401284393344547
653 5931057903034923043639
654 6187373096584976036534
655 6454562039906120755709
656 6733077591718115718783
657 7023391126544637194628
658 7325993277970674625367
659 7641394711193707663808
660 7970126926002307491253
661 8312743091358884516015
662 8669818912807991177114
663 9041953533977941880522
664 9429770473491593408899
665 9833918598652001083195
666 10255073137320393808349
667 10693936729457563300525
668 11151240519855409870193
669 11627745293643101371140
670 12124242656212158406180
671 12641556259266856419788
672 13180543074770715084089
673 13742094718626610627385
674 14327138825997284012306
675 14936640480244817659538
676 15571603697542109266468
677 16233072969286578951548
678 16922134864526405090555
679 17639919694692598971554
680 18387603243016306218202
681 19166408561099974198349
682 19977607835203563893262
683 20822524324902931707629
684 21702534376876985075808
685 22619069516683352334863
686 23573618621489234096459
687 24567730176834957795550
688 25603014620622681328792
689 26681146777641831745205
690 27803868388066372339789
691 28972990733487024396909
692 30190397364174291443836
693 31458046931405712106177
694 32777976128833376773128
695 34152302747015564805145
696 35583228845389580588743
697 37073044046121681264336
698 38624128954434596656536
699 40238958710183751367190
700 41920106675630125483807
701 43670248264540955702022
702 45492164917939412777068
703 47388748232021233496172
704 49363004243960283131919
705 51418057881536432177930
706 53557157582738213251812
707 55783680091719755015310
708 58101135437726753671051
709 60513172103850031467323
710 63023582392717848744454
711 65636307996499896654166
712 68355445778867127374443
713 71185253776832613061004
714 74130157430689811812487
715 77194756050566320000046
716 80383829528423779082177
717 83702345304658466484911
718 87155465598792633363594
719 90748554914094271609341
720 94487187826323126610139
721 98377157067173862807102
722 102424481913373793549753
723 106635416892792980340805
724 111016460819339280364291
725 115574366168840581584549
726 120316148808561536424605
727 125249098093463132526550
728 130380787342790985165043
729 135719084711072881093379
730 141272164468118449131591
731 147048518703144502600969
732 153056969468699237449023
733 159306681380627742850756
734 165807174690910877129570
735 172568338850820195428441
736 179600446582464025258741
737 186914168477454733823817
738 194520588142105505889572
739 202431217909267371105291
740 210658015137644630529755
741 219213399120180106479683
742 228110268623881681013371
743 237362020084269332897986
744 246982566478458298714446
745 256986356901760069791542
746 267388396873579727142655
747 278204269399316683065335
748 289450156815937348198974
749 301142863449883720043089
750 313299839117012576446265
751 325939203495327081511002
752 339079771402367438739258
753 352741079010271065285567
754 366943411032696965607978
755 381707828919034954705473
756 397056200092589569813665
757 413011228270742411053889
758 429596484906456814255794
759 446836441791896786280023
760 464756504866389681495082
761 483383049272470878610914
762 502743455705310499695751
763 522866148102438830556537
764 543780632722360447730036
765 565517538662379087694884
766 588108659867748031704652
767 611586998686116318967930
768 635986811023161606032759
769 661343653157288196106953
770 687694430273325980092388
771 715077446777295153960198
772 743532458456505077041708
773 773100726551536066096932
774 803825073809012921196200
775 835749942586521283884438
776 868921455083545359606302
777 903387475774921010858024
778 939197676126004760437743
779 976403601671559955506307
780 1015058741543259456762792
781 1055218600533703062471054
782 1096940773787950896788332
783 1140285024216784747293573
784 1185313362729231507782232
785 1232090131385320269553220
786 1280682089573601136856373
787 1331158503321633583962062
788 1383591237851459321801475
789 1438054853496013538097450
790 1494626705096503499481248
791 1553387045004999494136757
792 1614419129820844739526509
793 1677809330994003129212244
794 1743647249433131659811092
795 1812025834260993352048454
796 1883041505864821922593215
797 1956794283394417018291050
798 2033387916866094323686068
799 2112930024036144326574074
800 2195532232213173204403359
801 2281310325184615610341527
802 2370384395438828740712993
803 2462879001870506829451206
804 2558923333163702241563109
805 2658651377053510959663967
806 2762202095674484054085246
807 2869719607211070531836955
808 2981353374072888865463241
809 3097258397825372866590623
810 3217595421114351026078134
811 3342531136831405919095308
812 3472238404775430988857527
813 3606896476074665497967836
814 3746691225642654508731961
815 3891815392951059590175200
816 4042468831412048051301321
817 4198858766673124711026415
818 4361200064137751738678763
819 4529715506035940512651078
820 4704636078380206706348300
821 4886201268153868267566183
822 5074659371090648365601370
823 5270267810416934920435675
824 5473293466940858613039774
825 5684013020885596360813669
826 5902713305878001647327341
827 6129691675517821822441228
828 6365256382967401030349558
829 6609726974016901775523501
830 6863434694095724822894527
831 7126722909716983219234943
832 7399947544858609345202726
833 7683477532801962262169200
834 7977695283966675002930145
835 8282997170298957289253503
836 8599794026789668494181662
837 8928511670718219205207907
838 9269591439238768866850130
839 9623490745946283772665082
840 9990683657081826941049866
841 10371661488058992688875869
842 10766933421016698324271573
843 11177027144127628425484194
844 11602489513416519583571608
845 12043887237868202027816318
846 12501807588631906863212111
847 12976859133155832272957780
848 13469672495114368445683958
849 13980901141019739599010744
850 14511222194440163700172523
851 15061337278777988769739491
852 15631973389593672484844361
853 16223883797494963743003283
854 16837848982645256599044555
855 17474677601980855401176172
856 18135207490263853075040555
857 18820306696135521608650627
858 19530874554374585421892076
859 20267842795605536325485794
860 21032176694744296400184075
861 21824876259512086961702883
862 22646977460393363867314215
863 23499553503460179306739775
864 24383716147533376974879463
865 25300617067200671793930410
866 26251449263262959420243043
867 27237448522233198610758426
868 28259894926566966844674981
869 29320114417360363893337453
870 30419480411309388652639989
871 31559415473785302761374806
872 32741393049942883555523537
873 33966939255842924005814166
874 35237634731636925805415450
875 36555116558930723237047899
876 37921080244514841602352653
877 39337281772722808881205762
878 40805539728754479321054787
879 42327737495379771708582140
880 43905825525519154542160686
881 45541823693280809194608936
882 47237823726120757111746113
883 48995991720881437593424323
884 50818570746556361065854299
885 52707883536723634232376782
886 54666335274689456384478883
887 56696416474484221911033557
888 58800705960958737339254402
889 60981873952336380081463421
890 63242685248688901897795357
891 65586002529919127926255931
892 68014789766953140645146495
893 70532115749967789752551879
894 73141157737606660004585043
895 75845205231269089904892938
896 78647663878692599278000856
897 81552059511189291944845399
898 84562042319041594115519975
899 87681391169712217439638666
900 90914018073677650307271400
901 94263972802853939192850041
902 97735447666748185785218263
903 101332782451639222701358981
904 105060469528266513385169078
905 108923159133687628443326600
906 112925664833151864902195143
907 117072969168030886235479806
908 121370229496046865050038624
909 125822784030244708729139273
910 130436158083367749191608409
911 135216070524515995881926775
912 140168440455192907575150511
913 145299394112080861944778443
914 150615272004127327684766585
915 156122636291773415312953041
916 161828278416414250272456307
917 167739226988446734124556286
918 173862755942535003161369881
919 180206392969007533724652096
920 186777928230592663601429410
921 193585423374001591679383602
922 200637220846179985375729374
923 207941953525371478476243974
924 215508554677468901967362267
925 223346268248472388295605628
926 231464659504227866706731923
927 239873626028985276070710166
928 248583409094693425077249776
929 257604605413338202430711528
930 266948179285033167942594295
931 276625475154986837564463627
932 286648230592899622216293154
933 297028589708785815354227651
934 307779117019672684427812062
935 318912811782100057185882219
936 330443122805830269735761584
937 342383963764680438343223649
938 354749729020907225115444550
939 367555309980109098271401953
940 380816111994163065861923259
941 394548071830282529073292298
942 408767675724870816002788162
943 423491978041451694778311167
944 438738620552584319742225881
945 454525852366316248192060305
946 470872550518395008940452473
947 487798241252146858398958730
948 505323122008641495861330380
949 523468084150494318804911858
950 542254736443413994431210652
951 561705429320383440526556737
952 581843279954167505000212290
953 602692198164671490555406522
954 624276913188531994457550563
955 646623001339206153803871343
956 669756914586738160259175267
957 693706010087323717530163463
958 718498580693764869800554236
959 744163886478910267944840184
960 770732187305210429521737349
961 798234776474584885069137591
962 826704015493899314567754343
963 856173369992486923282094970
964 886677446829320477316292792
965 918252032428650741527385344
966 950934132384174695952900072
967 984762012373084047371527935
968 1019775240422672432525994930
969 1056014730573549599259715846
970 1093522787984924060753537479
971 1132343155528873595828396687
972 1172521061922026905956608173
973 1214103271444631170912597318
974 1257138135298580647585882568
975 1301675644657632353388203524
976 1347767485464737836588286296
977 1395467095033176678532769981
978 1444829720509989364328150164
979 1495912479262076217478717503
980 1548774421247256991064989346
981 1603476593434574268296407039
982 1660082106340174929455530012
983 1718656202747219528623099492
984 1779266328680451489567264746
985 1841982206708308634173022920
986 1906875911647780819967187986
987 1974021948749611571559430276
988 2043497334443910796696372149
989 2115381679728792302249990066
990 2189757276287276260674157999
991 2266709185420405487947879813
992 2346325329887317919457178554
993 2428696588745898627554067589
994 2513916895290605810151190656
995 2602083338187129172121389826
996 2693296265906698883327689755
997 2787659394566121778572283289
998 2885279919282981704928924953
999 2986268629158906052356568854
1000 3090740026007373750688024617