0 1
1 0
2 1
3 1
4 1
5 1
6 2
7 3
8 5
9 7
10 10
11 13
12 18
13 23
14 31
15 40
16 53
17 68
18 89
19 113
20 146
21 184
22 234
23 293
24 369
25 458
26 572
27 706
28 874
29 1073
30 1320
31 1611
32 1970
33 2393
34 2909
35 3518
36 4255
37 5122
38 6167
39 7394
40 8862
41 10585
42 12637
43 15038
44 17886
45 21213
46 25141
47 29723
48 35112
49 41383
50 48737
51 57278
52 67258
53 78830
54 92313
55 107913
56 126042
57 146980
58 171246
59 199224
60 231571
61 268796
62 311742
63 361079
64 417869
65 483007
66 557835
67 643516
68 741757
69 854070
70 982605
71 1129331
72 1296956
73 1488011
74 1705921
75 1953931
76 2236338
77 2557311
78 2922241
79 3336429
80 3806652
81 4339640
82 4943867
83 5627872
84 6402240
85 7277743
86 8267613
87 9385404
88 10647587
89 12071210
90 13676759
91 15485570
92 17523115
93 19816050
94 22395948
95 25296073
96 28555511
97 32215629
98 36324785
99 40934322
100 46103918
101 51897226
102 58387800
103 65654325
104 73787374
105 82884059
106 93055675
107 104421912
108 117119346
109 131295160
110 147116790
111 164764933
112 184444475
113 206376977
114 230812833
115 258023171
116 288313663
117 322015615
118 359501578
119 401175863
120 447491967
121 498942462
122 556078768
123 619500151
124 689876115
125 767934845
126 854488243
127 950419794
128 1056712994
129 1174438384
130 1304785742
131 1449050720
132 1608670979
133 1785212487
134 1980410562
135 2196155598
136 2434539616
137 2697842076
138 2988582253
139 3309505298
140 3663641822
141 4054294077
142 4485103629
143 4960038586
144 5483470025
145 6060160696
146 6695352043
147 7394754457
148 8164646314
149 9011867186
150 9943929989
151 10969017945
152 12096112540
153 13334994728
154 14696390807
155 16191979971
156 17834560022
157 19638062785
158 21617743437
159 23790204962
160 26173614432
161 28787739733
162 31654195896
163 34796496694
164 38240336595
165 42013659654
166 46146982105
167 50673483501
168 55629375050
169 61054017455
170 66990343067
171 73485004775
172 80588859838
173 88357157521
174 96850092621
175 106133039167
176 116277185659
177 127359822470
178 139465070739
179 152684235315
180 167116640101
181 182870058438
182 200061672667
183 218818594678
184 239278968139
185 261592597567
186 285922213044
187 312444226834
188 341350187259
189 372847683706
190 407162017737
191 444537284685
192 485238292952
193 529551852339
194 577788981318
195 630286435445
196 687409245568
197 749552529788
198 817144410126
199 890648155149
200 970565534960
201 1057439347242
202 1151857275761
203 1254454866304
204 1365919961733
205 1486996201061
206 1618488120603
207 1761265258555
208 1916268021296
209 2084512494985
210 2267097188146
211 2465208662977
212 2680129288764
213 2913243820400
214 3166048312073
215 3440157797198
216 3737316531159
217 4059406945249
218 4408461419664
219 4786672706963
220 5196407460678
221 5640218361729
222 6120859657314
223 6641301252617
224 7204746560973
225 7814648858846
226 8474731785177
227 9189008311395
228 9961804273147
229 10797780352196
230 11701959089100
231 12679750327824
232 13736982215205
233 14879930636420
234 16115354774664
235 17450531134364
236 18893294328640
237 20452076368955
238 22135953433976
239 23954691215087
240 25918798522256
241 28039579579086
242 30329195455727
243 32800724329357
244 35468231864002
245 38346840612176
246 41452810612296
247 44803619263218
248 48418053604168
249 52316302175889
250 56520060640532
251 61052637373183
252 65939074303133
253 71206268212084
254 76883108956913
255 83000618719465
256 89592110056609
257 96693345678900
258 104342719102286
259 112581437876023
260 121453730012919
261 131007053982124
262 141292334514008
263 152364203152433
264 164281267512473
265 177106386691423
266 190906978635940
267 205755335288924
268 221728973337422
269 238910994663099
270 257390486444016
271 277262933213564
272 298630673122579
273 321603368754012
274 346298527246066
275 372842038003243
276 401368765401544
277 432023162609855
278 464959946794325
279 500344799485594
280 538355135498190
281 579180901706853
282 623025452371833
283 670106459742370
284 720656910195811
285 774926141852732
286 833180977812997
287 895706908014002
288 962809377975354
289 1034815134376617
290 1112073690179176
291 1194958855943389
292 1283870404898275
293 1379235814948414
294 1481512160319223
295 1591188092432187
296 1708785988265880
297 1834864201930428
298 1970019503760482
299 2114889638603861
300 2270156094044387
301 2436547006047808
302 2614840299718881
303 2805866988173659
304 3010514734781832
305 3229731597097194
306 3464530065792511
307 3715991312092177
308 3985269765732074
309 4273597931795263
310 4582291577937582
311 4912755195002782
312 5266487872667027
313 5645089487630124
314 6050267356944008
315 6483843248183782
316 6947760910973147
317 7444094015560983
318 7975054675711667
319 8543002435491795
320 9150453911017386
321 9800092960303451
322 10494781587307183
323 11237571446702983
324 12031716171587192
325 12880684383992027
326 13788173627854640
327 14758125077372006
328 15794739279392132
329 16902492775725176
330 18086155884435371
331 19350811478991510
332 20701875066471277
333 22145115996475204
334 23686680126065056
335 25333113765183929
336 27091389253831213
337 28968931988445849
338 30973649276950434
339 33113960832834968
340 35398831318459542
341 37837804741096738
342 40441041145030000
343 43219355396812515
344 46184258543018427
345 49348001531339360
346 52723621813654789
347 56324992616206753
348 60166875437974331
349 64264975557467838
350 68636001155247962
351 73297725828024758
352 78269055152103291
353 83570097068660132
354 89222236803257945
355 95248216090083538
356 101672217472846868
357 108519953451947711
358 115818761314906551
359 123597703420483981
360 131887673844070958
361 140721511157774289
362 150134118329775296
363 160162589521370027
364 170846344850490725
365 182227272907812785
366 194349882185790554
367 207261461217787399
368 221012248687621238
369 235655613320990821
370 251248244928558029
371 267850356430637201
372 285525898352449111
373 304342785643419602
374 324373138439792471
375 345693536652624108
376 368385290143217223
377 392534724402926818
378 418233483655126227
379 445578851338565621
380 474674090060374039
381 505628801027876650
382 538559305234414285
383 573589046467521699
384 610849018618843671
385 650478217434111752
386 692624119406296016
387 737443188031522136
388 785101410376416762
389 835774864271136059
390 889650319345321640
391 946925872331374588
392 1007811620146860207
393 1072530371306986259
394 1141318399502484224
395 1214426240039586935
396 1292119533331733760
397 1374679916307421144
398 1462405966312736467
399 1555614198564274064
400 1654640122158377524
401 1759839355910914145
402 1871588809502109560
403 1990287931450131807
404 2116360029902692727
405 2250253668053267225
406 2392444140737211816
407 2543435034335616321
408 2703759877163304435
409 2873983882833403265
410 3054705794457651589
411 3246559832586502335
412 3450217755499325753
413 3666391035213951297
414 3895833158650802349
415 4139342057846385387
416 4397762679558673183
417 4671989698750392504
418 4962970387291313301
419 5271707643031208317
420 5599263191682007703
421 5946760967410007735
422 6315390685784158903
423 6706411615821757192
424 7121156566106978610
425 7561036092666893199
426 8027542945042243616
427 8522256759296079152
428 9046849016006575905
429 9603088273171652672
430 10192845693843652582
431 10818100879747761726
432 11480948032651747419
433 12183602456224791316
434 12928407422299170925
435 13717841415930008165
436 14554525785530701602
437 15441232814330697705
438 16380894242034564448
439 17376610254996632116
440 18431658976654761913
441 19549506478842456967
442 20733817348878375264
443 21988465835622361299
444 23317547612870402728
445 24725392186142207073
446 26216575985059074006
447 27795936170554161856
448 29468585203326745906
449 31239926206331630798
450 33115669172354397806
451 35101848053413222391
452 37204838788147310015
453 39431378308322590662
454 41788584586243129969
455 44283977769078318869
456 46925502468091063013
457 49721551254199261162
458 52680989434680646820
459 55813181168472518371
460 59128017002394123550
461 62635942892425010073
462 66347990800644000836
463 70275810939377688139
464 74431705762278320758
465 78828665782102731228
466 83480407324951622999
467 88401412309858140218
468 93606970174537806229
469 99113222046295590841
470 104937207291073031868
471 111096912550826599566
472 117611323415623105215
473 124500478853043574551
474 131785528556035558624
475 139488793345537044537
476 147633828805256080255
477 156245492300125643484
478 165350013573703017366
479 174975069092848738311
480 185149860354639859082
481 195905196342455883188
482 207273580367861385835
483 219289301505793220927
484 231988530883529458414
485 245409423053688934780
486 259592222737987893885
487 274579377197139145839
488 290415654542508364579
489 307148268272683650686
490 324827008382364681755
491 343504379357404651378
492 363235745438389095988
493 384079483500465681985
494 406097143970293454170
495 429353620165228550826
496 453917326517955985464
497 479860386112970111377
498 507258828044686294092
499 536192795069148979927
500 566746762110346701412
501 599009766143362191016
502 633075648071713662773
503 669043307176556092231
504 707016968817058875376
505 747106466020768893274
506 789427535711408838828
507 834102130280321940263
508 881258745323929822192
509 931032764327709396094
510 983566821201413942368
511 1039011181527921617316
512 1097524143520972467792
513 1159272459644382387312
514 1224431779987512994679
515 1293187118448951633727
516 1365733342932550024944
517 1442275690717212886998
518 1523030310324775336354
519 1608224831167854884069
520 1698098962434087331924
521 1792905122621282096951
522 1892909101325004423618
523 1998390754839125869292
524 2109644737330251190118
525 2226981269307227169889
526 2350726945321738465767
527 2481225582797964250589
528 2618839114119605791140
529 2763948524066712360190
530 2916954834941804144324
531 3078280141691575554802
532 3248368699595581217796
533 3427688067063347956438
534 3616730306365922863623
535 3816013245101844272244
536 4026081801503057199953
537 4247509376664947502000
538 4480899317112835798412
539 4726886451101434828196
540 4986138702396352453639
541 5259358785277346903893
542 5547285984881963728854
543 5850698027006308904151
544 6170413041887093706003
545 6507291626495876193667
546 6862239010314529672668
547 7236207329577739385779
548 7630198015439619984705
549 8045264301549737783749
550 8482513857030989598363
551 8943111550893006862677
552 9428282354460688098309
553 9939314388453510213691
554 10477562121939110183295
555 11044449730457479350812
556 11641474621245290908716
557 12270211133581727399228
558 12932314422959381945765
559 13629524537897102089778
560 14363670698946892053019
561 15136675789584414964285
562 15950561069465303952393
563 16807451120694018854831
564 17709579038606793601779
565 18659291878765160499548
566 19659056372778617943377
567 20711464925803982476378
568 21819241909563918493759
569 22985250264994147730417
570 24212498429702708304585
571 25504147605734119664439
572 26863519384290662326280
573 28294103744419802593027
574 29799567443928797140601
575 31383762821197026134639
576 33050737027909003534938
577 34804741713199151769592
578 36650243181160642019659
579 38591933044203848378539
580 40634739396329173245519
581 42783838530984496128523
582 45044667229884630639836
583 47422935649855802860377
584 49924640836614015937064
585 52556080895160544336607
586 55323869848474140830254
587 58234953217052141449843
588 61296624354012218762807
589 64516541571447801537461
590 67902746096066820100989
591 71463680893244776574023
592 75208210401151950911132
593 79145641217848489446179
594 83285743786978452950070
595 87638775129074212484307
596 92215502668446207116615
597 97027229207174811843593
598 102085819100930352621088
599 107403725693066964504614
600 112994020066911927873122
601 118870421178087829692219
602 125047327432470307979674
603 131539849777515691945974
604 138363846378772589837930
605 145535958955760551939022
606 153073650855819952220064
607 160995246947167611743800
608 169319975417184281316117
609 178068011564877737652353
610 187260523681659324953546
611 196919721117805071730033
612 207068904637603676241924
613 217732519169773736289869
614 228936209065838471099200
615 240706875983107000364432
616 253072739515532779377142
617 266063400700098465997333
618 279709908533558119775563
619 294044829639204805403014
620 309102321231121689763119
621 324918207528714698501470
622 341530059782775771846347
623 358977280080216955430055
624 377301189103784529070070
625 396545118029557734091365
626 416754504754985622385954
627 437976994657372777247637
628 460262546093521069343823
629 483663540859116715230998
630 508234899838168975378021
631 534034204081482651192705
632 561121821565863834353669
633 589561039895302911544457
634 619418205219182889618920
635 650762867653056227736095
636 683667933502518122416402
637 718209824602239235948862
638 754468645098488393713810
639 792528356016148063254570
640 832476957968886737516293
641 874406682385067997828941
642 918414191641151592322650
643 964600788509616658900062
644 1013072635349257939292102
645 1063940983482465816176212
646 1117322413226709190054144
647 1173339085065822765958871
648 1232119002471250432284645
649 1293796286903551305921063
650 1358511465551134861758378
651 1426411772385281800920576
652 1497651463139459262138127
653 1572392144845142115595004
654 1650803120587794072579100
655 1733061750173171834963515
656 1819353827428262544079006
657 1909873974890191110688352
658 2004826056673519690801849
659 2104423610338133871368327
660 2208890298620187983509687
661 2318460381923349765625981
662 2433379212511329942923735
663 2553903751380716982267679
664 2680303108840649188428738
665 2812859109867453201561047
666 2951866885353980965570296
667 3097635490418857745519515
668 3250488550996900254549830
669 3410764939981677513067264
670 3578819484252059689263098
671 3755023703968926868581436
672 3939766585594323677416991
673 4133455390144698990081198
674 4336516498261675994037726
675 4549396293748627163376630
676 4772562087299316154607984
677 5006503082215662446360518
678 5251731383996384308304953
679 5508783055755565254423907
680 5778219221522177356436097
681 6060627219555957278212192
682 6356621807914932951575652
683 6666846424601961450952717
684 6991974504726132874337449
685 7332710857215339542208472
686 7689793103734132305694657
687 8063993182570552526189807
688 8456118920383577715846057
689 8867015674822312197543022
690 9297568051166996738172412
691 9748701696272204901940514
692 10221385173243469302523824
693 10716631920420623883672121
694 11235502298404976053280599
695 11779105729022244869858820
696 12348602930291086816875541
697 12945208251635751328601503
698 13570192113774550034333273
699 14224883557899656921059771
700 14910672908973455130369516
701 15629014558166910168486070
702 16381429869693114136759232
703 17169510217507271480065794
704 17994920157591556296789611
705 18859400741780811644547459
706 19764772979353372822621981
707 20712941452869936395115431
708 21705898095034656565957520
709 22745726133634218050405981
710 23834604211926789966944013
711 24974810692159243759916639
712 26168728150234179959575820
713 27418848069881849370762336
714 28727775745064509965050207
715 30098235399703697535116359
716 31533075534225116815616316
717 33035274508810723123577161
718 34607946373686252918593645
719 36254346957201995800214072
720 37977880222940659376832421
721 39782104907553359116743279
722 41670741451541348704311398
723 43647679235709159506340113
724 45716984136575342911484952
725 47882906414579431843380169
726 50149888949531906150247444
727 52522575838354529480107720
728 55005821370818246495012509
729 57604699399638680794170594
730 60324513122005091262819673
731 63170805290328216917214092
732 66149368870768957241606275
733 69266258168880953001613833
734 72527800442542442755114541
735 75940608023190661049359956
736 79511590967285664057183845
737 83247970260840795023740566
738 87157291600847903536457512
739 91247439778414330146088651
740 95526653689503317691588600
741 100003542000243623834883937
742 104687099494939508190069612
743 109586724136078792952748510
744 114712234866900421887405018
745 120073890188349674557867324
746 125682407543619448484838941
747 131548983544851399728003232
748 137685315078056396696609882
749 144103621323806903245063299
750 150816666732864588306057912
751 157837784997527297234199834
752 165180904061225616102815003
753 172860572210658483912290257
754 180891985296650070555436235
755 189291015131819339890664346
756 198074239115205320852729679
757 207258971136062835679799370
758 216863293811267049701579812
759 226906092113013035790743803
760 237407088445906422997876417
761 248386879234979823130974307
762 259866973088781279677481172
763 271869830604326302130225737
764 284418905883534945315974283
765 297538689833644607037237745
766 311254755327155491730086049
767 325593804299977404825141139
768 340583716869768694994391664
769 356253602559832511366854725
770 372633853717534660769994139
771 389756201219866104894972887
772 407653772562672023073255735
773 426361152434036073426112913
774 445914445876531792028986189
775 466351344147353194580975055
776 487711193389911026419571651
777 510035066235142185356756509
778 533365836455734111611643578
779 557748256801517744820927425
780 583229040149647951941649719
781 609856944108665052676381739
782 637682859221341071243802017
783 666759900917146781431404392
784 697143505371466696861166821
785 728891529435116927375875950
786 762064354804532309673549253
787 796724996609952978274674073
788 832939216606314921389256020
789 870775641159092754274475148
790 910305884225326123575654486
791 951604675538232260586969835
792 994749994212448787712380526
793 1039823207995800717191401598
794 1086909218402839161834051498
795 1136096611974983285868685252
796 1187477817922220490203612745
797 1241149272411697909506138487
798 1297211589779494182050422341
799 1355769740953097323925825913
800 1416933239383970380761235858
801 1480816334801752091116860487
802 1547538215114468541025791688
803 1617223216792301544823446572
804 1690001044086339911427500383
805 1766006997447995254177494762
806 1845382211529781169957186982
807 1928273903163583922665183485
808 2014835629728798528078182448
809 2105227558339402357324573027
810 2199616746296611900312043469
811 2298177433271838149330051823
812 2401091345703664410452478494
813 2508548013912122636905389390
814 2620745102454103123969096697
815 2737888754264886853068277475
816 2860193949153023669086111482
817 2987884877238665296243700709
818 3121195327949505896908885906
819 3260369095213239544404242690
820 3405660399511442808136723512
821 3557334327486568698776488209
822 3715667289821849007380594109
823 3880947498142863972711194542
824 4053475461719930191836154518
825 4233564504781778768100584453
826 4421541305283851475257317184
827 4617746456008412166260957694
828 4822535048909187265040705776
829 5036277283649871137700071569
830 5259359101324222131396155124
831 5492182844385069778957975115
832 5735167943851046342449893565
833 5988751634902660933479459937
834 6253389702024177149284559270
835 6529557254894026895419239511
836 6817749536274952579186891045
837 7118482763205084726633332446
838 7432295002843526138660036202
839 7759747084378069898923002528
840 8101423548459257465346224784
841 8457933635683402199103167853
842 8829912315708332085164317562
843 9218021358648734253193175220
844 9622950450464022611407872620
845 10045418354119862462787221232
846 10486174118375824018826922829
847 10945998336125336213791858577
848 11425704454291169042775064431
849 11926140137359293805804699517
850 12448188686717198404482498317
851 12992770518048746349169547025
852 13560844699127554263747165206
853 14153410550443769774850177595
854 14771509311196201551449331926
855 15416225873282100544219437468
856 16088690586021711369642950329
857 16790081134463087231367502492
858 17521624494225841962967653974
859 18284598965959547006137497538
860 19080336292614679295038586463
861 19910223862850401778444458734
862 20775707004035383121483096085
863 21678291368434315064337131238
864 22619545416315200984041667201
865 23601102999859808901258107455
866 24624666051913410222937522286
867 25692007383768965840292672074
868 26804973596346848583519165449
869 27965488109302870836814059354
870 29175554312776467663128644193
871 30437258846676194904757289587
872 31752775012592965965365717592
873 33124366323631455653792941850
874 34554390197658654242958754688
875 36045301799684403593785334913
876 37599658039313785674949058278
877 39220121729444163464226356422
878 40909465912622481401000506903
879 42670578361729775294875075779
880 44506466261921801267686458439
881 46420261081025883655399127535
882 48415223635876684016580514050
883 50494749362366176066335248681
884 52662373797287960508874742287
885 54921778280371691957764628098
886 57276795885232213587152123733
887 59731417588298479618333536756
888 62289798685142003134802790562
889 64956265463991825243795710721
890 67735322146605494822021015210
891 70631658107061655952314841109
892 73650155379452324101982665442
893 76795896465880123175772567039
894 80074172456610549659163786690
895 83490491474690008772804459294
896 87050587457819968108696962286
897 90760429290774328327333215033
898 94626230302164204065125193850
899 98654458139889922659996787542
900 102851845040177525959548207608
901 107225398505674532213135891675
902 111782412408680687731160207818
903 116530478536211991823077139577
904 121477498594244093540254488843
905 126631696689152264460273013735
906 132001632305063410475702374010
907 137596213796558976267418190838
908 143424712416920173058819063564
909 149496776902886652127491734971
910 155822448637710809663183471656
911 162412177415130221961566892761
912 169276837827754742709318171454
913 176427746304270376321684632959
914 183876678820803866177992727230
915 191635889312767786210694878819
916 199718128814520728064204889794
917 208136665355228669167984799914
918 216905304640406967890205241171
919 226038411549755350335089502069
920 235550932483076169986203542781
921 245458418587286782625156711941
922 255777049898805802020414901945
923 266523660436907891718892573501
924 277715764285008613786950665584
925 289371582698257262575353607002
926 301510072277287877021529784577
927 314150954249504278711162599355
928 327314744900860665889526114215
929 341022787202742503268102002781
930 355297283680260167191617269166
931 370161330570037504162269529795
932 385638953317416482567962900643
933 401755143464904906977243186216
934 418535896985674447670533423430
935 436008254117968439963044760673
936 454200340758411157170430389225
937 473141411474419968693798439916
938 492861894198217514738979082558
939 513393436667320164961480509345
940 534768954678850583103875449534
941 557022682227583596198356231382
942 580190223600295242948181479622
943 604308607501742261450096675723
944 629416343290463350707270806778
945 655553479405561729331739693279
946 682761664068711327648257267142
947 711084208348823837606627524422
948 740566151680131877935973631772
949 771254329927882197652894293442
950 803197446099403801171141678480
951 836446143802016668801106417759
952 871053083553089655639296320253
953 907073022051538776825893394585
954 944562894524192378818130111957
955 983581900264735327294646971933
956 1024191591487393964565846543128
957 1066455965622134966820125672847
958 1110441561182938758064532839615
959 1156217557345669685724597543751
960 1203855877377215911657116611744
961 1253431296062909921907583283855
962 1305021551284781719257612945918
963 1358707459908939282963743333836
964 1414573038146331650593098152600
965 1472705626557327317141147552058
966 1533196019876952379307865948460
967 1596138601844277493513623475739
968 1661631485226339074924935087859
969 1729776657234126980128606830215
970 1800680130535588044153224436684
971 1874452100078281274618600816545
972 1951207105942297206353465765172
973 2031064202452320165037480607430
974 2114147133786290117512049383090
975 2200584516327009995450191055170
976 2290510028012268252605625048316
977 2384062604948604907965836142681
978 2481386645563767142670471249653
979 2582632222583178011065541636602
980 2687955303126405100693960187706
981 2797517977230665830366268606597
982 2911488695119870099634538108107
983 3030042513549580488260438812987
984 3153361351570594315817974351015
985 3281634256066622446897103985031
986 3415057677434787602979834376729
987 3553835755791392559103824428375
988 3698180618099648571964743024888
989 3848312686630809813134554018286
990 4004460999185464958993660926666
991 4166863541517596257992439053456
992 4335767592420465846492290801710
993 4511430081950433462992139246407
994 4694117963282487628931293877599
995 4884108598709589353695928601569
996 5081690160316924346463743569058
997 5287162045881843079502993747919
998 5500835310570681103302010786412
999 5723033115024802327163862198822
1000 5954091190450141347516381740043