0 1
1 1
2 2
3 3
4 5
5 7
6 11
7 15
8 22
9 29
10 42
11 55
12 76
13 99
14 133
15 172
16 227
17 290
18 376
19 477
20 612
21 769
22 975
23 1217
24 1528
25 1895
26 2359
27 2907
28 3592
29 4400
30 5403
31 6584
32 8034
33 9742
34 11823
35 14272
36 17234
37 20713
38 24897
39 29803
40 35674
41 42542
42 50719
43 60272
44 71592
45 84794
46 100373
47 118506
48 139827
49 164595
50 193622
51 227275
52 266587
53 312083
54 365072
55 426289
56 497388
57 579378
58 674360
59 783701
60 910069
61 1055284
62 1222726
63 1414832
64 1635859
65 1889035
66 2179730
67 2512182
68 2893162
69 3328200
70 3825830
71 4393215
72 5041088
73 5778715
74 6619558
75 7575552
76 8663559
77 9898866
78 11302596
79 12894252
80 14700248
81 16745367
82 19062582
83 21683326
84 24648678
85 27998366
86 31783501
87 36054144
88 40873811
89 46305391
90 52427722
91 59319579
92 67078642
93 75803408
94 85614702
95 96635375
96 109014669
97 122905428
98 138491780
99 155963474
100 175547339
101 197478413
102 222035732
103 249509931
104 280243733
105 314595821
106 352986572
107 395857793
108 443724465
109 497129778
110 556703765
111 623113092
112 697127472
113 779563832
114 871361283
115 973519239
116 1087181982
117 1213570226
118 1354076561
119 1510189690
120 1683602275
121 1876127084
122 2089818931
123 2326882172
124 2589808127
125 2881273525
126 3204295337
127 3562119391
128 3958394978
129 4397052753
130 4882501740
131 5419495655
132 6013355283
133 6669822612
134 7395311425
135 8196748851
136 9081857615
137 10058984387
138 11137418003
139 12327203639
140 13639501816
141 15086387798
142 16681256732
143 18438608037
144 20374502090
145 22506329775
146 24853327324
147 27436331018
148 30278357898
149 33404345584
150 36841807814
151 40620559649
152 44773457802
153 49336112615
154 54347723558
155 59850780046
156 65892004517
157 72522044348
158 79796537140
159 87775796259
160 96526014840
161 106118948763
162 116633278195
163 128154293321
164 140775433608
165 154597983631
166 169732813705
167 186300094027
168 204431264297
169 224268775751
170 245968321331
171 269698617832
172 295643932136
173 324003919351
174 354996484475
175 388857695802
176 425845027663
177 466237371867
178 510338714297
179 558478270602
180 611014657065
181 668336182567
182 730865582337
183 799060505414
184 873418887619
185 954479681705
186 1042828958117
187 1139100932311
188 1243984895187
189 1358226601318
190 1482636145495
191 1618089787366
192 1765538906728
193 1926012354859
194 2100626637792
195 2290588900922
196 2497208511798
197 2721900801686
198 2966200245450
199 3231765102878
200 3520392421118
201 3834023744092
202 4174762194360
203 4544879448061
204 4946835186928
205 5383285569590
206 5857105387393
207 6371398298773
208 6929522071093
209 7535100886262
210 8192054105508
211 8904611004393
212 9677343558202
213 10515184024015
214 11423462311306
215 12407926894872
216 13474787417197
217 14630739489786
218 15883013266969
219 17239402777330
220 18708321312579
221 20298836031295
222 22020731124681
223 23884548550282
224 25901660066746
225 28084315087481
226 30445722832238
227 33000108436958
228 35762806647107
229 38750327487929
230 41980463123732
231 45472364589137
232 49246663663046
233 53325562387530
234 57732972057897
235 62494617511087
236 67638195627649
237 73193496660370
238 79192584978791
239 85669940035757
240 92662662463160
241 100210637654017
242 108356770745224
243 117147176226685
244 126631445826561
245 136862868051455
246 147898733545807
247 159800589021164
248 172634585290602
249 186471770676900
250 201388487634309
251 217466711448843
252 234794502164011
253 253466395212215
254 273583916266884
255 295256031378836
256 318599733415663
257 343740560332692
258 370813263038425
259 399962401625485
260 431343105829280
261 465121760413030
262 501476870888349
263 540599850799979
264 582696007070018
265 627985443685620
266 676704182958987
267 729105202104468
268 785459708888964
269 846058329830577
270 911212561179387
271 981256130021891
272 1056546644312792
273 1137467151063863
274 1224428012282528
275 1317868687691178
276 1418259866988784
277 1526105508234771
278 1641945260870493
279 1766356795068439
280 1899958554482924
281 2043412416588996
282 2197426819245019
283 2362759797382515
284 2540222533220229
285 2730682820692254
286 2935069095670430
287 3154374386305068
288 3389660886961942
289 3642064460309178
290 3912799826952621
291 4203165693758741
292 4514550640492982
293 4848438958634953
294 5206417326816895
295 5590181455388091
296 6001543654291930
297 6442440391024728
298 6914940867923805
299 7421255615113582
300 7963746209178307
301 8544935038419796
302 9167516311760968
303 9834367151353385
304 10548560059522979
305 11313375513695509
306 12132316080561194
307 13009120710689109
308 13947780713104522
309 14952555972162242
310 16027993022717482
311 17178943440180377
312 18410584286776468
313 19728438957582578
314 21138400302410660
315 22646754246435269
316 24260205930496885
317 25985906465140473
318 27831482475096927
319 29805066390697357
320 31915329830496242
321 34171517884747579
322 36583486824214147
323 39161742887316677
324 41917484863822164
325 44862647961141780
326 48009951879653527
327 51372950405235067
328 54966085669283723
329 58804744194867443
330 62905318120028029
331 67285268514981836
332 71963194443107313
333 76958904467562726
334 82293494531677763
335 87989428686423986
336 94070626892182080
337 100562556125126803
338 107492329336985789
339 114888808240185974
340 122782714812919920
341 131206747221676494
342 140195705427569639
343 149786621882577864
344 160018902981732595
345 170934476368216169
346 182577950187077963
347 194996779056701651
348 208241443315749158
349 222365635967171108
350 237426464373932600
351 253484660759800927
352 270604809104287661
353 288855582095254422
354 308309996302982594
355 329045678826917697
356 351145154196917439
357 374696144344392299
358 399791891089944370
359 426531493502411287
360 455020270291180875
361 485370139100480150
362 517700023637091407
363 552136279987346289
364 588813153882830156
365 627873259730314193
366 669468094056206070
367 713758573612147826
368 760915611750846502
369 811120722720227740
370 864566668517169157
371 921458137319760269
372 982012469250603056
373 1046460417829590746
374 1115046964065078989
375 1188032170849418051
376 1265692095895974472
377 1348319750158407379
378 1436226121356797601
379 1529741248792675016
380 1629215370572363144
381 1735020128627949372
382 1847549854265947370
383 1967222918806035529
384 2094483173775515849
385 2229801464360876011
386 2373677242452595634
387 2526640262089506342
388 2689252385655357840
389 2862109482704930533
390 3045843451946919347
391 3241124347298652591
392 3448662640885304888
393 3669211602904265762
394 3903569833757318895
395 4152583927346465840
396 4417151303665695569
397 4698223188531035019
398 4996807781527156681
399 5313973588932878092
400 5650852965884272949
401 6008645843434194927
402 6388623688201195547
403 6792133669143439551
404 7220603082859583359
405 7675544010814192207
406 8158558263896233274
407 8671342586560612898
408 9215694180290752966
409 9793516517481079871
410 10406825510157289795
411 11057756003486126695
412 11748568663552346225
413 12481657228220474106
414 13259556196030726447
415 14084948920836194709
416 14960676193049302603
417 15889745274129484259
418 16875339471584227123
419 17920828220088998404
420 19029777762929929979
421 20205962398412711735
422 21453376392946233371
423 22776246524565015906
424 24179045366725762152
425 25666505275366401117
426 27243633197865766692
427 28915726266243603967
428 30688388302777215230
429 32567547199879028973
430 34559473312749608951
431 36670798826338381370
432 38908538246334869537
433 41280109975628627645
434 43793359138115115072
435 46456581611448722056
436 49278549443804215054
437 52268537616711331511
438 55436352343329015884
439 58792360865036616293
440 62347522951235090390
441 66113424066452265562
442 70102310426501623871
443 74327125909471851406
444 78801551061601213737
445 83540044166033753064
446 88557884634393694948
447 93871218692008937305
448 99497107638322318922
449 105453578656856104038
450 111759678479746132981
451 118435529885543458728
452 125502391360822222381
453 132982719909530942779
454 140900237368377145587
455 149280000218450849696
456 158148473281558899417
457 167533607298907843823
458 177464920813441905065
459 187973586362219681982
460 199092521435865496271
461 210856484221706173487
462 223302174626517265110
463 236468340607384689277
464 250395890348940852153
465 265128010329252485714
466 280710289858716830505
467 297190852150120454934
468 314620492554423580558
469 333052824038661650829
470 352544430595220522148
471 373155028679757920616
472 394947637426621216947
473 417988757762873261321
474 442348561234721242474
475 468101088694606577714
476 495324459733541047561
477 524101093037785669563
478 554517938631634529065
479 586666722220356561158
480 620644202679213744900
481 656552442942155000387
482 694499095427886401967
483 734597702301575850247
484 776968011810007699221
485 821736311038795206378
486 869035776438687835348
487 919006842526258959079
488 971797590225187225584
489 1027564155317126029975
490 1086471158598432937385
491 1148692158283270858138
492 1214410126391307127395
493 1283817949740706992249
494 1357118957439605509211
495 1434527475586554401539
496 1516269411242302021437
497 1602582866483861806057
498 1693718784787945957249
499 1789941630666986940989
500 1891530105006539722329
501 1998777897152630902498
502 2111994476418148953663
503 2231505924196659900039
504 2357655809593364922571
505 2490806109917417430357
506 2631338179208159053956
507 2779653766313033884833
508 2936176085976883751984
509 3101350944653497671988
510 3275647924812836743929
511 3459561629669544840308
512 3653612992448945928916
513 3858350652354757280501
514 4074352401729277670696
515 4302226706835264463247
516 4542614307159569130294
517 4796189895961823581764
518 5063663887415563120765
519 5345784273391248528893
520 5643338575717453305366
521 5957155897331235871521
522 6288109078688294988955
523 6637116963244494680210
524 7005146778963391475876
525 7393216640104904826908
526 7802398176888148531240
527 8233819297774472309174
528 8688667092661551131560
529 9168190882277625003413
530 9673705422829539548117
531 10206594271794149324382
532 10768313324740612875409
533 11360394529736780691813
534 11984449790138786430095
535 12642175063050197061536
536 13335354665246371978998
537 14065865794660001375997
538 14835683280312904101310
539 15646884569683744480339
540 16501654967587738032055
541 17402293136544118924680
542 18351216874009457791774
543 19350969177540294966716
544 20404224614686570870978
545 21513796009878623294286
546 22682641466665305779440
547 23913871738887902957148
548 25210757970848502835458
549 26576739821514046428610
550 28015433994674349243464
551 29530643191699683596890
552 31126365510849117020802
553 32806804311541830111677
554 34576378569764870805626
555 36439733744974281272107
556 38401753187092256782145
557 40467570106097368510611
558 42642580135465853846065
559 44932454514315422089233
560 47343153922412032390708
561 49880942995480552887252
562 52552405558152207982696
563 55364460604836906969770
564 58324379069320793994274
565 61439801416506828265212
566 64718756100888428822889
567 68169678928613367156316
568 71801433371869677430208
569 75623331876229463378727
570 79645158214208651833286
571 83877190929829023011077
572 88330227932386860167440
573 93015612288772215039393
574 97945259277948138016546
575 103131684761937509748628
576 108588034942832775164744
577 114328117565668180423142
578 120366434643122793059680
579 126718216767920464556316
580 133399459095945294896970
581 140426959072550465967512
582 147818355992781415540615
583 155592172475243300397178
584 163767857948748071067424
585 172365834239423878729093
586 181407543366613654286862
587 190915497643964899384962
588 200913332204077352558837
589 211425860052668338916577
590 222479129781588166486046
591 234100486057120093008214
592 246318633024873372079517
593 259163700759181250994653
594 272667314911391214992588
595 286862669697532848039278
596 301784604394032535100331
597 317469683495732059820197
598 333956280720474951397009
599 351284667029598829221842
600 369497102865624328542777
601 388637934792991009960241
602 408753696761719778119776
603 429893216197927803016651
604 452107725161368398802882
605 475450976793705362803674
606 499979367319845621947252
607 525752063847688658707433
608 552831138252794719187404
609 581281707417016472128051
610 611172080133984375747300
611 642573910976401105507489
612 675562361466833338201220
613 710216268875295543324637
614 746618323016739376598128
615 784855251402733714753783
616 825018013154738326262456
617 867202002067140127536665
618 911507259264866422337609
619 958038695880785658441781
620 1006906326238524309719464
621 1058225512006397468148225
622 1112117217852604466159542
623 1168708279111633139586099
624 1228131682040588033009336
625 1290526857223732635227012
626 1356039986756928407862404
627 1424824325823079500388008
628 1497040539348031079502084
629 1572857054405726243692426
630 1652450429125061333350478
631 1736005738830258864737488
632 1823716980235883311972127
633 1915787494497131414341593
634 2012430410011409079158712
635 2113869105846959710913581
636 2220337696776196878381418
637 2332081540871528699227784
638 2449357770730322785873306
639 2572435849376329965568654
640 2701598152001220455948398
641 2837140574691263279236238
642 2979373171408527409731468
643 3128620820478262486257851
644 3285223921967055647864076
645 3449539127319761002909102
646 3621940102765350452046099
647 3802818327986599785025998
648 3992583931700559276124548
649 4191666565783161934492500
650 4400516319733961413103105
651 4619604677265339442901521
652 4849425516974540291927635
653 5090496159047521603049493
654 5343358460129841701237929
655 5608579958493097636403526
656 5886755071824770109873726
657 6178506349965708209510146
658 6484485785132906713137621
659 6805376182165154349023865
660 7141892591557670189802938
661 7494783808055836462623065
662 7864833937822914811841635
663 8252864037205261460668557
664 8659733826380782756459592
665 9086343481190270559042389
666 9533635506732230702315838
667 10002596696321683644977431
668 10494260179714538912694113
669 11009707564525749322167511
670 11550071175092231662167110
671 12116536393065732969957524
672 12710344104366886970008519
673 13332793257174421687728753
674 13985243535994582287517180
675 14669118156908103829415086
676 15385906789490098494022583
677 16137168610961179813600996
678 16924535498555139548074851
679 17749715366163383624714538
680 18614495651774485257170968
681 19520746962315404912415769
682 20470426882992603953838861
683 21465583958334272775796481
684 22508361852662648864989750
685 23601003697844844064464462
686 24745856636737184262351844
687 25945376570875764659101150
688 27202133121574304736459182
689 28518814813748322323200457
690 29898234492438024873170511
691 31343334982182654391026886
692 32857195000100851195659442
693 34443035333736716052710000
694 36104225295485252845933624
695 37844289465643360766182734
696 39666914736942738593399930
697 41575957673683762524852341
698 43575452199460117295387396
699 45669617627759975406763461
700 47862867050665437940156144
701 50159816101204673561269621
702 52565292105917356170650407
703 55084343644567137692884406
704 57722250535016744916271665
705 60484534261698883366860910
706 63376968867279545951359119
707 66405592327576791148902048
708 69576718431049371148141015
709 72896949184689747122936382
710 76373187769502085726985282
711 80012652069324930807838291
712 83822888798206424758349970
713 87811788252183724641925453
714 91987599712876529475927475
715 96358947531019319359090286
716 100934847919733868230134393
717 105724726488135991939430525
718 110738436547675425476423553
719 115986278224485247714469492
720 121479018412960193070721333
721 127227911606753906487265920
722 133244721645476921145480027
723 139541744416449830683373894
724 146131831553118324388081648
725 153028415172920980141784998
726 160245533699825979103982898
727 167797858818059066355090264
728 175700723606157023281599498
729 183970151901920324106227779
730 192622888951651943524300536
731 201676433398654237291306550
732 211149070668986312624719445
733 221059907814228183086402820
734 231428909874262805189505886
735 242276937825004432248564282
736 253625788179519298130198291
737 265498234313091240112481674
738 277918069586575156948731203
739 290910152344694216432470313
740 304500452870021243554369604
741 318716102375922803110877366
742 333585444126146468351976035
743 349138086771515160366598916
744 365404959998936959343546511
745 382418372590989474178786054
746 400212072999451983262892503
747 418821312539500398744096922
748 438282911316793065851788198
749 458635327003334299975445111
750 479918726583945901960154605
751 502175061199180936211180314
752 525448144216921824636120937
753 549783732669284493724815916
754 575229612198359268613450790
755 601835685659107601724882356
756 629654065535183545250841788
757 658739170328681843619565293
758 689147825092848036770940093
759 720939366282502392226818804
760 754175751105592919723503874
761 788921671565534767922231480
762 825244673393336556697224864
763 863215280075327559828153613
764 902907122192376581131127006
765 944397072293927568525178230
766 987765385541045740613617584
767 1033095846360776705832411865
768 1080475921365844322801442707
769 1129996918802554399814528073
770 1181754154802416847711177669
771 1235847126722635872801996942
772 1292379693874258634261851312
773 1351460265947273597291946202
774 1413201999456664833267364496
775 1477723002544867026389193572
776 1545146548491940251853940658
777 1615601298297239779847434388
778 1689221532713481588115885660
779 1766147394127664721551883739
780 1846525138701787289447957183
781 1930507399201051336680468354
782 2018253458957184635842299949
783 2109929537430565319018410686
784 2205709087856340620849956546
785 2305773107477198070670947279
786 2410310460888649862038644000
787 2519518217041686157458991406
788 2633602000472686835851259687
789 2752776357351132673293781442
790 2877265136962666974168602114
791 3007301889267505595388431777
792 3143130279203335952696358372
793 3285004518426238292785664022
794 3433189815214606442720592335
795 3587962843287546280568942536
796 3749612230323157323634194962
797 3918439066990887985909601994
798 4094757437348761695980644251
799 4278894971487530397427002342
800 4471193421343309779398651246
801 4672009260634189545094092570
802 4881714309918929376350764518
803 5100696387812691918027770322
804 5329359989440747256291618049
805 5568126993251065751195561123
806 5817437397356330641997779506
807 6077750086619285324127051578
808 6349543631748862606670039801
809 6633317121721608094268156572
810 6929591030900668999597358172
811 7238908122275668677335750030
812 7561834388309106185361184542
813 7898960030930280419001243876
814 8250900482284976409195679169
815 8618297467909176199878553258
816 9001820114067601072001642657
817 9402166101062962903305731822
818 9820062864400070665200493046
819 10256268845759467393376972251
820 10711574795819715213847485761
821 11186805131043878665756866527
822 11682819346636858154859365997
823 12200513487963041836237800032
824 12740821682812028336726484835
825 13304717736989891721042811733
826 13893216795819490688602014306
827 14507377074230505463536374301
828 15148301658234270772068755247
829 15817140380683721656808064354
830 16515091774342163346659350613
831 17243405105398543941138105798
832 18003382490700018817476061756
833 18796381102095986333048466907
834 19623815461431361242889955479
835 20487159829860425626767934499
836 21387950695307480774752390970
837 22327789362045099117981585235
838 23308344646527839493840243552
839 24331355683775751102670978987
840 25398634848782188518615486436
841 26512070797589762400214248127
842 27673631632872606376393007486
843 28885368199046311869190431418
844 30149417512136502707687603986
845 31468006329835171260297886753
846 32843454867399973102473663364
847 34278180665266002311587308110
848 35774702614483382934038754452
849 37335645146325802799538352083
850 38963742592678049504904817706
851 40661843724061255882556670556
852 42432916472438104766366081466
853 44280052846211247248978028505
854 46206474045133943384773673707
855 48215535783144912656837676101
856 50310733827469075461702190949
857 52495709762642562356557940871
858 54774256988475860739346266236
859 57150326961311260103269410461
860 59628035688314051748807881543
861 62211670484906851239266524467
862 64905697005869665146176040388
863 67714766561028039187192058765
864 70643723726897158900786319368
865 73697614266081644215745061147
866 76881693366711094476971839354
867 80201434214657999061929670505
868 83662536911802417084799786321
869 87270937754111806402307124202
870 91032818883862541780161348235
871 94954618330873997735978810220
872 99043040458227722342922892071
873 103305066828532090729677337241
874 107747967507441327220384057037
875 112379312821772586465558068514
876 117206985590263748361751545548
877 122239193845699996928228508704
878 127484484067890572626733885295
879 132951754947717074720719898454
880 138650271703286551715841531094
881 144589680970021438731786163460
882 150780026287393310446664006948
883 157231764205869661910388421736
884 163955781038585736837788234326
885 170963410283184030557362676980
886 178266450740280017546266042715
887 185877185356016944497040663096
888 193808400817267182407442119581
889 202073407929121332203934596977
890 210686062805485701276964099994
891 219660788904778043557287243563
892 229012599943982147610702724609
893 238757123725583341546300427878
894 248910626913275935461634003780
895 259490040793694456349319027049
896 270512988062895262788218292968
897 281997810677782995619762645355
898 293963598814264922931331992576
899 306430220975499410796933248016
900 319418355295315923675252188976
901 332949522083591333922812857197
902 347046117662210420240309071722
903 361731449542079586698007803134
904 377029772993647925798589226603
905 392966329065374977166725885490
906 409567384106722438808951122830
907 426860270854387472799149414215
908 444873431142797603234029012193
909 463636460302194665165487079560
910 483180153310114582538398438104
911 503536552764557110370194668994
912 524738998749809412413333339297
913 546822180668568387842144275732
914 569822191116881277013861112149
915 593776581881313632902348871474
916 618724422140848791037520624190
917 644706358959136988484229032963
918 671764680156044473396541634917
919 699943379650808573194539898795
920 729288225372691992337122632973
921 759846829838645283482455554545
922 791668723501348162549259738993
923 824805430974895880251070760595
924 859310550249553769135873076903
925 895239835011199807417788378248
926 932651280185549433706577515710
927 971605210831777658235817844109
928 1012164374514969367036721094018
929 1054394037291698241474216663092
930 1098362083448217783847225854513
931 1144139119135992648323439598421
932 1191798580054876440977229057741
933 1241416843339890490806395039422
934 1293073343813560693631247994346
935 1346850694771852069990124951505
936 1402834813478199864992443937054
937 1461115051546685610995292375011
938 1521784330402356673313333047972
939 1584939282013739747141057178904
940 1650680395100076659955267619999
941 1719112167023403066767777576610
942 1790343261583635908043352006222
943 1864486672943008770054694354770
944 1941659895914849511525354478456
945 2021985102860492607518484505184
946 2105589327447429522967581412874
947 2192604655531270363254525151750
948 2283168423434105624499865523725
949 2377423423902049168262926161571
950 2475518120035516538532124323706
951 2577606867496761670520005995272
952 2683850145310782048321553791266
953 2794414795587506209248579109401
954 2909474272505639287091321005830
955 3029208900911243626079445317592
956 3153806144897533331451189121953
957 3283460886746027674892406813437
958 3418375716623620206059972700667
959 3558761233444823361966472189858
960 3704836357323945612662897674859
961 3856828654057775508219679314550
962 4014974672096010297571504865638
963 4179520292473681709587460786505
964 4350721092197747528091193526864
965 4528842721598319437038322644547
966 4714161296174259427947392345156
967 4906963803482561731029980061825
968 5107548525641644683370712165046
969 5316225478039847386958341026382
970 5533316864862686275428319089701
971 5759157552075193418617120435490
972 5994095558519586498197286095437
973 6238492565813001971710862796376
974 6492724447755742321312517108683
975 6757181819986812032665419557711
976 7032270610651160060105653249476
977 7318412652871349055654737970157
978 7616046299846080609464978575265
979 7925627063428433638762066361542
980 8247628277068600387123269181750
981 8582541784038615057891952640947
982 8930878651890879394852026959657
983 9293169914137451542581098337334
984 9669967340173931296518213291526
985 10061844234509569421091324208944
986 10469396266404841274276011733393
987 10893242331058346377934305851276
988 11334025443527455897370742376826
989 11792413666610786650765857863341
990 12269101073966305008670538783360
991 12764808749785779535874137525394
992 13280285826395422755757030372777
993 13816310561202976565087286615715
994 14373691454464263363774484488932
995 14953268409396394994630650844205
996 15555913936221512407423231886081
997 16182534401783130754161911678910
998 16834071326438045342837796410165
999 17511502729989283297865561125551
1000 18215844528490973741703797362218