-1 1
0 1
1 2
2 3
3 5
4 6
5 10
6 12
7 18
8 23
9 31
10 39
11 54
12 66
13 86
14 107
15 137
16 168
17 213
18 259
19 323
20 392
21 482
22 580
23 711
24 850
25 1029
26 1228
27 1476
28 1750
29 2093
30 2470
31 2934
32 3453
33 4078
34 4780
35 5625
36 6566
37 7689
38 8952
39 10440
40 12113
41 14080
42 16286
43 18865
44 21764
45 25127
46 28910
47 33289
48 38198
49 43857
50 50215
51 57504
52 65684
53 75044
54 85530
55 97491
56 110893
57 126119
58 143170
59 162509
60 184122
61 208575
62 235904
63 266732
64 301150
65 339913
66 383130
67 431707
68 485832
69 546534
70 614107
71 689782
72 773911
73 867971
74 972470
75 1089094
76 1218532
77 1362804
78 1522752
79 1700774
80 1897986
81 2117155
82 2359730
83 2628999
84 2926714
85 3256784
86 3621446
87 4025220
88 4470916
89 4963898
90 5507561
91 6108250
92 6770174
93 7500721
94 8305084
95 9191988
96 10167662
97 11242411
98 12423857
99 13723998
100 15152094
101 16722298
102 18445676
103 20338879
104 22415278
105 24694286
106 27192006
107 29931259
108 32931168
109 36218543
110 39816302
111 43755679
112 48064036
113 52778015
114 57929988
115 63562878
116 69715176
117 76436883
118 83773672
119 91784035
120 100521774
121 110055254
122 120448098
123 131779838
124 144125532
125 157578013
126 172225393
127 188175893
128 205533171
129 224422970
130 244967034
131 267311765
132 291599556
133 318000714
134 346682054
135 377841116
136 411673002
137 448407196
138 488271192
139 531531321
140 578453036
141 629344762
142 684515884
143 744323850
144 809128308
145 879343220
146 955386858
147 1037737715
148 1126881660
149 1223372062
150 1327772208
151 1440721536
152 1562873100
153 1694964689
154 1837752714
155 1992088572
156 2158846852
157 2339009372
158 2533587320
159 2743711377
160 2970549539
161 3215403964
162 3479621879
163 3764701849
164 4072197428
165 4403831262
166 4761393386
167 5146863711
168 5562302142
169 6009982809
170 6492275462
171 7011789493
172 7571248926
173 8173647144
174 8822112106
175 9520075447
176 10271127504
177 11079198869
178 11948407654
179 12883254466
180 13888458240
181 14969169147
182 16130792358
183 17379216544
184 18720628582
185 20161759145
186 21709683932
187 23372091380
188 25157069970
189 27073395803
190 29130309212
191 31337823748
192 33706487422
193 36247719301
194 38973554612
195 41897006295
196 45031798000
197 48392752870
198 51995508916
199 55856941962
200 59994862923
201 64428472526
202 69178044830
203 74265416250
204 79713649496
205 85547565451
206 91793386816
207 98479310063
208 105635134244
209 113292876658
210 121486380000
211 130251981524
212 139628098308
213 149655947526
214 160379115970
215 171844335662
216 184101030512
217 197202159322
218 211203739274
219 226165753800
220 242151660652
221 259229370464
222 277470731348
223 296952592133
224 317756264035
225 339968666910
226 363681776838
227 388993862501
228 416008910612
229 444837969575
230 475598553634
231 508416092571
232 543423325770
233 580761867660
234 620581582902
235 663042287775
236 708313109004
237 756574321535
238 808016704214
239 862843525972
240 921269890190
241 983524894334
242 1049850966615
243 1120506200955
244 1195763702960
245 1275914116340
246 1361264970160
247 1452143426694
248 1548895636396
249 1651889712537
250 1761515114551
251 1878185869755
252 2002339979038
253 2134442923095
254 2274987099682
255 2424495623210
256 2583521820292
257 2752653349915
258 2932511753140
259 3123756939391
260 3327086804920
261 3543242100323
262 3773006151232
263 4017210141941
264 4276732938724
265 4552506846981
266 4845517557856
267 5156810401178
268 5487490459154
269 5838729361628
270 6211765572664
271 6607911799189
272 7028555481032
273 7475166846857
274 7949299663446
275 8452599999164
276 8986807248080
277 9553763691193
278 10155415837988
279 10793824833411
280 11471168190179
281 12189751121788
282 12952008693448
283 13760518194111
284 14618001767060
285 15527339890034
286 16491574580154
287 17513924086824
288 18597786718229
289 19746756891708
290 20964629665860
291 22255418243604
292 23623359335084
293 25072932252576
294 26608865176284
295 28236156024638
296 29960079740234
297 31786211068542
298 33720433027426
299 35768961776146
300 37938356377358
301 40235545993161
302 42667841099240
303 45242963188828
304 47969057655412
305 50854726245723
306 53909041767890
307 57141583596457
308 60562454425284
309 64182319072214
310 68012423560776
311 72064637540632
312 76351475922672
313 80886145307837
314 85682568472110
315 90755435136696
316 96120229679300
317 101793286663789
318 107791822090808
319 114133994193218
320 120838938628384
321 127926834989074
322 135418946432718
323 143337692456312
324 151706693397962
325 160550850133915
326 169896393992090
327 179770973971738
328 190203712724406
329 201225302019747
330 212868065389332
331 225166062690638
332 238155160139518
333 251873144775906
334 266359802747260
335 281657044624943
336 297808992751286
337 314862118515755
338 332865339733513
339 351870170947776
340 371930831978460
341 393104412499377
342 415450992853444
343 439033824344517
344 463919463610642
345 490177970047060
346 517883055234368
347 547112299128151
348 577947316018760
349 610473991363079
350 644782665988395
351 680968395437038
352 719131154385500
353 759376120647493
354 801813901781800
355 846560846190977
356 893739294188244
357 943477918662271
358 995912003189576
359 1051183815071048
360 1109442913121661
361 1170846556251717
362 1235560043930006
363 1303757163557857
364 1375620567001352
365 1451342260429273
366 1531124020403744
367 1615177930305441
368 1703726839933574
369 1797004952785920
370 1895258333613206
371 1998745551344679
372 2107738239214360
373 2222521798694847
374 2343396017385910
375 2470675839545061
376 2604692047556202
377 2745792105307850
378 2894340909325712
379 3050721711961012
380 3215336948998724
381 3388609249967829
382 3570982349819828
383 3762922194499015
384 3964917944692446
385 4177483185700538
386 4401157032171050
387 4636505451810261
388 4884122481008576
389 5144631672982178
390 5418687434776226
391 5706976611556905
392 6010219956638577
393 6329173864360347
394 6664631986034334
395 7017427125159545
396 7388433013008816
397 7778566381369181
398 8188788912947364
399 8620109507804997
400 9073586425355440
401 9550329762339577
402 10051503804309004
403 10578329734798168
404 11132088216051680
405 11714122350392104
406 12325840511961784
407 12968719583401992
408 13644308061913396
409 14354229596665780
410 15100186394837422
411 15883963086974160
412 16707430461232398
413 17572549686600799
414 18481376405622418
415 19436065348304581
416 20438874816599238
417 21492171724236791
418 22598436509492364
419 23760268639590007
420 24980391991022146
421 26261660860878373
422 27607065857793796
423 29019740465734191
424 30502967492789154
425 32060186237288745
426 33694999545265288
427 35411181633473970
428 37212685811200690
429 39103653018949102
430 41088420275524330
431 43171529996653810
432 45357739233025876
433 47652029839090973
434 50059618573893424
435 52585968195765900
436 55236798504481664
437 58018098444561719
438 60936138173466092
439 63997482263812919
440 67209002890170256
441 70577894227616464
442 74111686858182492
443 77818263472067845
444 81705874602847156
445 85783155747295946
446 90059144548429832
447 94543299459122492
448 99245518502844606
449 104176159617553646
450 109346061134429983
451 114766563950740180
452 120449533879527016
453 126407385812085783
454 132653108105265336
455 139200288908518394
456 146063142768949060
457 153256539313424163
458 160796032267559062
459 168697890698734152
460 176979130662616710
461 185657549231110797
462 194751758997341148
463 204281225132237689
464 214266302999296584
465 224728278503241160
466 235689409087936950
467 247172967663605607
468 259203287283525896
469 271805808961230459
470 285007130347458966
471 298835057774034926
472 313318659280521060
473 328488321250676988
474 344375806166735646
475 361014314235927758
476 378438546283049784
477 396684770796853904
478 415790892407002668
479 435796524817073635
480 456743065348376510
481 478673774266318798
482 501633855915002558
483 525670544984884712
484 550833194806924554
485 577173371156237407
486 604744948320911342
487 633604211086910657
488 663809959249121506
489 695423618475211412
490 728509353983157861
491 763134191040855496
492 799368138593363796
493 837284320218960380
494 876959108555595836
495 918472267600707026
496 961907098858016588
497 1007350595943063977
498 1054893603446359508
499 1104630984887246118
500 1156661795373096396
501 1211089464028638767
502 1268021981621299168
503 1327572098687282827
504 1389857529388103025
505 1455001166656472691
506 1523131303654595892
507 1594381867369931089
508 1668892659159866802
509 1746809608346143822
510 1828285033450674218
511 1913477917465627173
512 2002554191518183753
513 2095687033628627450
514 2193057176685484706
515 2294853232653464431
516 2401272026892294064
517 2512518949937818007
518 2628808320365314926
519 2750363766437917202
520 2877418619896050014
521 3010216329955488966
522 3149010890596176090
523 3294067289595310733
524 3445661972099505008
525 3604083327593766967
526 3769632192768354542
527 3942622379561016604
528 4123381220571425504
529 4312250141569293488
530 4509585252974035626
531 4715757970492671097
532 4931155656468087872
533 5156182292607720790
534 5391259175307743572
535 5636825644753965910
536 5893339838661746278
537 6161279482371789092
538 6441142705804152578
539 6733448899544366990
540 7038739600192041488
541 7357579417834733407
542 7690556995388652444
543 8038286013286325280
544 8401406228856571538
545 8780584564519323136
546 9176516233731795430
547 9589925919487584571
548 10021568993878557396
549 10472232794233172559
550 10942737943906906364
551 11433939733979989837
552 11946729553490879992
553 12482036385244385885
554 13040828354356936414
555 13624114347400061458
556 14232945688831254820
557 14868417893430129100
558 15531672480942357284
559 16223898872554810411
560 16946336354898430178
561 17700276132152470530
562 18487063451433703366
563 19308099823035364621
564 20164845320173233612
565 21058820980850959907
566 21991611295956168480
567 22964866807299019680
568 23980306799152809036
569 25039722108156069059
570 26144978034570979976
571 27298017380970465618
572 28500863600764486892
573 29755624083911804889
574 31064493561638717342
575 32429757658841941495
576 33853796575396397506
577 35339088926451502589
578 36888215722317087297
579 38503864519500422530
580 40188833722873321300
581 41946037072076036732
582 43778508291504775252
583 45689405938622681796
584 47682018429291587710
585 49759769276581245167
586 51926222521104361456
587 54185088391130823171
588 56540229169873295994
589 58995665310096646211
590 61555581772772287752
591 64224334631927390561
592 67006457921743924888
593 69906670770149509691
594 72929884794285772070
595 76081211804307864117
596 79365971790220517932
597 82789701240531756908
598 86358161766760127524
599 90077349085016330998
600 93953502328028248534
601 97993113741409979836
602 102202938736871463446
603 106590006358885635867
604 111161630136856079124
605 115925419382151842129
606 120889290901409176504
607 126061481188480863131
608 131450559065791966012
609 137065438840657957476
610 142915393946712355990
611 149010071139333896870
612 155359505214629679708
613 161974134324391394055
614 168864815856003223276
615 176042842953436517807
616 183519961647774952144
617 191308388677312387971
618 199420829965167096088
619 207870499838589099743
620 216671140957431370380
621 225837045040322372153
622 235383074355598340736
623 245324684070119245168
624 255677945422667534824
625 266459569819908385107
626 277686933821297042008
627 289378105116035358888
628 301551869458233019584
629 314227758668768416882
630 327426079669851043403
631 341167944666490617720
632 355475302440791420240
633 370370970879306618100
634 385878670699399997002
635 402023060501201750604
636 418829773111241407172
637 436325453351072333009
638 454537797197208185040
639 473495592472793869184
640 493228761037717911881
641 513768402625082613925
642 535146840291270511028
643 557397667635463574289
644 580555797756527311698
645 604657514111509714652
646 629740523244536500464
647 655844009559208337553
648 683008692104344727083
649 711276883555566389482
650 740692551363817230832
651 771301381263245466850
652 803150843111055634878
653 836290259262233049716
654 870770875453518424822
655 906645934410647894754
656 943970752155260274992
657 982802797237247856703
658 1023201772871304145266
659 1065229702215871311960
660 1108951016775925058948
661 1154432648180979331882
662 1201744123322772507988
663 1250957663117972190402
664 1302148284883803298438
665 1355393908606690537514
666 1410775467095692317434
667 1468377020316470705670
668 1528285873901888952386
669 1590592702151563256924
670 1655391675521307809478
671 1722780592932342882438
672 1792861018906602579886
673 1865738425876630564392
674 1941522341682367738462
675 2020326502623052659476
676 2102269012083180800338
677 2187472505121631916209
678 2276064319050253738700
679 2368176670413187259013
680 2463946838401293014802
681 2563517355136476771863
682 2667036202869195296916
683 2774657018548845467645
684 2886539305820124893796
685 3002848654931514910142
686 3123756970619708120677
687 3249442708484185637684
688 3380091119927567334318
689 3515894506205670606000
690 3657052481675818401756
691 3803772246818913058887
692 3956268871137905475508
693 4114765586541688786225
694 4279494091332469421470
695 4450694865441177142562
696 4628617497045791003272
697 4813521021254896887490
698 5005674271009651057438
699 5205356240926543447056
700 5412856464254096858042
701 5628475403708408522811
702 5852524856382382723232
703 6085328373538742966482
704 6327221695505231086984
705 6578553202530061153268
706 6839684381841663358212
707 7110990311821701216134
708 7392860163563206779772
709 7685697720776941590588
710 7989921918347941940236
711 8305967400562849561186
712 8634285099342666621510
713 8975342833562570887738
714 9329625929828820611974
715 9697637865859280042674
716 10079900936875853200900
717 10476956946224310566966
718 10889367920671229831564
719 11317716851666761853055
720 11762608463067735314134
721 12224670006687683391099
722 12704552086216655592003
723 13202929510960161848214
724 13720502179992382771712
725 14257995998260912566150
726 14816163825294591311870
727 15395786458145206083947
728 15997673649275442768202
729 16622665161123277449408
730 17271631858120846296114
731 17945476838003614328520
732 18645136603258661103664
733 19371582274660271847183
734 20125820847817865959628
735 20908896494803929121088
736 21721891911869138937838
737 22565929715439337182848
738 23442173887490002213126
739 24351831272627977333668
740 25296153128071267956408
741 26276436729000338923353
742 27294027030574183639554
743 28350318389237335039447
744 29446756344721297977808
745 30584839465529090611524
746 31766121259424814642042
747 32992212151889798285809
748 34264781534194622747676
749 35585559884232370058098
750 36956340961899300460426
751 38378984082363875955748
752 39855416469157339842078
753 41387635690634815746269
754 42977712181898096202138
755 44627791855950330943886
756 46340098806343389998552
757 48116938105323560953712
758 49960698699918341149680
759 51873856410220469805479
760 53858977032507345771220
761 55918719551718388946636
762 58055839466138118652556
763 60273192229091037401238
764 62573736810720868248584
765 64960539384961896566281
766 67436777145016101118214
767 70005742252764704277034
768 72670845925686359991926
769 75435622667052117577358
770 78303734643246418712156
771 81278976214347637237484
772 84365278622114413705344
773 87566714841897846189253
774 90887504602944005960470
775 94332019584018252015365
776 97904788789156607426050
777 101610504110913442042240
778 105454026086275829326042
779 109440389853079549298418
780 113574811312488067919908
781 117862693505865148070479
782 122309633212020896420252
783 126921427773689356736590
784 131704082159665511700242
785 136663816272020968348783
786 141807072505305716253232
787 147140523567752488780287
788 152671080571904128127268
789 158405901405316029607672
790 164352399389303040266910
791 170518252237059067985038
792 176911411319706008601252
793 183540111252319901255721
794 190412879809118860200872
795 197538548180626482157304
796 204926261582666892959904
797 212585490230819892226547
798 220526040690910438079968
799 228758067620028046382990
800 237292085909417863862145
801 246138983244661677341192
802 255310033095311125052114
803 264816908150373059200140
804 274671694212686205157360
805 284886904569633791244289
806 295475494854168155086996
807 306450878414703647271236
808 317826942208854931580986
809 329618063240759707329921
810 341839125558032377977195
811 354505537829346276218337
812 367633251519833097399720
813 381238779686636301150031
814 395339216413027053458732
815 409952256904844173021951
816 425096218268969328656948
817 440790060999114966649654
818 457053411190026930301498
819 473906583506992225269474
820 491370604933238745626472
821 509467239323833360060352
822 528219012790250159490932
823 547649239946041059326757
824 567782051039472066769774
825 588642420005499850853896
826 610256193464757256859284
827 632650120703988737468359
828 655851884667530737604606
829 679890133996476444192243
830 704794516147175108114946
831 730595711628044081274348
832 757325469388536462939720
833 785016643401730232703297
834 813703230476720702628728
835 843420409344928717329577
836 874204581059000924088336
837 906093410751229757611412
838 939125870792829967299880
839 973342285403993685842562
840 1008784376758897917139322
841 1045495312638771659370428
842 1083519755680221338373786
843 1122903914275309683438470
844 1163695595173811794050820
845 1205944257847746729325153
846 1249701070672046393674782
847 1295018968985292542138876
848 1341952715088048141504072
849 1390558960246789909653355
850 1440896308764874164172876
851 1493025384192877420934974
852 1547008897743906451380080
853 1602911718990829211179111
854 1660800948915456827629410
855 1720745995391530447895736
856 1782818651176269459257566
857 1847093174497547823757609
858 1913646372316490538259520
859 1982557686358100444530835
860 2053909281995071567612302
861 2127786140083293698725876
862 2204276151839918701002224
863 2283470216868760503707237
864 2365462344429985715441292
865 2450349758065530704504521
866 2538233003683684085481138
867 2629216061221355513957631
868 2723406459994372966747388
869 2820915397861861699855109
870 2921857864322397956881240
871 3026352767675998659257149
872 3134523066377466788615130
873 3246495904723666878599225
874 3362402753008583399856472
875 3482379552297786012381734
876 3606566863965025676507348
877 3735110024152205564109414
878 3868159303304893778394512
879 4005870070954847404965972
880 4148402965911766416102408
881 4295924072046615525219606
882 4448605099839430514439961
883 4606623573885499332005141
884 4770163026544219325346828
885 4939413197936798859529204
886 5114570242489220203734134
887 5295836942239680368297063
888 5483422927119818472032476
889 5677544902442813721063432
890 5878426883821378778961954
891 6086300439763469364187310
892 6301404942183327911658950
893 6523987825091341730379307
894 6754304851715857877215800
895 6992620390337075461505494
896 7239207699102671141870869
897 7494349220122959736284614
898 7758336883132810911698662
899 8031472419036909932636206
900 8314067683644265464870454
901 8606444991928512311670655
902 8908937463139780098545068
903 9221889377125881495290718
904 9545656542209719602826394
905 9880606675003195984812715
906 10227119792526986075314174
907 10585588617040395768066723
908 10956418993974554189021366
909 11340030323398579165883936
910 11736856005437368833074692
911 12147343900097660158777286
912 12571956801948009515614684
913 13011172930138019955788546
914 13465486434231174001867870
915 13935407916367062677733073
916 14421464970257881426218208
917 14924202737567340703573718
918 15444184482209293027207776
919 15981992183148589146000604
920 16538227146275933447580294
921 17113510635975746348411137
922 17708484526995435850789786
923 18323811977273841077867438
924 18960178122376178428143340
925 19618290792234407343998491
926 20298881250881711878791206
927 21002704959923714290437099
928 21730542366479070241977630
929 22483199716378460854122398
930 23261509893401330671814644
931 24066333285388651247879277
932 24898558678060672772443116
933 25759104177430247270779485
934 26648918161693392626956796
935 27568980263543208522252232
936 28520302383844802481534842
937 29503929737676285595822341
938 30520941933732967166641682
939 31572454088162384415408336
940 32659617973890463481668618
941 33783623206572872132229836
942 34945698468298948088060904
943 36147112770252769960481930
944 37389176755530001375161588
945 38673244043389910819287528
946 40000712616216857906167584
947 41373026250550074552155983
948 42791675993536373022262220
949 44258201686248904713638719
950 45774193535311907772865252
951 47341293734364025788806367
952 48961198136890709382790466
953 50635657982053215400831414
954 52366481675140875496320866
955 54155536624374887060321493
956 56004751135792382178522632
957 57916116368045920845667150
958 59891688348955531886676120
959 61933590055761866117458935
960 64044013561032615967141558
961 66225222246291103621065354
962 68479553085441287370226884
963 70809419000185760220886811
964 73217311289640578461517636
965 75705802136478940575547263
966 78277547191945085594308260
967 80935288242214120246141445
968 83681855958585096380832779
969 86520172734135473128285752
970 89453255609479166988158134
971 92484219290418008247495363
972 95616279260293153841873066
973 98852754989997773923668346
974 102197073248631941954658418
975 105652771517942945635678996
976 109223501513716964706017460
977 112913032817458254995230370
978 116725256621718074115757248
979 120664189592614092374222396
980 124733977853110760988870058
981 128938901090818363632132583
982 133283376794102124135629932
983 137771964620489194147019003
984 142409370901399214360705324
985 147200453287430269465523201
986 152150225538474471724304246
987 157263862463153714485752190
988 162546705012113442823427132
989 168004265529939303265600627
990 173642233170514100374958440
991 179466479480870771331171952
992 185483064158655305088553844
993 191698240988563675175922274
994 198118463963181138563517556
995 204750393593914873875867626
996 211600903417781728817202100
997 218677086706088602067947362
998 225986263381120765404692544
999 233535987147243013429150268
1000 241334052842903797072399313