-1 1
0 0
1 2
2 1
3 2
4 3
5 4
6 5
7 7
8 8
9 11
10 13
11 16
12 19
13 25
14 28
15 35
16 41
17 50
18 58
19 71
20 81
21 98
22 113
23 134
24 154
25 183
26 208
27 244
28 280
29 326
30 371
31 431
32 489
33 565
34 641
35 735
36 832
37 953
38 1075
39 1225
40 1382
41 1569
42 1764
43 1999
44 2243
45 2533
46 2839
47 3195
48 3575
49 4018
50 4484
51 5026
52 5604
53 6267
54 6975
55 7787
56 8652
57 9639
58 10698
59 11895
60 13181
61 14636
62 16193
63 17948
64 19838
65 21952
66 24229
67 26777
68 29517
69 32573
70 35868
71 39526
72 43472
73 47852
74 52567
75 57787
76 63421
77 69636
78 76342
79 83735
80 91703
81 100472
82 109932
83 120314
84 131516
85 143801
86 157040
87 171537
88 187174
89 204260
90 222680
91 242795
92 264465
93 288099
94 313567
95 341292
96 371163
97 403663
98 438648
99 476669
100 517606
101 562032
102 609847
103 661706
104 717486
105 777924
106 842927
107 913277
108 988917
109 1070729
110 1158635
111 1253637
112 1355704
113 1465902
114 1584247
115 1711945
116 1849014
117 1996807
118 2155409
119 2326275
120 2509570
121 2706933
122 2918541
123 3146241
124 3390319
125 3652761
126 3933972
127 4236187
128 4559867
129 4907518
130 5279750
131 5679288
132 6106921
133 6565706
134 7056533
135 7582827
136 8145718
137 8748931
138 9393851
139 10084657
140 10822924
141 11613329
142 12457776
143 13361383
144 14326436
145 15358656
146 16460637
147 17638775
148 18896155
149 20239787
150 21673292
151 23204519
152 24837570
153 26581205
154 28440216
155 30424233
156 32538842
157 34794788
158 37198375
159 39761599
160 42491757
161 45402056
162 48500897
163 51803018
164 55317900
165 59061961
166 63046080
167 67288363
168 71801268
169 76604964
170 81713457
171 87149223
172 92928240
173 99075308
174 105608598
175 112555723
176 119937103
177 127783453
178 136117933
179 144974475
180 154379308
181 164370169
182 174976452
183 186240117
184 198194378
185 210885585
186 224351197
187 238642726
188 253802097
189 269886512
190 286943153
191 305035249
192 324215846
193 344555129
194 366112344
195 388965382
196 413180740
197 438844480
198 466031134
199 494836163
200 525342696
201 557656563
202 591870785
203 628102300
204 666455125
205 707058828
206 750029223
207 795509836
208 843629992
209 894548203
210 948408720
211 1005387058
212 1065643603
213 1129372584
214 1196752687
215 1267998351
216 1343308530
217 1422920408
218 1507054851
219 1595974128
220 1689923861
221 1789193448
222 1894055827
223 2004830836
224 2121821100
225 2245379929
226 2375843262
227 2513600758
228 2659025131
229 2812546604
230 2974577849
231 3145593759
232 3326051724
233 3516475131
234 3717370622
235 3929315593
236 4152870367
237 4388671677
238 4637339616
239 4899575517
240 5176065293
241 5467581956
242 5774883134
243 6098820599
244 6440231689
245 6800053890
246 7179212166
247 7578738958
248 7999654830
249 8443096410
250 8910190121
251 9402186165
252 9920327312
253 10465989185
254 11040541472
255 11645497375
256 12282366903
257 12952813202
258 13658500240
259 14401256534
260 15182914110
261 16005482676
262 16870979575
263 17781612109
264 18739600880
265 19747370621
266 20807363724
267 21922243070
268 23094695263
269 24327642808
270 25624039805
271 26987094143
272 28420051863
273 29926433068
274 31509804635
275 33174027097
276 34923018611
277 36761013263
278 38692312356
279 40721558484
280 42853473516
281 45093145304
282 47445755651
283 49916880473
284 52512203232
285 55237833043
286 58100003182
287 61105403891
288 64260869370
289 67573725993
290 71051462990
291 74702101369
292 78533847529
293 82555479149
294 86775985716
295 91204972418
296 95852282180
297 100728423009
298 105844171003
299 111211017408
300 116840756640
301 122745954044
302 128939513137
303 135435170458
304 142247041169
305 149390136609
306 156879893056
307 164732713279
308 172965471896
309 181596087729
310 190643005007
311 200125792191
312 210064603868
313 220480807268
314 231396418017
315 242834762079
316 254819884345
317 267377240915
318 280533086167
319 294315197166
320 308752231358
321 323874491405
322 339713252592
323 356301563016
324 373673546587
325 391865240205
326 410913864211
327 430858705929
328 451740356310
329 473601634128
330 496486795455
331 520442500880
332 545516988516
333 571761094242
334 599227387296
335 627971237721
336 658049921564
337 689523737746
338 722455073131
339 756909580347
340 792955201241
341 830663399183
342 870108148838
343 911367225958
344 954521152636
345 999654556775
346 1046855071717
347 1096214758886
348 1147828970082
349 1201797836413
350 1258225081820
351 1317219592304
352 1378894179039
353 1443367220588
354 1510761385189
355 1581205349982
356 1654832469745
357 1731782588004
358 1812200651045
359 1896238603764
360 1984053958894
361 2075811781891
362 2171683201960
363 2271847503019
364 2376490574948
365 2485807102541
366 2599998968539
367 2719277545949
368 2843862037985
369 2973981892161
370 3109875075953
371 3251790604986
372 3399986766421
373 3554733766991
374 3716311888807
375 3885014278033
376 4061145031634
377 4245022118110
378 4436975409048
379 4637349739285
380 4846502866191
381 5064808691944
382 5292655149583
383 5530447579306
384 5778606556115
385 6037571427972
386 6307798067607
387 6589762598161
388 6883959067944
389 7190903354917
390 7511130781306
391 7845200206946
392 8193691564408
393 8557210169207
394 8936384175294
395 9331869094029
396 9744345188402
397 10174522211564
398 10623136720137
399 11090957064313
400 11578780619766
401 12087439021085
402 12617795333185
403 13170749541628
404 13747235642373
405 14348227423736
406 14974735475616
407 15627813255930
408 16308554042018
409 17018097296798
410 17757625540858
411 18528371058262
412 19331612690473
413 20168682874746
414 21040964386310
415 21949897727961
416 22896977797748
417 23883761673478
418 24911865209167
419 25982971209498
420 27098825983824
421 28261247931844
422 29472124032500
423 30733418891053
424 32047171167040
425 33415503078363
426 34840616802048
427 36324804461225
428 37870444475029
429 39480012084170
430 41156075657036
431 42901307752760
432 44718481420681
433 46610481830647
434 48580302543416
435 50631057771966
436 52765978631887
437 54988426034295
438 57301886959807
439 59709988019495
440 62216491729602
441 64825310811926
442 67540504482598
443 70366293497389
444 73307056503517
445 76367345871817
446 79551884091400
447 82865580470687
448 86313527591704
449 89901018889252
450 93633545222260
451 97516813382343
452 101556742762978
453 105759484889859
454 110131420211381
455 114679178667081
456 119409636664976
457 124329938747477
458 129447494740957
459 134770002626133
460 140305445888899
461 146062117618209
462 152048618135232
463 158273880390952
464 164747167862730
465 171478101372649
466 178476657290635
467 185753195807139
468 193318459531442
469 201183603303536
470 209360193184177
471 217860237946743
472 226696188507382
473 235880971141092
474 245427987457195
475 255351149442166
476 265664879984616
477 276384149905196
478 287524479094176
479 299101975589081
480 311133337446561
481 323635893988960
482 336627608426973
483 350127121462188
484 364153754738764
485 378727556878944
486 393869307909016
487 409600567873940
488 425943682267278
489 442921833440127
490 460559047134564
491 478880246788290
492 497911261341018
493 517678882607880
494 538210874408802
495 559536033262024
496 581684198959607
497 604686318707828
498 628574459351160
499 653381875168793
500 679143021818513
501 705893628080592
502 733670711676396
503 762512655121682
504 792459223658340
505 823551645465269
506 855832631806163
507 889346461939434
508 924139005672336
509 960257813171148
510 997752140206581
511 1036673043163772
512 1077073407116384
513 1119008046433963
514 1162533735922297
515 1207709317280613
516 1254595733645768
517 1303256142255365
518 1353755952580864
519 1406162945664932
520 1460547316133836
521 1516981798520254
522 1575541713558936
523 1636305101923952
524 1699352775047305
525 1764768456817898
526 1832638839282833
527 1903053732694058
528 1976106126572599
529 2051892348614517
530 2130512131428789
531 2212068780949301
532 2296669249284788
533 2384424313109202
534 2475448653199991
535 2569861043421844
536 2667784437347394
537 2769346168593271
538 2874678045062513
539 2983916561214680
540 3097203000616179
541 3214683660878999
542 3336509965018815
543 3462838699960780
544 3593832137361717
545 3729658286390853
546 3870491024840160
547 4016510367061987
548 4167902605992275
549 4324860597303813
550 4487583913144784
551 4656279143374154
552 4831160061998368
553 5012447946542540
554 5200371757967359
555 5395168479430723
556 5597083310659104
557 5806370027149911
558 6023291190177218
559 6248118527699894
560 6481133160968172
561 6722626008620417
562 6972898031076546
563 7232260659101852
564 7501036057397435
565 7779557579141808
566 8068170049975481
567 8367230250280055
568 8677107220992744
569 8998182775168861
570 9330851827317805
571 9675522936061040
572 10032618658457970
573 10402576125842957
574 10785847424883888
575 11182900208471016
576 11594218105531166
577 12020301369132554
578 12461667316858244
579 12918851018602932
580 13392405769609686
581 13882903820217558
582 14390936883986782
583 14917116911989777
584 15462076638225618
585 16026470401389350
586 16610974730121768
587 17216289214984385
588 17843137136444396
589 18492266390151981
590 19164450160345819
591 19860487901922576
592 20581206062330273
593 21327459123711100
594 22100130376757815
595 22900133026634808
596 23728411022058783
597 24585940229139051
598 25473729319383026
599 26392821015407408
600 27344293042022032
601 28329259448235043
602 29348871625374504
603 30404319710312538
604 31496833675075135
605 32627684816028361
606 33798186919949431
607 35009697844461383
608 36263620765354645
609 37561405854118524
610 38904551611868201
611 40294606649671514
612 41733171115021904
613 43221898581267233
614 44762497572420780
615 46356733568646411
616 48006430635835896
617 49713473553977370
618 51479809558603531
619 53307450599574716
620 55198475201379349
621 57155030860592103
622 59179336032744185
623 61273682676639972
624 63440438376279202
625 65682049041009146
626 68001041170913197
627 70400024722619207
628 72881695527401365
629 75448838332433433
630 78104329381735692
631 80851139643581773
632 83692337564403922
633 86631092494017532
634 89670677623565203
635 92814473620268358
636 96065971761496321
637 99428777791798826
638 102906615265252430
639 106503329638637499
640 110222891835314023
641 114069402588527549
642 118047096241234475
643 122160345354733609
644 126413664759011952
645 130811716443161992
646 135359313872098477
647 140061427175459953
648 144923187747880924
649 149949893754462625
650 155147015032062150
651 160520198930886550
652 166075275535725505
653 171818263863580517
654 177755377425321775
655 183893030800876012
656 190237845562198152
657 196796657249224647
658 203576521676756424
659 210584722334917445
660 217828777104328831
661 225316446106663100
662 233055738853087427
663 241054922572463678
664 249322529820002844
665 257867367311376956
666 266698524020606546
667 275825380550507244
668 285257617749631904
669 295005226651731820
670 305078517643865267
671 315488131008522685
672 326245046677411764
673 337360595412381244
674 348846469180467862
675 360714733012385049
676 372977836037062497
677 385648624057710312
678 398740351286881878
679 412266693683026742
680 426241761428482356
681 440680113072469753
682 455596768797510205
683 471007225416425049
684 486927470475915478
685 503373998158483901
686 520363824273684188
687 537914503119433272
688 556044143415019432
689 574771426178285136
690 594115621658269389
691 614096608288665194
692 634734890680180961
693 656051619714790740
694 678068611662088529
695 700808369481378599
696 724294103130693852
697 748549752148323090
698 773600007225934256
699 799470334145947616
700 826186996695068848
701 853777082037030246
702 882268525047982842
703 911690135209447623
704 942071622450422254
705 973443625650972671
706 1005837740081603477
707 1039286547611766181
708 1073823645843024937
709 1109483680122944729
710 1146302374472782584
711 1184316565513757370
712 1223564235296623250
713 1264084547252000965
714 1305917881036195896
715 1349105870624508766
716 1393691441292765191
717 1439718849980133372
718 1487233724533590247
719 1536283106472484722
720 1586915492631325840
721 1639180880466760316
722 1693130812240287746
723 1748818423017226386
724 1806298487540007036
725 1865627471075589776
726 1926863579139544418
727 1990066811358249037
728 2055299014211464308
729 2122623938086026202
730 2192107293215214305
731 2263816810108982541
732 2337822298879568725
733 2414195713244812640
734 2493011213438515985
735 2574345233995547817
736 2658276550457826357
737 2744886351159901783
738 2834258307954484794
739 2926478652230669678
740 3021636249893793285
741 3119822681862637794
742 3221132323552882536
743 3325662430111622437
744 3433513220668917512
745 3544787968583683921
746 3659593090740876979
747 3778038243099408147
748 3900236415329403853
749 4026304031967118552
750 4156361052704559853
751 4290531079474773470
752 4428941462721667161
753 4571723414758417302
754 4719012122365125912
755 4870946866780198221
756 5027671142994315368
757 5189332786756123282
758 5356084100949555920
759 5528081990017856557
760 5705488093834416958
761 5888468929969475734
762 6077196035489048464
763 6271846117513802252
764 6472601203402696409
765 6679648800080017132
766 6893182053087430615
767 7113399915179333587
768 7340507314755537679
769 7574715334254474577
770 7816241388504933104
771 8065309413477651902
772 8322150055126173199
773 8587000869085989316
774 8860106520607958228
775 9141718995828549667
776 9432097813430299338
777 9731510248142900980
778 10040231554802207795
779 10358545204775855157
780 10686743123131316062
781 11025125938719896784
782 11374003235201113729
783 11733693815561250537
784 12104525967784593028
785 12486837744622827005
786 12880977244749295535
787 13287302908642486787
788 13706183816102892498
789 14137999999163295547
790 14583142756898422217
791 15042014986322114217
792 15515031515473267472
793 16002619453314828376
794 16505218542130796653
795 17023281527499814399
796 17557274531097135199
797 18107677441871408525
798 18674984310407842872
799 19259703762500922938
800 19862359416295419180
801 20483490319515300967
802 21123651390668371255
803 21783413881257448964
804 22463365842407197717
805 23164112613458529636
806 23886277315447396206
807 24630501367562278426
808 25397445008985427174
809 26187787844770711805
810 27002229397642862849
811 27841489684940444140
812 28706309802052372280
813 29597452532162888205
814 30515702963098949803
815 31461869131705117289
816 32436782675974719889
817 33441299515984684558
818 34476300543281814409
819 35542692340415175181
820 36641407909658913858
821 37773407433286700659
822 38939679043828498975
823 40141239627350801816
824 41379135637560310202
825 42654443944479225274
826 43968272694837348396
827 45321762208657160188
828 46716085888511183434
829 48152451166670689700
830 49632100465940764604
831 51156312200172994143
832 52726401789540647302
833 54343722717362760108
834 56009667602839805848
835 57725669317298927280
836 59493202117569370779
837 61313782824929472481
838 63188972022476140464
839 65120375300226554340
840 67109644520020177488
841 69158479130417403614
842 71268627502858757750
843 73441888320202010823
844 75680111988067282380
845 77985202101055866280
846 80359116933424789406
847 82803870987251315734
848 85321536566798372777
849 87914245413120973749
850 90584190366721865222
851 93333627093332151621
852 96164875839706905120
853 99080323255569478153
854 102082424247651682940
855 105173703903062011721
856 108356759446952250014
857 111634262272845722724
858 115008960009604033982
859 118483678664551189571
860 122061324805711990492
861 125744887823883227004
862 129537442236438323585
863 133442150074819191236
864 137462263316541621201
865 141601126404930425401
866 145862178816308023248
867 150248957719162803958
868 154765100683879550312
869 159414348488907318549
870 164200547980786205322
871 169127655035287502902
872 174199737575897424924
873 179420978698329837679
874 184795679856065604425
875 190328264157077417896
876 196023279725484176077
877 201885403179800463089
878 207919443180239208095
879 214130344098295992717
880 220523189759742973373
881 227103207315870348919
882 233875771192750745184
883 240846407175010602256
884 248020796572496634246
885 255404780528028743917
886 263004364413193245175
887 270825722372125912877
888 278875201958780332682
889 287159328929429821928
890 295684812134403057849
891 304458548572666841662
892 313487628551710805208
893 322779341018268357615
894 332341179000757560563
895 342180845230941915791
896 352306257884084222796
897 362725556507131441078
898 373447108072540146906
899 384479513229379380384
900 395831612687629302222
901 407512493809460941033
902 419531497341682432558
903 431898224365364081962
904 444622543395038273652
905 457714597705780377704
906 471184812818747999389
907 485043904225833312929
908 499302885282142673171
909 513973075349392425965
910 529066108117012307688
911 544593940186552621257
912 560568859844232572949
913 577003496109793881942
914 593910827984496001039
915 611304193989078119197
916 629197301912460063097
917 647604238864748496142
918 666539481553223374453
919 686017906877679290510
920 706054802761649698874
921 726665879318798469610
922 747867280268793140304
923 769675594704941977716
924 792107869125660756480
925 815181619835123233144
926 838914845622860334512
927 863326040830844571897
928 888434208715453471650
929 914258875216127532562
930 940820103035708727067
931 968138506147636098233
932 996235264632521454035
933 1025132139962763596911
934 1054851490635187160923
935 1085416288273952188064
936 1116850134101145251470
937 1149177275900976839953
938 1182422625372362721088
939 1216611775999624421340
940 1251771021333375778459
941 1287927373815257453476
942 1325108584035835724335
943 1363343160563354769192
944 1402660390229847583211
945 1443090359016466185312
946 1484663973421643884228
947 1527412982458249446568
948 1571370000160412154523
949 1616568528750588282352
950 1663042982344551236488
951 1710828711349444070489
952 1759962027429495010464
953 1810480229199243483340
954 1862421628515753108862
955 1915825577534491391515
956 1970732496397163020248
957 2027183901721181154390
958 2085222435755785884401
959 2144891896379653507345
960 2206237267801684437194
961 2269304752145109658333
962 2334141801773214786702
963 2400797152542306597130
964 2469320857836740836033
965 2539764323577291498885
966 2612180344054156001280
967 2686623138781683588400
968 2763148390222527774956
969 2841813282584324186993
970 2922676541532906647762
971 3005798475031364563827
972 3091241015145222059116
973 3179067761029412244734
974 3269344022933524183761
975 3362136867447593014850
976 3457515163821010963751
977 3555549631583633821895
978 3656312889297716874127
979 3759879504676746103406
980 3866326045895783469972
981 3975731134336632358482
982 4088175498588327930660
983 4203742029953727134184
984 4322515839278546090832
985 4444584315361296277080
986 4570037184756238758294
987 4698966573235757966430
988 4831467068719945461038
989 4967635785947997601336
990 5107572432694847839926
991 5251379377816071109724
992 5399161720920040366611
993 5551027363959107075403
994 5707087084534244243184
995 5867454611213936896435
996 6032246700657179091768
997 6201583216850632605032
998 6375587212245157797951
999 6554385011111372915755
1000 6738106294894703203636