-1 1
0 1
1 2
2 3
3 4
4 5
5 8
6 10
7 13
8 18
9 22
10 28
11 36
12 45
13 56
14 70
15 85
16 104
17 128
18 154
19 187
20 226
21 270
22 323
23 386
24 457
25 542
26 642
27 755
28 888
29 1042
30 1218
31 1422
32 1658
33 1926
34 2236
35 2591
36 2994
37 3456
38 3984
39 4583
40 5265
41 6042
42 6918
43 7914
44 9042
45 10314
46 11752
47 13376
48 15202
49 17258
50 19574
51 22170
52 25088
53 28362
54 32026
55 36129
56 40722
57 45850
58 51578
59 57976
60 65101
61 73044
62 81891
63 91726
64 102664
65 114822
66 128312
67 143283
68 159890
69 178280
70 198652
71 221204
72 246138
73 273706
74 304170
75 337794
76 374906
77 415846
78 460962
79 510679
80 565432
81 625682
82 691968
83 764860
84 844951
85 932940
86 1029554
87 1135565
88 1251864
89 1379384
90 1519126
91 1672218
92 1839866
93 2023344
94 2224096
95 2443652
96 2683650
97 2945920
98 3232410
99 3545210
100 3886632
101 4259156
102 4665426
103 5108376
104 5591136
105 6117062
106 6689848
107 7313447
108 7992096
109 8730438
110 9533460
111 10406488
112 11355361
113 12386330
114 13506094
115 14721959
116 16041762
117 17473894
118 19027488
119 20712343
120 22538938
121 24518674
122 26663759
123 28987274
124 31503400
125 34227340
126 37175360
127 40365081
128 43815378
129 47546448
130 51580142
131 55939844
132 60650594
133 65739412
134 71235234
135 77169012
136 83574128
137 90486298
138 97943730
139 105987575
140 114661834
141 124013590
142 134093464
143 144955598
144 156657875
145 169262490
146 182835914
147 197449203
148 213178624
149 230105654
150 248317380
151 267907156
152 288974714
153 311626570
154 335976844
155 362147377
156 390268274
157 420478798
158 452927586
159 487773295
160 525185600
161 565345560
162 608446322
163 654694348
164 704309824
165 757527574
166 814598410
167 875789734
168 941386594
169 1011693260
170 1087034016
171 1167754370
172 1254222952
173 1346832434
174 1446001062
175 1552174779
176 1665828466
177 1787467698
178 1917631256
179 2056892650
180 2205862197
181 2365190002
182 2535567750
183 2717731292
184 2912464002
185 3120599082
186 3343022546
187 3580677210
188 3834565452
189 4105752780
190 4395372516
191 4704629068
192 5034802280
193 5387252762
194 5763425994
195 6164857363
196 6593178488
197 7050122086
198 7537527994
199 8057350535
200 8611664330
201 9202671528
202 9832710271
203 10504261818
204 11219958946
205 11982595960
206 12795137096
207 13660726543
208 14582700072
209 15564595084
210 16610162474
211 17723380110
212 18908464938
213 20169886804
214 21512384352
215 22940979273
216 24460992706
217 26078063692
218 27798166152
219 29627628149
220 31573153397
221 33641841470
222 35841210294
223 38179221426
224 40664303770
225 43305380138
226 46111896616
227 49093850673
228 52261822242
229 55627008016
230 59201254622
231 62997094920
232 67027788192
233 71307358974
234 75850639772
235 80673317750
236 85791980536
237 91224166068
238 96988417106
239 103104334976
240 109592637788
241 116475224116
242 123775235790
243 131517126174
244 139726734080
245 148431357526
246 157659833260
247 167442622963
248 177811899440
249 188801639428
250 200447723972
251 212788038978
252 225862583650
253 239713586954
254 254385625286
255 269925748576
256 286383615856
257 303811632362
258 322265096432
259 341802356974
260 362484973178
261 384377885594
262 407549598716
263 432072367244
264 458022394697
265 485480045516
266 514530061580
267 545261793112
268 577769444568
269 612152326386
270 648515123134
271 686968178334
272 727627787186
273 770616507338
274 816063489186
275 864104815384
276 914883861392
277 968551677718
278 1025267383866
279 1085198586013
280 1148521819280
281 1215423004586
282 1286097931934
283 1360752772330
284 1439604606562
285 1522881984752
286 1610825517832
287 1703688489832
288 1801737504786
289 1905253170162
290 2014530805172
291 2129881188122
292 2251631345970
293 2380125372630
294 2515725292560
295 2658811971665
296 2809786062850
297 2969069002598
298 3137104061856
299 3314357437526
300 3501319402010
301 3698505515050
302 3906457882551
303 4125746482382
304 4356970560312
305 4600760081718
306 4857777258986
307 5128718159391
308 5414314377666
309 5715334795074
310 6032587430256
311 6366921364998
312 6719228769329
313 7090447030332
314 7481560968948
315 7893605169192
316 8327666426280
317 8784886296164
318 9266463773730
319 9773658106181
320 10307791723834
321 10870253318026
322 11462501072220
323 12086066029884
324 12742555628960
325 13433657411820
326 14161142892242
327 14926871613038
328 15732795402874
329 16580962814528
330 17473523780386
331 18412734494208
332 19400962502776
333 20440692043836
334 21534529642844
335 22685209950003
336 23895601858770
337 25168714918044
338 26507706021130
339 27915886414799
340 29396729042448
341 30953876205582
342 32591147588574
343 34312548664778
344 36122279466380
345 38024743768758
346 40024558707584
347 42126564813554
348 44335836517956
349 46657693150654
350 49097710416250
351 51661732404976
352 54355884164512
353 57186584817356
354 60160561287470
355 63284862663200
356 66566875184752
357 70014337923106
358 73635359182672
359 77438433616688
360 81432460128120
361 85626760593372
362 90031099398094
363 94655703866600
364 99511285624117
365 104609062886490
366 109960783763202
367 115578750620579
368 121475845500872
369 127665556692088
370 134162006501008
371 140979980227874
372 148134956448162
373 155643138657730
374 163521488287300
375 171787759197999
376 180460533724632
377 189559260275064
378 199104292610146
379 209116930877828
380 219619464416066
381 230635216461692
382 242188590845926
383 254305120701302
384 267011519326530
385 280335733304000
386 294306997899706
387 308955894909136
388 324314413053520
389 340416010966970
390 357295682953760
391 374990027632168
392 393537319519010
393 412977583748150
394 433352674058260
395 454706354112839
396 477084382368572
397 500534600641304
398 525107026449426
399 550853949370917
400 577830031582586
401 606092412679180
402 635700819029780
403 666717677865268
404 699208236209258
405 733240684940604
406 768886288201800
407 806219518290458
408 845318196348856
409 886263639094906
410 929140811755762
411 974038487550716
412 1021049414000360
413 1070270486246890
414 1121802927773522
415 1175752478829940
416 1232229592784194
417 1291349640826286
418 1353233125372160
419 1418005902422084
420 1485799413344783
421 1556750926481052
422 1631003788857621
423 1708707688538266
424 1790018928049520
425 1875100709222220
426 1964123430028234
427 2057264993908429
428 2154711131981186
429 2256655738776294
430 2363301222051312
431 2474858867135736
432 2591549216522610
433 2713602465328078
434 2841258873135264
435 2974769193015750
436 3114395118430842
437 3260409748598456
438 3413098073210594
439 3572757477287489
440 3739698266837538
441 3914244216308554
442 4096733138708392
443 4287517479163210
444 4486964933002632
445 4695459089363402
446 4913400101179864
447 5141205382777611
448 5379310336178560
449 5628169107106672
450 5888255372046724
451 6160063157597112
452 6444107693243506
453 6740926299051974
454 7051079309679854
455 7375151035974444
456 7713750765833464
457 8067513805889018
458 8437102565457360
459 8823207684614639
460 9226549208149528
461 9647877807025536
462 10087976049419042
463 10547659723301312
464 11027779212401210
465 11529220927856412
466 12052908797750760
467 12599805816616619
468 13170915657466978
469 13767284348821344
470 14390002019068542
471 15040204711020142
472 15719076269418328
473 16427850304030322
474 17167812231515988
475 17940301399153332
476 18746713293392402
477 19588501836780116
478 20467181776712656
479 21384331169353348
480 22341593962662433
481 23340682682407774
482 24383381224902438
483 25471547760873102
484 26607117754776432
485 27792107103780382
486 29028615401307608
487 30318829329974331
488 31665026188652786
489 33069577559115620
490 34534953117663130
491 36063724597035278
492 37658569904694354
493 39322277403503860
494 41057750360758676
495 42868011572335019
496 44756208168699288
497 46725616609442122
498 48779647873881970
499 50921852855259367
500 53155927965990352
501 55485720962383240
502 57915236997208452
503 60448644908492546
504 63090283753883986
505 65844669599964676
506 68716502575865770
507 71710674201603663
508 74832275001588586
509 78086602413778732
510 81479169006074318
511 85015711011608166
512 88702197194650010
513 92544838060020204
514 96550095419024256
515 100724692324991973
516 105075623392784546
517 109610165516767092
518 114335889001871236
519 119260669123726737
520 124392698134023272
521 129740497727437544
522 135312931987897024
523 141119220832201584
524 147168953969224794
525 153472105394478712
526 160039048440108322
527 166880571400658982
528 174007893756615232
529 181432683018066912
530 189167072211193542
531 197223678032029320
532 205615619692412720
533 214356538483410100
534 223460618083429754
535 232942605638738333
536 242817833644581548
537 253102242657158488
538 263812404867302656
539 274965548567289441
540 286579583544398200
541 298673127435565210
542 311265533078117496
543 324376916893977434
544 338028188345522081
545 352241080502076018
546 367038181758575138
547 382442968748882248
548 398479840497137234
549 415174153853299844
550 432552260260120404
551 450641543899814558
552 469470461271728724
553 489068582253493332
554 509466632699390206
555 530696538632881630
556 552791472091662736
557 575785898684980776
558 599715626926471562
559 624617859407355795
560 650531245876427536
561 677495938297065098
562 705553647953287875
563 734747704678721808
564 765123118286416370
565 796726642279524472
566 829606839924913216
567 863814152776225891
568 899400971735228600
569 936421710742627206
570 974932883194360284
571 1014993181181981660
572 1056663557658425986
573 1100007311635652604
574 1145090176523639148
575 1191980411723184015
576 1240748897590662418
577 1291469233896196878
578 1344217841900099316
579 1399074070178600850
580 1456120304333621528
581 1515442080725158898
582 1577128204371552494
583 1641270871167106020
584 1707965794570809880
585 1777312336927214218
586 1849413645585198872
587 1924376793985202703
588 2002312927893402456
589 2083337416966610800
590 2167570011837049834
591 2255135006914788788
592 2346161409111559664
593 2440783112695659754
594 2539139080497101692
595 2641373531688747134
596 2747636136375905234
597 2858082217237148614
598 2972872958466471448
599 3092175622274423715
600 3216163773217076114
601 3345017510629895256
602 3478923709451966362
603 3618076269738287604
604 3762676375166979168
605 3912932760857616608
606 4069061990830272882
607 4231288745445048109
608 4399846119172264082
609 4574975929058142318
610 4756929034262112992
611 4945965667053472004
612 5142355775671133525
613 5346379379462779588
614 5558326936732628246
615 5778499725744519083
616 6007210239341013514
617 6244782593653524022
618 6491552951397643186
619 6747869960263358691
620 7014095206925758468
621 7290603687222798372
622 7577784293063895564
623 7876040316650827798
624 8185789972615315834
625 8507466938696789414
626 8841520915603442952
627 9188418206724802596
628 9548642318385185096
629 9922694581349201254
630 10311094794317947044
631 10714381890177962922
632 11133114625789203976
633 11567872296128327368
634 12019255473629618208
635 12487886773592583357
636 12974411646558235304
637 13479499198584836066
638 14003843040383490082
639 14548162166310094308
640 15113201864241980416
641 15699734657400373774
642 16308561279219347278
643 16940511682397201980
644 17596446083302421802
645 18277256042949768282
646 18983865585800998664
647 19717232357684796766
648 20478348824178055170
649 21268243510833697126
650 22087982286684543530
651 22938669692504855608
652 23821450315358780362
653 24737510211013842154
654 25688078375854845728
655 26674428269986053752
656 27697879393263602396
657 28759798916062807044
658 29861603366643024928
659 31004760377032440667
660 32190790489423908658
661 33421269025137026188
662 34697828018267472650
663 36022158216220131410
664 37396011149393097536
665 38821201272352427344
666 40299608178920202392
667 41833178893676404421
668 43423930242455297456
669 45073951304507782294
670 46785405949087095946
671 48560535459303662190
672 50401661246194503066
673 52311187656047258672
674 54291604874116435248
675 56345491927978676485
676 58475519793878226528
677 60684454609521223042
678 62975160996897273496
679 65350605498821719134
680 67813860133010425962
681 70368106067630378132
682 73016637422395922520
683 75762865199411042406
684 78610321348102127215
685 81562662968725173332
686 84623676659075013546
687 87797283009182295442
688 91087541248937406098
689 94498654053738756654
690 98034972513436253378
691 101701001270009696064
692 105501403829596036074
693 109441008054669554468
694 113524811842364979924
695 117757988995125155869
696 122145895290063481664
697 126694074753635849102
698 131408266148427645152
699 136294409679090129980
700 141358653924685445280
701 146607363004931431128
702 152047123988088227642
703 157684754548476074150
704 163527310881868654922
705 169582095887281465018
706 175856667623946601042
707 182358848052545746837
708 189096732070074727884
709 196078696848011957838
710 203313411483771240070
711 210809846975750067040
712 218577286532613135352
713 226625336227789328830
714 234963936010523073490
715 243603371085181861042
716 252554283670893785970
717 261827685153986415826
718 271434968646094824256
719 281387921961215237796
720 291698741025416484240
721 302380043733356910016
722 313444884266203140473
723 324906767886024761056
724 336779666222217055344
725 349078033065996741790
726 361816820689539105530
727 375011496706849843124
728 388678061494005855776
729 402833066186972946980
730 417493631275784507804
731 432677465814458967638
732 448402887266662531450
733 464688842007755869510
734 481554926504515056708
735 499021409194505843193
736 517109253087784045784
737 535840139114309697604
738 555236490241217308768
739 575321496384845516335
740 596119140143213608538
741 617654223375459190298
742 639952394655585775952
743 663040177628729302244
744 686945000299058046042
745 711695225279335704796
746 737320181033120556866
747 763850194141565465224
748 791316622627786904168
749 819751890372805333870
750 849189522658145401120
751 879664182871284397456
752 911211710411271104232
753 943869159833026374752
754 977674841270042531436
755 1012668362176441052514
756 1048890670430650209860
757 1086384098844285490712
758 1125192411121177190188
759 1165360849312915050856
760 1206936182818727427763
761 1249966758979004244242
762 1294502555313333302314
763 1340595233455505464328
764 1388298194839578256704
765 1437666638192795346052
766 1488757618892896294744
767 1541630110249140853046
768 1596345066768241000988
769 1652965489468296232276
770 1711556493305787589036
771 1772185376782731023218
772 1834921693803173650920
773 1899837327850362392784
774 1967006568558152180710
775 2036506190752501161113
776 2108415536041249723698
777 2182816597032828022312
778 2259794104267032758754
779 2339435615943585491030
780 2421831610536862329992
781 2507075582387916737148
782 2595264140367731287430
783 2686497109708562931904
784 2780877637103235500064
785 2878512299175312687272
786 2979511214426287340578
787 3083988158769193501496
788 3192060684761416698808
789 3303850244652979921470
790 3419482317370160524944
791 3539086539557978673860
792 3662796840808926728042
793 3790751583209222141410
794 3923093705337897404228
795 4059970870858225929201
796 4201535621845262424208
797 4347945536997684249192
798 4499363394886695187066
799 4655957342399432500308
800 4817901068539137869834
801 4985373983749352811752
802 5158561404934515021724
803 5337654746354601389832
804 5522851716576927086058
805 5714356521673802586530
806 5912380074860510087858
807 6117140212774030722385
808 6328861918599066210072
809 6547777552254193479970
810 6774127087857512926198
811 7008158358697830427302
812 7250127309944292224634
813 7500298259334516119402
814 7758944166088560994478
815 8026346908303592481467
816 8302797569091884229856
817 8588596731732767691974
818 8884054784117354198674
819 9189492232773351238695
820 9505240026766004671232
821 9831639891780167369848
822 10169044674697774269044
823 10517818698994516760300
824 10878338131289304394404
825 11250991359390233592462
826 11636179382191171396304
827 12034316211783758619393
828 12445829288160697246674
829 12871159906897529970020
830 13310763660211798439680
831 13765110891810539839528
832 14234687165949465165778
833 14719993751139911988014
834 15221548118952841367918
835 15739884458382666378441
836 16275554206247616494368
837 16829126594117721556428
838 17401189212276253084152
839 17992348591235649408500
840 18603230801344641169779
841 19234482071039394831708
842 19886769424308066455366
843 20560781337955276181140
844 21257228419270582347456
845 21976844104723119120296
846 22720385380323235035498
847 23488633524311137414549
848 24282394872852277419970
849 25102501609439578607616
850 25949812578723520927668
851 26825214125512613743026
852 27729620959709005113008
853 28663977047966780306404
854 29629256532883975897526
855 30626464680563558881336
856 31656638857403491900872
857 32720849537001603951130
858 33820201338087397478476
859 34955834094420043562701
860 36128923957619729097002
861 37340684533928313916610
862 38592368055924825293980
863 39885266590251748812690
864 41220713282439461905808
865 42600083639948391938960
866 44024796854581654260890
867 45496317165455136142413
868 47016155263747129587018
869 48585869740485774417644
870 50207068578669855827662
871 51881410691056795621180
872 53610607504991083217018
873 55396424595687018388430
874 57240683369421369634848
875 59145262798134493268898
876 61112101206982722356578
877 63143198116430305572556
878 65240616140515963278656
879 67406482942977349839194
880 69642993252966250318152
881 71952410942138310886500
882 74337071164953629222486
883 76799382564078495977740
884 79341829542834100373564
885 81966974606695223286498
886 84677460775900719095994
887 87476014071298059874972
888 90365446075606518648386
889 93348656572347581457504
890 96428636264757033433348
891 99608469577061005651878
892 102891337540567975359456
893 106280520767100421013830
894 109779402512363697600326
895 113391471831925592749825
896 117120326832558097882664
897 120969678021773339497252
898 124943351758468240275440
899 129045293807677472258991
900 133279573002521792591482
901 137650385016528791942852
902 142162056249595599233759
903 146819047830958350910286
904 151625959742631123157800
905 156587535066877713929716
906 161708664361383333680242
907 166994390165899795205457
908 172449911644247365043152
909 178080589365669247791666
910 183891950229650596170876
911 189889692538433165154724
912 196079691221579465341418
913 202468003217066394644324
914 209060873013518041977456
915 215864738358320879041142
916 222886236136501765248304
917 230132208425390299891712
918 237609708730232295575008
919 245326008406070396976516
920 253288603271361356015952
921 261505220418957441816524
922 269983825230241792815786
923 278732628598374449896040
924 287760094366777599345725
925 297074946989165088669602
926 306686179417602810077620
927 316603061225273348212549
928 326835146970810248193592
929 337392284811264647096588
930 348284625370970113760182
931 359522630873780250801402
932 371117084546368215122826
933 383079100300498112159822
934 395420132702405113622776
935 408151987237654440273117
936 421286830880089363395858
937 434837202973725014171122
938 448816026436698370987402
939 463236619296645661894295
940 478112706567146483727584
941 493458432475149542273252
942 509288373049578420572156
943 525617549081607104805374
944 542461439467394500153842
945 559835994944375238022044
946 577757652232520637744632
947 596243348592309126028525
948 615310536811480143359408
949 634977200632989516732232
950 655261870636937861400754
951 676183640589607224168800
952 697762184273114847205112
953 720017772809577048597250
954 742971292494071246081668
955 766644263151090054690980
956 791058857029598631741842
957 816237918252235513092596
958 842204982834638060374432
959 868984299291326812818377
960 896600849845049031256964
961 925080372256960529120300
962 954449382295517030631568
963 984735196862452336609972
964 1015965957794740522914360
965 1048170656361973807295186
966 1081379158479137187823234
967 1115622230655325512028970
968 1150931566699528877432748
969 1187339815205208822226712
970 1224880607836000692582316
971 1263588588435507507955942
972 1303499442984798260742850
973 1344649930431888958378756
974 1387077914418168526957794
975 1430822395927434660915790
976 1475923546883926929800592
977 1522422744726486667018146
978 1570362607986736132028776
979 1619787032899953291765946
980 1670741231078124086422156
981 1723271768275482045484260
982 1777426604277695770011040
983 1833255133946738928701830
984 1890808229454375897907840
985 1950138283738119216576112
986 2011299255214463513166138
987 2074346713785175424313833
988 2139337888173420509833192
989 2206331714627537226155502
990 2275388887031325644510924
991 2346571908460805081415180
992 2419945144228511164769386
993 2495574876457550150371370
994 2573529360228806872106932
995 2653878881345913640807864
996 2736695815763831839474642
997 2822054690728176288317774
998 2910032247673725837306434
999 3000707506931913301716765
1000 3094161834298474239491992