0 1
1 0
2 1
3 1
4 1
5 2
6 3
7 3
8 4
9 5
10 8
11 9
12 12
13 13
14 17
15 22
16 28
17 34
18 42
19 48
20 59
21 71
22 88
23 106
24 130
25 151
26 181
27 210
28 250
29 295
30 354
31 417
32 494
33 577
34 675
35 780
36 909
37 1053
38 1231
39 1431
40 1668
41 1930
42 2240
43 2573
44 2963
45 3392
46 3896
47 4461
48 5129
49 5873
50 6742
51 7710
52 8816
53 10043
54 11439
55 12981
56 14742
57 16708
58 18957
59 21482
60 24364
61 27582
62 31236
63 35299
64 39876
65 44949
66 50645
67 56949
68 64039
69 71923
70 80805
71 90693
72 101822
73 114193
74 128064
75 143455
76 160630
77 179633
78 200777
79 224122
80 250078
81 278782
82 310713
83 346067
84 385409
85 428959
86 477361
87 530882
88 590220
89 655710
90 728161
91 807934
92 896008
93 992902
94 1099791
95 1217401
96 1347180
97 1490009
98 1647625
99 1821084
100 2012333
101 2222652
102 2454261
103 2708625
104 2988300
105 3295025
106 3631721
107 4000560
108 4405040
109 4847890
110 5333374
111 5864905
112 6447516
113 7085353
114 7784285
115 8549161
116 9386758
117 10302778
118 11304945
119 12399902
120 13596542
121 14902580
122 16328378
123 17883167
124 19579173
125 21427644
126 23443206
127 25639360
128 28033429
129 30641496
130 33483705
131 36578947
132 39950576
133 43620504
134 47615639
135 51961404
136 56688616
137 61826778
138 67411448
139 73476976
140 80064844
141 87215761
142 94978365
143 103401028
144 112540967
145 122455161
146 133210485
147 144873685
148 157522172
149 171233646
150 186097405
151 202203136
152 219653574
153 238552184
154 259016688
155 281166397
156 305136715
157 331065668
158 359110092
159 389430862
160 422210315
161 457636580
162 495921918
163 537285560
164 581973884
165 630241502
166 682372890
167 738662378
168 799437340
169 865036526
170 935835617
171 1012223616
172 1094630404
173 1183502077
174 1279330680
175 1382628090
176 1493958990
177 1613913140
178 1743140631
179 1882322921
180 2032210249
181 2193590158
182 2367328009
183 2554332769
184 2755600032
185 2972176090
186 3205203616
187 3455883113
188 3725522772
189 4015497121
190 4327300166
191 4662502357
192 5022807615
193 5410007820
194 5826045703
195 6272967226
196 6752989836
197 7268453778
198 7821895663
199 8415996367
200 9053661211
201 9737963705
202 10472230625
203 11259982919
204 12105026300
205 13011387418
206 13983412532
207 15025698859
208 16143200410
209 17341156473
210 18625204963
211 20001306233
212 21475867357
213 23055661461
214 24747962475
215 26560463789
216 28501425009
217 30579588624
218 32804341821
219 35185629901
220 37734130963
221 40461167121
222 43378890867
223 46500191134
224 49838894666
225 53409665844
226 57228221905
227 61311229714
228 65676535880
229 70343058790
230 75331037827
231 80661920447
232 86358630495
233 92445453889
234 98948327708
235 105894724495
236 113313969672
237 121237127221
238 129697347443
239 138729759196
240 148371850542
241 158663363994
242 169646713060
243 181366878015
244 193871855519
245 207212556668
246 221443290059
247 236621658413
248 252809081866
249 270070693596
250 288475903531
251 308098298467
252 329016250513
253 351312820131
254 375076418034
255 400400713225
256 427385351040
257 456135875433
258 486764512182
259 519390110337
260 554139007938
261 591145001890
262 630550301939
263 672505538517
264 717170810452
265 764715726002
266 815320551075
267 869176282100
268 926485892008
269 987464440251
270 1052340421257
271 1121355908848
272 1194768021968
273 1272849109167
274 1355888335698
275 1444191922319
276 1538084866762
277 1637911239022
278 1744036058283
279 1856845655437
280 1976749717444
281 2104181743086
282 2239601281633
283 2383494501644
284 2536376667344
285 2698792848236
286 2871320656334
287 3054571126207
288 3249191734356
289 3455867452797
290 3675324074312
291 3908329444435
292 4155697098479
293 4418287689965
294 4697012955828
295 4992837347773
296 5306782362731
297 5639928396314
298 5993419462667
299 6368465308289
300 6766346558859
301 7188417116732
302 7636109789292
303 8110939005589
304 8614506970958
305 9148506765495
306 9714729094542
307 10315065834590
308 10951517486586
309 11626197257585
310 12341339308856
311 13099303472908
312 13902584386571
313 14753816903590
314 15655786197361
315 16611433922284
316 17623869337931
317 18696376282061
318 19832425379567
319 21035681874365
320 22310019017796
321 23659526832250
322 25088526763677
323 26601581485210
324 28203510930011
325 29899403231934
326 31694632287243
327 33594869956508
328 35606105293728
329 37734658172006
330 39987200358999
331 42370770741120
332 44892798498268
333 47561120172099
334 50384005216878
335 53370175223473
336 56528832169700
337 59869680085652
338 63402956334009
339 67139455992538
340 71090566432062
341 75268294682245
342 79685305568770
343 84354952282900
344 89291318369889
345 94509251759869
346 100024410889597
347 105853302514128
348 112013332314621
349 118522846818370
350 125401188920546
351 132668744315270
352 140347002370598
353 148458607549636
354 157027426153594
355 166078603223459
356 175638635770983
357 185735435772441
358 196398410577087
359 207658532781654
360 219548428698573
361 232102456005824
362 245356801329412
363 259349566695889
364 274120877291104
365 289712977797395
366 306170351404642
367 323539827021902
368 341870710623822
369 361214904330606
370 381627051105985
371 403164666766581
372 425888299138389
373 449861674074227
374 475151870327665
375 501829480818360
376 529968804566056
377 559648024648450
378 590949418735046
379 623959555280436
380 658769524425719
381 695475154178040
382 734177263559862
383 774981900791181
384 818000620857890
385 863350747945677
386 911155680026836
387 961545178262023
388 1014655701606062
389 1070630726426590
390 1129621114604810
391 1191785466911164
392 1257290528426468
393 1326311579445004
394 1399032882076171
395 1475648112572956
396 1556360853067434
397 1641385069190716
398 1730945651050646
399 1825278940198406
400 1924633324085000
401 2029269816772025
402 2139462711493936
403 2255500219821978
404 2377685187496506
405 2506335797303030
406 2641786353776546
407 2784388055683065
408 2934509855841141
409 3092539309599868
410 3258883516730842
411 3433970053027093
412 3618248001876603
413 3812188977053940
414 4016288252662507
415 4231065886265898
416 4457067957319579
417 4694867801293532
418 4945067368075943
419 5208298579254012
420 5485224819352517
421 5776542429453868
422 6082982345175598
423 6405311740661542
424 6744335827741662
425 7100899665002626
426 7475890133226267
427 7870237924754161
428 8284919711149106
429 8720960329020070
430 9179435156752749
431 9661472514270876
432 10168256267156366
433 10701028459212964
434 11261092164079346
435 11849814371353417
436 12468629107574122
437 13119040598770053
438 13802626684874203
439 14521042283588988
440 15276023124731372
441 16069389542877347
442 16903050560677866
443 17779008040911120
444 18699361151390627
445 19666310910766017
446 20682165072080270
447 21749343101395421
448 22870381521662003
449 24047939368140083
450 25284804038954355
451 26583897275373167
452 27948281569524588
453 29381166721305260
454 30885916856823243
455 32466057616982754
456 34125283843447681
457 35867467456882709
458 37696665870765041
459 39617130621076635
460 41633316572149119
461 43749891364271055
462 45971745480859684
463 48304002585623931
464 50752030526424685
465 53321452640051773
466 56018159774544010
467 58848322646852477
468 61818404972938627
469 64935176971033214
470 68205729697115895
471 71637489795144948
472 75238235144363304
473 79016110967943669
474 82979646909566346
475 87137774623619105
476 91499846411953200
477 96075654433306331
478 100875451046191407
479 105909969791435072
480 111190447603624517
481 116728647736536160
482 122536884021629033
483 128628045921554128
484 135015625028521628
485 141713742445414133
486 148737177730776295
487 156101398820361520
488 163822593639619381
489 171917702793009056
490 180404454079607171
491 189301398193856066
492 198627946397372262
493 208404409492933608
494 218652038925690546
495 229393069313581851
496 240650763273342746
497 252449457814662416
498 264814613211738834
499 277772863594475296
500 291352070214281123
501 305581376594684247
502 320491266569914199
503 336113624389449389
504 352481797942001968
505 369630664244335235
506 387596698302797835
507 406418044459518398
508 426134591389327793
509 446788049826334235
510 468422034247014378
511 491082147554843120
512 514816070057544038
513 539673651745358573
514 565707009227769558
515 592970626298744518
516 621521459555326355
517 651419047998819897
518 682725628113869295
519 715506253310829499
520 749828919300273796
521 785764694240418061
522 823387855302721687
523 862776030450839979
524 904010347159883817
525 947175586823811051
526 992360346664519716
527 1039657207843338084
528 1089162911679200468
529 1140978542626362391
530 1195209720012842881
531 1251966797142711382
532 1311365069865718489
533 1373524993167642955
534 1438572407991802343
535 1506638776794701244
536 1577861430160785655
537 1652383822927866432
538 1730355802270619577
539 1811933886144644905
540 1897281554668848027
541 1986569552801222125
542 2079976207026581057
543 2177687754363571117
544 2279898686558499282
545 2386812107725801086
546 2498640108456909414
547 2615604154607073896
548 2737935493942731309
549 2865875578803499733
550 2999676508127576472
551 3139601486936866909
552 3285925306801736207
553 3438934845321447627
554 3598929588320759484
555 3766222172735932847
556 3941138954081108231
557 4124020596407154024
558 4315222688844269172
559 4515116386580495538
560 4724089080581759690
561 4942545093845586759
562 5170906408721746341
563 5409613423035347856
564 5659125739785286094
565 5919922988098725014
566 6192505680470074608
567 6477396103910507579
568 6775139250307422099
569 7086303783570019817
570 7411483049147062986
571 7751296123448736256
572 8106388909068122174
573 8477435273296435605
574 8865138236161258184
575 9270231205456159846
576 9693479265347685133
577 10135680516011461171
578 10597667471265204222
579 11080308511637060600
580 11584509400238618677
581 12111214858870892872
582 12661410212148592173
583 13236123097059678151
584 13836425246179429748
585 14463434341940918273
586 15118315950632994810
587 15802285533515497491
588 16516610544193817675
589 17262612609634799155
590 18041669804465436524
591 18855219015934227405
592 19704758409706613903
593 20591849993885679191
594 21518122291991006970
595 22485273122311977532
596 23495072494969058680
597 24549365624136847441
598 25650076067402236017
599 26799208989767479887
600 27998854564949452165
601 29251191511558220511
602 30558490777530207415
603 31923119370489359653
604 33347544348184215355
605 34834336966792404655
606 36386177002066668540
607 38005857241265638098
608 39696288161738479784
609 41460502794296145735
610 43301661788206509493
611 45223058676182326878
612 47228125357237898227
613 49320437796059851432
614 51503721957877943972
615 53781859977786410992
616 56158896584673040647
617 58639045779038533740
618 61226697786087153327
619 63926426283723609395
620 66742995928120541895
621 69681370176862311125
622 72746719433675530852
623 75944429515155260238
624 79280110464912321995
625 82759605715993192935
626 86389001628501141456
627 90174637403758536504
628 94123115403539046819
629 98241311876261100424
630 102536388120374493417
631 107015802087450847789
632 111687320457032619884
633 116559031186440525513
634 121639356569540653105
635 126937066808443713453
636 132461294134210849404
637 138221547481396975722
638 144227727754723656267
639 150490143693662586242
640 157019528375595270420
641 163827056364397457122
642 170924361547661833635
643 178323555670612412152
644 186037247612682161003
645 194078563416167881319
646 202461167115919418126
647 211199282381016338448
648 220307715020605263558
649 229801876366562501984
650 239697807588605548066
651 250012204956383551236
652 260762446107836933424
653 271966617340370158190
654 283643541987994696704
655 295812809903135525962
656 308494808110336228433
657 321710752652839394104
658 335482721703575473939
659 349833689963982990371
660 364787564426731096007
661 380369221528398039009
662 396604545772998538944
663 413520469855254218060
664 431145016369635904786
665 449507341137166325528
666 468637778241489325447
667 488567886809566377097
668 509330499634369284575
669 530959773678599556134
670 553491242563074151816
671 576961871082812742266
672 601410111861165289699
673 626875964189372872604
674 653401035169072127152
675 681028603209870863742
676 709803684007184054781
677 739773099057629342520
678 770985546845409345635
679 803491676762647146159
680 837344165905990918999
681 872597798818684332007
682 909309550330029031955
683 947538671568310682929
684 987346779309495976534
685 1028797948745321251480
686 1071958809844272068631
687 1116898647397292217325
688 1163689504933711449027
689 1212406292608114824452
690 1263126899256405312972
691 1315932308731308005646
692 1370906720729114399333
693 1428137676228074026193
694 1487716187764577852960
695 1549736874678384621592
696 1614298103568224515090
697 1681502134100616673687
698 1751455270429370319500
699 1824268018381010458566
700 1900055248680771668344
701 1978936366387744089144
702 2061035486832125950895
703 2146481618237544939358
704 2235408851340980217700
705 2327956556208751559557
706 2424269586582049239728
707 2524498491967219918842
708 2628799737826679358252
709 2737335934103746548671
710 2850276072461246555810
711 2967795772486674311500
712 3090077537269426524704
713 3217311018623950579516
714 3349693292391792470278
715 3487429144119157950339
716 3630731365572473414713
717 3779821062413230660543
718 3934927973526362667028
719 4096290802350273165774
720 4264157560737017995758
721 4438785925719983444438
722 4620443609754533790027
723 4809408744840731608910
724 5005970281133424338253
725 5210428400483207015279
726 5423094945556270564638
727 5644293865013717111603
728 5874361675444012771062
729 6113647940568896431534
730 6362515768465047315230
731 6621342327364311947559
732 6890519380826475660406
733 7170453842892716323987
734 7461568354068658794080
735 7764301878793546723096
736 8079110325302872349717
737 8406467188592703371841
738 8746864217455253527748
739 9100812106349311999693
740 9468841213141448853955
741 9851502303540974424501
742 10249367323335461207839
743 10663030199313548705261
744 11093107670057609173555
745 11540240147561465468647
746 12005092610936793760985
747 12488355533236946366562
748 12990745842748532078499
749 13513007919858512406647
750 14055914630939887603090
751 14620268400448629650838
752 15206902322774200623968
753 15816681315127565439848
754 16450503313115387162788
755 17109300510382580609138
756 17794040644086035313684
757 18505728327687697898101
758 19245406432952561073998
759 20014157522754290105097
760 20813105336706163657048
761 21643416331343899418336
762 22506301277020224325629
763 23403016913371458848736
764 24334867665668756569271
765 25303207424058209590867
766 26309441388166178246801
767 27355027979228575804002
768 28441480822395397139461
769 29570370801534599067898
770 30743328189373169315074
771 31962044855476113517058
772 33228276555099859984503
773 34543845301609319027908
774 35910641825706571488875
775 37330628124361600648651
776 38805840102918299950684
777 40338390313480985987446
778 41930470793294761857916
779 43584356006454601175757
780 45302405892912655494118
781 47087069028364335657169
782 48940885899256216619725
783 50866492296759306619567
784 52866622834242983707309
785 54944114592374827416750
786 57101910896693956775332
787 59343065232084831334946
788 61670745299332963146725
789 64088237218512668810988
790 66598949884745161544090
791 69206419481423351204271
792 71914314156823193717379
793 74726438869569055999019
794 77646740409281246517535
795 80679312598271283992930
796 83828401681050500292954
797 87098411907945262109574
798 90493911320053653993885
799 94019637742296933212462
800 97680504992304478267008
801 101481609312380518161520
802 105428236032832422504136
803 109525866474441203810316
804 113780185098934424147278
805 118197086915813864068551
806 122782685155019834714233
807 127543319214397207023917
808 132485562892109655158955
809 137616232913622642148462
810 142942397764110928751946
811 148471386836611182527585
812 154210799907531619972544
813 160168516950586195776949
814 166352708301570902478495
815 172771845185846484324567
816 179434710621803411925513
817 186350410713023480755771
818 193528386343328646838574
819 200978425288338696985502
820 208710674758703784302818
821 216735654389602259528247
822 225064269692710403762465
823 233707825986269535604049
824 242678042820567728679903
825 251987068915567696853316
826 261647497629183761337415
827 271672382974121751448451
828 282075256203050671924460
829 292870142981283769229148
830 304071581168089602376791
831 315694639227161648695923
832 327754935288810639935781
833 340268656885852563017470
834 353252581387298659497801
835 366724097153365452994594
836 380701225437559750629029
837 395202643061010709732275
838 410247705886567866301978
839 425856473119609626974742
840 442049732464970007315392
841 458849026168828573790148
842 476276677976995087362597
843 494355821040471811847800
844 513110426801892817502049
845 532565334895907802992429
846 552746284099430234625814
847 573679944367156543054488
848 595393949990757333445455
849 617916933919648888516839
850 641278563284395519551726
851 665509576163322919560512
852 690641819636219363694162
853 716708289168555794017780
854 743743169373114147691885
855 771781876195494850772189
856 800861100573602444358712
857 831018853620820939658118
858 862294513386397090139820
859 894728873246197915779656
860 928364191981003830422205
861 963244245599187308859135
862 999414380964821146252768
863 1036921571291995051140626
864 1075814473570523688920541
865 1116143487988016221277385
866 1157960819417903976690142
867 1201320541042868380796652
868 1246278660187972610656346
869 1292893186437711391523114
870 1341224202116302349374928
871 1391333935210526106625579
872 1443286834819792812501060
873 1497149649218177194647151
874 1552991506618811133700064
875 1610883998731176813708491
876 1670901267207782946488157
877 1733120093076960738059429
878 1797619989264766343831686
879 1864483296309342673218218
880 1933795281377673996310277
881 2005644240695158273910063
882 2080121605505354203254924
883 2157322051677890955187362
884 2237343613089833909495295
885 2320287798906584063147298
886 2406259714896089050618495
887 2495368188911094962067296
888 2587725900682284278910311
889 2683449516066276142172458
890 2782659825901018018531962
891 2885481889622420517427728
892 2992045183805097775061167
893 3102483755791603046354979
894 3216936382584039484395640
895 3335546735173671758140269
896 3458463548494158112381072
897 3585840797186002050996207
898 3717837877370346735705320
899 3854619794632466680429461
900 3996357358426393939077288
901 4143227383114619836287151
902 4295412895868486408159627
903 4453103351657680476621866
904 4616494855569541350392044
905 4785790392702011860422364
906 4961200065887022063538673
907 5142941341504560704758988
908 5331239303661349902586782
909 5526326917011879930260347
910 5728445298513963462289905
911 5937843998415216421621110
912 6154781290782060401416254
913 6379524473887528352867264
914 6612350180790174385315980
915 6853544700441548717941508
916 7103404309676598306451473
917 7362235616447025262571769
918 7630355914675467655998304
919 7908093551114592345779050
920 8195788304614013014450015
921 8493791778204771797867929
922 8802467804431001224206348
923 9122192864365860784152340
924 9453356520769844235732232
925 9796361865857740261560186
926 10151625984162727364154773
927 10519580430995038021643219
928 10900671727016097078011409
929 11295361869458821012880779
930 11704128860549581791743048
931 12127467253698007808640412
932 12565888718047034464448803
933 13019922621987231722793483
934 13490116636267175528790586
935 13977037357344250807735302
936 14481270951649591112457592
937 15003423821454549534942394
938 15544123293057073609946117
939 16104018328021182076356833
940 16683780258235469382784316
941 17284103545572598272242504
942 17905706566966315079100250
943 18549332425739847470476847
944 19215749790056070364635352
945 19905753759378530547411181
946 20620166759871012599974751
947 21359839469683511027743497
948 22125651775113254426222235
949 22918513758651193185332789
950 23739366719967463906575970
951 24589184230912805915849063
952 25468973225658467897993166
953 26379775127122422614218982
954 27322667010877879198517244
955 28298762807767308908684547
956 29309214546496137472464639
957 30355213637509566080483560
958 31437992199509852129282707
959 32558824430002918003575671
960 33719028021320133397338894
961 34919965623595039201565856
962 36163046356235056811754244
963 37449727369464705230852753
964 38781515457580629705354516
965 40159968725597968110947135
966 41586698311035092878020824
967 43063370162625938335396062
968 44591706877820608514094223
969 46173489600980303288843818
970 47810559984248318329690850
971 49504822213127622143515392
972 51258245098875732953382013
973 53072864239880013359944503
974 54950784254261499470056051
975 56894181086011670488186437
976 58905304387056625498318631
977 60986479977703569200140119
978 63140112388019919105004107
979 65368687482760185387951623
980 67674775172556833299895549
981 70061032214160848089366742
982 72530205102624741243465740
983 75085133058395202386823457
984 77728751112395911166103758
985 80464093292260749473467585
986 83294295912997611438216515
987 86222600975448324362749509
988 89252359676037181707328221
989 92387036031391852397999901
990 95630210621554862392562520
991 98985584455601441995792519
992 102456982963621852324112011
993 106048360119130652139577323
994 109763802696116050115117558
995 113607534665054032063132010
996 117583921732371506337322542
997 121697476027961927798139564
998 125952860945525822073211957
999 130354896140636026775725707
1000 134908562691606404928183067