0 1
1 1
2 1
3 2
4 3
5 4
6 6
7 9
8 13
9 17
10 25
11 33
12 45
13 61
14 82
15 106
16 142
17 183
18 238
19 306
20 395
21 499
22 638
23 804
24 1014
25 1268
26 1586
27 1967
28 2447
29 3018
30 3721
31 4566
32 5598
33 6827
34 8328
35 10108
36 12257
37 14812
38 17884
39 21508
40 25856
41 30980
42 37076
43 44261
44 52776
45 62768
46 74578
47 88407
48 104681
49 123703
50 146018
51 172019
52 202445
53 237830
54 279087
55 326991
56 382706
57 447221
58 522095
59 608631
60 708789
61 824347
62 957805
63 1111462
64 1288570
65 1492120
66 1726211
67 1994819
68 2303155
69 2656299
70 3060965
71 3523696
72 4052945
73 4657231
74 5347216
75 6133759
76 7030459
77 8051143
78 9212894
79 10533435
80 12034258
81 13737766
82 15671111
83 17862644
84 20346295
85 23158013
86 26340290
87 29938245
88 34005195
89 38597766
90 43782368
91 49630134
92 56223787
93 63652121
94 72018195
95 81432751
96 92023590
97 103928803
98 117306773
99 132328848
100 149191314
101 168106579
102 189316923
103 213085541
104 239711249
105 269518923
106 302876913
107 340185802
108 381898336
109 428507945
110 480570525
111 538692228
112 603554977
113 675902494
114 756569333
115 846467039
116 946615862
117 1058130424
118 1182256834
119 1320356346
120 1473947883
121 1644692102
122 1834438350
123 2045208679
124 2279252416
125 2539028616
126 2827268473
127 3146959184
128 3501413339
129 3894253583
130 4329493449
131 4811521166
132 5345192207
133 5935816296
134 6589260958
135 7311941556
136 8110941286
137 8994002505
138 9969664509
139 11047261178
140 12237076214
141 13550347341
142 14999446326
143 16597888551
144 18360539625
145 20303637293
146 22445025368
147 24804188921
148 27402525467
149 30263392623
150 33412420382
151 36877580814
152 40689543194
153 44881768667
154 49490921428
155 54556989413
156 60123757790
157 66238968620
158 72954861663
159 80328378154
160 88421787554
161 97302939085
162 107045984666
163 117731697263
164 129448298719
165 142291854840
166 156367234302
167 171788588772
168 188680459963
169 207178371421
170 227430100186
171 249596397563
172 273852461976
173 300388805426
174 329412954703
175 361150502998
176 395847066956
177 433769552080
178 475208419327
179 520479193538
180 569925083218
181 623918789766
182 682865525504
183 747205171904
184 817415773122
185 894016093530
186 977569655331
187 1068687781221
188 1168034249554
189 1276328898366
190 1394353012759
191 1522953573447
192 1663049482452
193 1815636585272
194 1981794850857
195 2162694289711
196 2359603256937
197 2573895399848
198 2807059250035
199 3060706393077
200 3336582532001
201 3636577070929
202 3962735900336
203 4317272607832
204 4702583239081
205 5121259426096
206 5576105407131
207 6070153370226
208 6606683105374
209 7189239896243
210 7821657194621
211 8508077496396
212 9252978473504
213 10061197294220
214 10937960768376
215 11888913629516
216 12920153285753
217 14038262717689
218 15250350502565
219 16564089031197
220 17987760633912
221 19530301911076
222 21201356857985
223 23011328291567
224 24971438985450
225 27093791263684
226 29391437381216
227 31878448494693
228 34569995641336
229 37482429555470
230 40633373775912
231 44041816926738
232 47728219788701
233 51714621878658
234 56024764514399
235 60684213886494
236 65720502414297
237 71163270743487
238 77044430121387
239 83398326079968
240 90261924863448
241 97675002060883
242 105680356523483
243 114324027590642
244 123655540534399
245 133728156512564
246 144599154055843
247 156330116590887
248 168987255088450
249 182641738582330
250 197370063948443
251 213254435577741
252 230383188978037
253 248851226766810
254 268760503684613
255 290220526958335
256 313348911521550
257 338271953879638
258 365125267426144
259 394054440373553
260 425215762373995
261 458776978408260
262 494918119635744
263 533832366729171
264 575726999504813
265 620824385231474
266 669363063532906
267 721598877170847
268 777806211159335
269 838279285855212
270 903333571631291
271 973307267025001
272 1048562913144121
273 1129489082532461
274 1216502220977342
275 1310048576155904
276 1410606298045496
277 1518687640574328
278 1634841355955801
279 1759655206826169
280 1893758694807874
281 2037825925561797
282 2192578717040415
283 2358789865828075
284 2537286686504894
285 2728954733848446
286 2934741831849764
287 3155662313498824
288 3392801605478261
289 3647321055736361
290 3920463148489455
291 4213556998774736
292 4528024282534851
293 4865385487647572
294 5227266654684555
295 5615406486006284
296 6031664005161262
297 6478026638592842
298 6956618916098347
299 7469711654494133
300 8019731837118258
301 8609273046011660
302 9241106676184236
303 9918193781496291
304 10643697799951961
305 11420997999646911
306 12253703913676218
307 13145670596970521
308 14101014994748394
309 15124133247719672
310 16219719247182810
311 17392784256306595
312 18648677936850560
313 19993110588934433
314 21432176970467233
315 22972381495838927
316 24620665210476635
317 26384434331898577
318 28271590787218469
319 30290564529129110
320 32450348095460734
321 34760533186729587
322 37231349765309553
323 39873707442205450
324 42699239697835048
325 45720350695098705
326 48950265276431814
327 52403081896881293
328 56093829134586851
329 60038525523909235
330 64254243407705489
331 68759176548437450
332 73572712253247405
333 78715507749304577
334 84209571628887618
335 90078350097056420
336 96346818912666554
337 103041580754170912
338 110190968977148966
339 117825157496736464
340 125976277845553948
341 134678543142741351
342 143968380117350170
343 153884568927333030
344 164468392016784259
345 175763791762893407
346 187817538264457280
347 200679407035554060
348 214402368077112581
349 229042786106979715
350 244660633551440090
351 261319716102365163
352 279087912586081187
353 298037428975487199
354 318245068449898770
355 339792517368774832
356 362766649234984363
357 387259846557832131
358 413370342879799164
359 441202584927725252
360 470867617360735719
361 502483490136825340
362 536175691196292065
363 572077604558553191
364 610330996779130905
365 651086531948381948
366 694504318453754144
367 740754487787672386
368 790017808921843977
369 842486338649617793
370 898364111746485489
371 957867871485906963
372 1021227844724784191
373 1088688562253598289
374 1160509729022521067
375 1236967145123140812
376 1318353682574528315
377 1404980319001941798
378 1497177233740710138
379 1595294967693928358
380 1699705653005011065
381 1810804314151631542
382 1929010247104719247
383 2054768478472220788
384 2188551311915645259
385 2330859964117130290
386 2482226298290213234
387 2643214657922504733
388 2814423809521184936
389 2996488997510968872
390 3190084120915599665
391 3395924035496913176
392 3614766991925367754
393 3847417214253455253
394 4094727630306086357
395 4357602758929589445
396 4637001766863721895
397 4933941700936539686
398 5249500909609165654
399 5584822660429555375
400 5941118968815794084
401 6319674645690314211
402 6721851580926461232
403 7149093271213413055
404 7602929610994090665
405 8084981956306319724
406 8596968482050941534
407 9140709843885964591
408 9718135167337053095
409 10331288376861585777
410 10982334889729612916
411 11673568689189234140
412 12407419804289210314
413 13186462212758231300
414 14013422197087971805
415 14891187172384746056
416 15822815019190512360
417 16811543942267206918
418 17860802891916763123
419 18974222571539329997
420 20155647071728977862
421 21409146157638743348
422 22739028254018776135
423 24149854158049796926
424 25646451528907550691
425 27233930187956293656
426 28917698283515603418
427 30703479358313708532
428 32597330379089969488
429 34605660771167649059
430 36735252523552520927
431 38993281412615741376
432 41387339416648953307
433 43925458375187305241
434 46616134972808065533
435 49468357107808811340
436 52491631733664354106
437 55696014240899044617
438 59092139476322847001
439 62691254475317331405
440 66505253014094938999
441 70546712066578712592
442 74828930283836929082
443 79365968590668658272
444 84172693029435557189
445 89264819956794307556
446 94658963736831105697
447 100372687048546426168
448 106424553965987541205
449 112834185942613670306
450 119622320874527917156
451 126810875389300709527
452 134423010553028569812
453 142483201159163730688
454 151017308811631091615
455 160052658984399312845
456 169618122291957768953
457 179744200173529531645
458 190463115249652292348
459 201808906576875858754
460 213817530085883230231
461 226526964454163917103
462 239977322727980891751
463 254210969972880923506
464 269272647299932565297
465 285209602578100439524
466 302071728215720655422
467 319911706355965323305
468 338785161908729646170
469 358750823801998636789
470 379870694918622527276
471 402210231143811055692
472 425838530037231896924
473 450828529601745675612
474 477257217715543685526
475 505205852751400255637
476 534760196008069760804
477 566010756534700646329
478 599053049037515331847
479 633987865512790978849
480 670921561366178277993
481 709966356732203446057
482 751240653831965708568
483 794869371160028131880
484 840984295424430117630
485 889724452116017723500
486 941236495725690179494
487 995675120579855366490
488 1053203493416945568774
489 1113993708779202357638
490 1178227268457412255183
491 1246095586177482068085
492 1317800518893018330227
493 1393554925999370480272
494 1473583257972546408346
495 1558122175888141319433
496 1647421203477005234381
497 1741743413326846561891
498 1841366149055307010052
499 1946581785233624242432
500 2057698527072200457306
501 2175041251834588842580
502 2298952394195699687601
503 2429792877717298337848
504 2567943094881656584463
505 2713803938084117332672
506 2867797884273039614137
507 3030370135888831603733
508 3201989821062965686603
509 3383151256005138747378
510 3574375272839194265682
511 3776210616120520150040
512 3989235411625171980543
513 4214058710978897443546
514 4451322116078850837644
515 4701701487245531370875
516 4965908739456439760045
517 5244693731005649605925
518 5538846249379125487297
519 5849198099137664346731
520 6176625297079201649281
521 6522050379965012487922
522 6886444830611322897916
523 7270831628172975002617
524 7676287929002881987702
525 8103947884510380002990
526 8555005603042059548298
527 9030718262864228801481
528 9532409383973708969247
529 10061472266537640446150
530 10619373604461438242294
531 11207657282679016020780
532 11827948367512977020214
533 12481957299571153035090
534 13171484299459287517916
535 13898423996735075839497
536 14664770293406967518858
537 15472621473456799382631
538 16324185570813706843207
539 17221786008416363480918
540 18167867522025205997607
541 19165002382693969917366
542 20215896932917060899923
543 21323398451759752773082
544 22490502365474958030663
545 23720359820448592032169
546 25016285636609612329404
547 26381766659832478279065
548 27820470533259344979180
549 29336254907920702977241
550 30933177114547222260064
551 32615504318983448092226
552 34387724185252476657473
553 36254556070912619650834
554 38220962781120560047708
555 40292162908489847579934
556 42473643787753650091752
557 44771175095006554026589
558 47190823123379649138236
559 49738965767870573953791
560 52422308254302666022350
561 55247899648367638166111
562 58223150183146606629024
563 61355849444609513700506
564 64654185457237799619231
565 68126764713158701566205
566 71782633191046396815523
567 75631298412441981117564
568 79682752586252378298439
569 83947496893754396238354
570 88436566969800722860020
571 93161559637677858864164
572 98134660958721782442658
573 103368675659757184323683
574 108877058005391955815722
575 114673944184386819342875
576 120774186283623200980745
577 127193387925632278958030
578 133947941650318084319525
579 141055068124225036094819
580 148532857265769008092394
581 156400311377874363450733
582 164677390384962084928054
583 173385059274594243864863
584 182545337850054631269389
585 192181352903876515272436
586 202317392928816307039856
587 212978965486911168266157
588 224192857364305020880065
589 235987197644115477005858
590 248391523837268181613401
591 261436851216306859467230
592 275155745505502235934413
593 289582399086207250421723
594 304752710885440240331054
595 320704370121897864914482
596 337476944093416332986121
597 355111970196774263680983
598 373653052381398675934081
599 393145962246128863318577
600 413638744999787813788802
601 435181830514692481058950
602 457828149714837331396239
603 481633256549732494313518
604 506655455818577958146376
605 532955937119650859238631
606 560598915214677129760840
607 589651777109194376790141
608 620185236166106264331160
609 652273493582004534850084
610 685994407573441853149775
611 721429670633963657687312
612 758664995241852992526484
613 797790308413535463091526
614 838899955518411445394037
615 882092913787374548014261
616 927473015969917024468845
617 975149184612855206972896
618 1025235677458332532923841
619 1077852344478685519950602
620 1133124897092539881822156
621 1191185190128396842546924
622 1252171517131098892421240
623 1316228919630606535123839
624 1383509511024201469575002
625 1454172815749624657384594
626 1528386124461121091975345
627 1606324865949326994585936
628 1688172996583422628335289
629 1774123408085748026541561
630 1864378354489857289593879
631 1959149899167832473489889
632 2058660382857036625724477
633 2163142913654687517265438
634 2272841879996887089415652
635 2388013487680610369129707
636 2508926322039649093723555
637 2635861936431378903654681
638 2769115468248320561646300
639 2908996283718713438227346
640 3055828652822435975067115
641 3209952455703631096931771
642 3371723922028966821143943
643 3541516404800698392873323
644 3719721190207204667283818
645 3906748345159597603220290
646 4103027604242964391972123
647 4309009297882936558074514
648 4525165323615261655366583
649 4751990162424961543296540
650 4990001942216277572555524
651 5239743550560900892581806
652 5501783798974905494185130
653 5776718641069158295744000
654 6065172447029930041460105
655 6367799336989574946973797
656 6685284575968915294063822
657 7018346033185692863613521
658 7367735708655893446778635
659 7734241330137920538825366
660 8118688023613647351005674
661 8521940060634929073577388
662 8944902686020830836572511
663 9388524029537784927311098
664 9853797105365284231735316
665 10341761903310192830267639
666 10853507575918063489621523
667 11390174725805049587925105
668 11952957797735520222710241
669 12543107580161723733565768
670 13161933821160987402696480
671 13810807963914644223849326
672 14491166007111172947261875
673 15204511495883760001984793
674 15952418649151601355789439
675 16736535629482693138617705
676 17558587961877587681108723
677 18420382108144564787543848
678 19323809203842974678837860
679 20270848965067017965872080
680 21263573772675239904514909
681 22304152941893228392866873
682 23394857185579031059371663
683 24538063279792075270985913
684 25736258940699922472005677
685 26992047922240069446115288
686 28308155344381798141042159
687 29687433262250348104781277
688 31132866486840668153034551
689 32647578668502683097591964
690 34234838654885392828726139
691 35898067135522482161369489
692 37640843585791376152202001
693 39466913523517276720936261
694 41380196092090619327722943
695 43384791984554090333165382
696 45484991723763989277556605
697 47685284314370714471211028
698 49990366283067973526648013
699 52405151124257158739783632
700 54934779169039145549283480
701 57584627896204392494953679
702 60360322704724259719575306
703 63267748168072224201811398
704 66313059791607593195854834
705 69502696295153036878299745
706 72843392443879212330229638
707 76342192451587738004252254
708 80006463981550420618051167
709 83843912771126736002694038
710 87862597907540122395675364
711 92070947783351284606280964
712 96477776761425009553794035
713 101092302580446227510243776
714 105924164533407592585686976
715 110983442452860418571769742
716 116280676538204784739483483
717 121826888061783992552804467
718 127633600992159946712261368
719 133712864574565474731656969
720 140077276910279219190327487
721 146740009578429388008557940
722 153714833345632210842045757
723 161016145010784886781738111
724 168658995434395009624398494
725 176659118803908766003161418
726 185032963188738800180332544
727 193797722440953504500843269
728 202971369500019393821623025
729 212572691162445019333723897
730 222621324379812223385512988
731 233137794151349924118230505
732 244143553080067905484981154
733 255661022664368116250985396
734 267713636400157153272541687
735 280325884771633833868778288
736 293523362212296337418032343
737 307332816121135014021946601
738 321782198022634161996584347
739 336900716962922032851176432
740 352718895238376217540027966
741 369268626557026726893362241
742 386583236737403720960932046
743 404697547053858126218979953
744 423647940342052982516062515
745 443472429983079927339055254
746 464210731889720329290337855
747 485904339623534005585110334
748 508596602776952125226288175
749 532332808760155362528845811
750 557160268138476385796957305
751 583128403672148277217482693
752 610288843216681585732615813
753 638695516648753341213595367
754 668404756989497468138516093
755 699475405904248143015996315
756 731968923765384121140971320
757 765949504472692578956273564
758 801484195233906955591692653
759 838643021516503012266445780
760 877499117390765830466371730
761 918128861493284385393958087
762 960612018849708861363141608
763 1005031888805523447943111451
764 1051475459324078070562480025
765 1100033567921878092920466378
766 1150801069522501164324981426
767 1203877011522173595431569456
768 1259364816372360931830219469
769 1317372471997373538838507459
770 1378012730378341098692425678
771 1441403314648620460386011728
772 1507667135060170229776266081
773 1576932514195288519634008421
774 1649333421813787069329361790
775 1725009719741785744092661736
776 1804107417225295506357742828
777 1886778937189219553858890966
778 1973183393860801217497507142
779 2063486882235471015462966678
780 2157862779882975222357434246
781 2256492061612174760300508191
782 2359563627534489900337540204
783 2467274645088185571976819433
784 2579830905609071301470732508
785 2697447196057262724430188304
786 2820347686534970189153009036
787 2948766334256358649525894501
788 3082947304657939614366937849
789 3223145410366204803811469103
790 3369626568768897172769065650
791 3522668278966911753794088326
792 3682560118915959485561001795
793 3849604263600263929840201625
794 4024116025115356359161401391
795 4206424415572918887733187300
796 4396872733778292014452861358
797 4595819176670118782354947415
798 4803637476552369196385936286
799 5020717565191058228881274192
800 5247466265892099273368202456
801 5484308014722280102744496836
802 5731685612083106585846539045
803 5990061005896562742211061321
804 6259916107713517978116898226
805 6541753643108879060296585880
806 6836098037783508637031872271
807 7143496340850691903244364391
808 7464519186845442567263348320
809 7799761798057448155465415793
810 8149845028853920278331536484
811 8515416453726257887888390599
812 8897151500865253421118208927
813 9295754633142762756851057126
814 9711960578454370172883940219
815 10146535611456767294912051029
816 10600278888816430176737304925
817 11074023840171847027915968850
818 11568639617101172681895955776
819 12085032602479857105642376201
820 12624147982709720760536587802
821 13186971385401187367623737619
822 13774530585195198673041970998
823 14387897280519748494464143680
824 15028188944189308947984252286
825 15696570750872665994128559806
826 16394257584577221759483443307
827 17122516129424605436802360438
828 17882667047124916705292376567
829 18676087244694014626523385061
830 19504212236101484228318965277
831 20368538601685131612131427706
832 21270626549322672811769262890
833 22212102581511519854919355980
834 23194662272674902632793711262
835 24220073161185783121927379479
836 25290177760780872870508428611
837 26406896696224298011683190533
838 27572231968275906598185387023
839 28788270353221578920672603989
840 30057186942434109709925884096
841 31381248827651934354302545751
842 32762818937891189857173697409
843 34204360034142941242938891477
844 35708438868253983893608800689
845 37277730512645010242088873583
846 38915022867786326801087412277
847 40623221354627234323689355851
848 42405353799462969724004454529
849 44264575519021213175068104120
850 46204174613861031119286388525
851 48227577478499165042618131350
852 50338354537014350047534120971
853 52540226213228214138592033384
854 54837069144923957867127625413
855 57232922651939749701594860736
856 59731995468365416721477673516
857 62338672749476814818215179814
858 65057523364465188320955933537
859 67893307486457073614538158647
860 70850984491776972230554318937
861 73935721180878259125438183404
862 77152900333860862943448507985
863 80508129614005244794699362925
864 84007250833284534306203133882
865 87656349594368388460464835591
866 91461765324206814769334017041
867 95430101714877821599340013391
868 99568237588003099620946441890
869 103883338199678919100095060891
870 108382867003539012241851428977
871 113074597890260261377759421740
872 117966627922544696259253833391
873 123067390585360424218328480623
874 128385669572004049573226632881
875 133930613127355634657817853722
876 139711748970538909970788759677
877 145738999820071951036733107364
878 152022699545501734020322069091
879 158573609970457502185004858845
880 165402938353037796574056362856
881 172522355570461914489788055027
882 179944015035973793802962658009
883 187680572377082415187179983145
884 195745205905363377330533170688
885 204151637909228816707756452004
886 212914156802303211811467157258
887 222047640161318267846296083853
888 231567578688767224889800437238
889 241490101136934960040753999212
890 251832000231351687015884197327
891 262610759633202241072673367267
892 273844581981766737558803189138
893 285552418059569114566557107038
894 297753997124574937256593729595
895 310469858455506122527700325338
896 323721384158135539752949069206
897 337530833282285993104109948674
898 351921377301193895441818919974
899 366917137006905212325478192591
900 382543220877458411928037966662
901 398825764973773390120440133283
902 415791974426415520897348198541
903 433470166574737282699226768968
904 451889815823325674228300397649
905 471081600283199022663947612437
906 491077450267811644984144323122
907 511910598716636312398929481179
908 533615633621912958657802544704
909 556228552537074736513181160883
910 579786819248400290926076758341
911 604329422694591172200793629266
912 629896938222247175560099277193
913 656531591268607284316550526176
914 684277323566451954929565468457
915 713179861969720973754228732187
916 743286790002202841437054607319
917 774647622235593916382783235139
918 807313881607321877593139443884
919 841339179792775833711770692674
920 876779300750998854390177983495
921 913692287567475302373556211628
922 952138532722400129690365881355
923 992180871917747843362071209854
924 1033884681601581005947603350364
925 1077317980333349612163837733658
926 1122551534139450216146809165218
927 1169658966014035118446399345547
928 1218716869726004931900527705800
929 1269804928099280444473878235661
930 1323006035939850548151276644814
931 1378406427789730314975366940236
932 1436095810694856785794873515470
933 1496167502181098127385248687976
934 1558718573639975332168266931038
935 1623849999333393270422057014226
936 1691666811234671659148508188339
937 1762278259931455362735043784694
938 1835797981824690639965356160124
939 1912344172866778804583182850352
940 1992039769091285850489379741396
941 2075012634196195579802262847710
942 2161395754452670647774549969918
943 2251327441221630786220534634814
944 2344951541371197765663074065984
945 2442417655899192948446473109838
946 2543881367076434634934316511315
947 2649504474438569866737631241844
948 2759455239966619672281040858085
949 2873908642809319543102806751021
950 2993046643913730749107813196884
951 3117058460944485189445111141381
952 3246140853886441265966274273029
953 3380498421740473706786093006156
954 3520343910737632807944763848977
955 3665898534512991918839454939216
956 3817392306697194763944640394680
957 3975064386401020934083585408681
958 4139163437086249463440790154910
959 4309947999334722330876494067653
960 4487686878046835273501432801371
961 4672659544620718998632131538485
962 4865156554684165586392253559938
963 5065479981972910235347073438450
964 5273943868971246110628592370671
965 5490874694954138786179939770087
966 5716611862094068129831777923257
967 5951508200320769688652735799580
968 6195930491647929283515376387305
969 6450260014707715317543212047249
970 6714893110261871121882615923705
971 6990241768486947816510392467810
972 7276734238861198029775075096628
973 7574815663511687468377388652835
974 7884948734912379856713262086671
975 8207614378857328158009253700710
976 8543312463667730305721270313539
977 8892562536627499987575642502231
978 9255904588679235605956217948884
979 9633899848451064735376387809777
980 10027131606724874964493541336977
981 10436206072497938767353289961312
982 10861753261832982523545202803819
983 11304427920736364508220870142375
984 11764910483350301209475847209247
985 12243908066793045130206983373803
986 12742155504030663314003573487546
987 13260416416215626796897210539612
988 13799484325980895810082965367255
989 14360183813233609878439913858553
990 14943371715049970892935566261462
991 15549938371332480545227156778010
992 16180808917952472652504230418912
993 16836944629164909673540600511875
994 17519344311148809536884849072488
995 18229045748595481949131867432209
996 18967127206338108455309695214491
997 19734708988090150602224296131415
998 20532955054436749340673693733025
999 21363074702302744338216601289187
1000 22226324308203336311243836988805