-1 1
0 0
1 2
2 2
3 3
4 2
5 5
6 4
7 7
8 6
9 12
10 10
11 17
12 14
13 23
14 24
15 34
16 32
17 47
18 46
19 64
20 64
21 87
22 88
23 117
24 118
25 156
26 160
27 207
28 212
29 271
30 280
31 352
32 366
33 455
34 476
35 587
36 612
37 748
38 788
39 950
40 1004
41 1205
42 1274
43 1515
44 1608
45 1900
46 2020
47 2373
48 2524
49 2951
50 3148
51 3659
52 3902
53 4521
54 4830
55 5563
56 5948
57 6827
58 7306
59 8353
60 8940
61 10189
62 10918
63 12394
64 13282
65 15038
66 16128
67 18199
68 19520
69 21969
70 23574
71 26461
72 28392
73 31794
74 34132
75 38123
76 40920
77 45619
78 48968
79 54474
80 58476
81 64919
82 69688
83 77224
84 82884
85 91685
86 98412
87 108670
88 116616
89 128577
90 137968
91 151869
92 162946
93 179102
94 192130
95 210882
96 226172
97 247916
98 265858
99 291027
100 312012
101 341144
102 365668
103 399323
104 427932
105 466796
106 500126
107 544937
108 583688
109 635327
110 680362
111 739779
112 791998
113 860352
114 920846
115 999352
116 1069342
117 1159454
118 1240344
119 1343681
120 1437000
121 1555409
122 1663016
123 1798542
124 1922416
125 2077462
126 2219944
127 2397111
128 2560802
129 2763130
130 2950992
131 3181858
132 3397212
133 3660418
134 3907108
135 4206937
136 4489166
137 4830514
138 5153144
139 5541406
140 5909856
141 6351186
142 6771604
143 7272875
144 7752126
145 8321098
146 8866990
147 9512302
148 10133504
149 10864983
150 11571346
151 12399839
152 13202372
153 14140175
154 15051248
155 16112078
156 17145494
157 18344738
158 19516156
159 20870906
160 22197628
161 23727235
162 25228822
163 26954645
164 28652898
165 30599013
166 32518336
167 34711497
168 36879102
169 39349231
170 41795724
171 44576095
172 47335300
173 50463224
174 53573210
175 57089977
176 60593020
177 64544857
178 68488170
179 72926406
180 77362444
181 82344283
182 87331728
183 92920651
184 98524492
185 104791284
186 111084080
187 118107141
188 125169440
189 133036074
190 140957468
191 149764491
192 158644336
193 168499225
194 178448216
195 189470043
196 200610594
197 212931744
198 225399932
199 239166685
200 253113344
201 268488111
202 284080438
203 301242899
204 318665992
205 337815138
206 357274348
207 378630201
208 400352334
209 424158672
210 448395178
211 474920904
212 501949648
213 531492560
214 561620896
215 594509681
216 628077058
217 664674921
218 702056840
219 742764435
220 784374990
221 829635025
222 875931892
223 926232136
224 977719956
225 1033598863
226 1090834634
227 1152885501
228 1216483032
229 1285359885
230 1355996462
231 1432419458
232 1510840532
233 1595603471
234 1682630872
235 1776606821
236 1873145184
237 1977295537
238 2084340804
239 2199723099
240 2318370834
241 2446148239
242 2577604336
243 2719055396
244 2864644916
245 3021175576
246 3182356024
247 3355510126
248 3533882754
249 3725356934
250 3922680892
251 4134337690
252 4352544712
253 4586428952
254 4827640604
255 5085995807
256 5352539468
257 5637827834
258 5932258012
259 6247178808
260 6572296926
261 6919810632
262 7278688880
263 7662039732
264 8058045232
265 8480788782
266 8917612584
267 9383643006
268 9865327446
269 10378910705
270 10909884242
271 11475689300
272 12060800194
273 12683938654
274 13328494212
275 14014558728
276 14724365808
277 15479474717
278 16260887690
279 17091731483
280 17951698152
281 18865593214
282 19811711836
283 20816653543
284 21857228870
285 22961955833
286 24106063832
287 25320121913
288 26577677492
289 27911492858
290 29293326908
291 30758283486
292 32276220704
293 33884747001
294 35551697732
295 37317355765
296 39147409116
297 41084997802
298 43093527228
299 45219188531
300 47422962910
301 49754301072
302 52171609530
303 54727817034
304 57378598104
305 60180597102
306 63086586132
307 66157174232
308 69342056652
309 72706073883
310 76195655588
311 79880157743
312 83702546500
313 87736997747
314 91922805014
315 96339282483
316 100921832930
317 105755255086
318 110770824534
319 116059187732
320 121547251308
321 127331898118
322 133335404894
323 139661304114
324 146226970220
325 153143026874
326 160321658616
327 167881044285
328 175727877116
329 183988393897
330 192563473172
331 201587936688
332 210956516332
333 220813182919
334 231046165370
335 241809182386
336 252983587694
337 264733488175
338 276932969556
339 289757200523
340 303072588772
341 317066090057
342 331595996492
343 346861814745
344 362713269784
345 379363234784
346 396652386196
347 414807829631
348 433660689900
349 453453229133
350 474006492092
351 495578870327
352 517980777234
353 541487779707
354 565899071628
355 591508498764
356 618103430528
357 645997166506
358 674964608418
359 705339758028
360 736884378512
361 769954503700
362 804298054536
363 840294500342
364 877677186020
365 916850520992
366 957532495886
367 1000154046696
368 1044417010124
369 1090780539272
370 1138929467548
371 1189352959541
372 1241717962900
373 1296545564098
374 1353483900420
375 1413087997339
376 1474986221380
377 1539769694358
378 1607045996824
379 1677444625352
380 1750551329700
381 1827036407653
382 1906462675752
383 1989543805275
384 2075818535564
385 2166046649641
386 2259741615074
387 2357712218752
388 2459445417914
389 2565802093337
390 2676241386972
391 2791679538576
392 2911546536136
393 3036817449570
394 3166891707004
395 3302806891510
396 3443930413728
397 3591366286230
398 3744448387460
399 3904351298893
400 4070373799804
401 4243765456133
402 4423788306644
403 4611771568700
404 4806938860854
405 5010704012805
406 5222250463390
407 5443081918160
408 5672339822780
409 5911623348878
410 6160030070986
411 6419260540456
412 6688366526968
413 6969156260703
414 7260633690112
415 7564721387634
416 7880373424360
417 8209633793688
418 8551404549796
419 8907858611350
420 9277843823104
421 9663670000393
422 10064128516778
423 10481674517657
424 10915040592596
425 11366836192396
426 11835732724374
427 12324503441035
428 12831756140592
429 13360437959003
430 13909090576940
431 14480845703319
432 15074176345464
433 15692410136411
434 16333948798648
435 17002327897119
436 17695875220228
437 18418347036850
438 19167994479110
439 19948808034339
440 20758959450186
441 21602687778331
442 22478082588720
443 23389646704906
444 24335384708924
445 25320079332920
446 26341647336088
447 27405168439775
448 28508468739124
449 29656943096915
450 30848324068308
451 32088340870019
452 33374629683328
453 34713274464659
454 36101812171844
455 37546703106272
456 39045382193756
457 40604709003015
458 42222013652026
459 43904579244965
460 45649628388584
461 47464893492344
462 49347486986128
463 51305617867640
464 53336285861476
465 55448205491347
466 57638261323420
467 59915704077459
468 62277300857320
469 64732871107794
470 67279062320878
471 69926297101292
472 72671101388174
473 75524537502615
474 78483008059764
475 81558253800260
476 84746552551630
477 88060364515711
478 91495841508840
479 95066206685172
480 98767484973236
481 102613708592674
482 106600775067664
483 110743574507355
484 115037876947164
485 119499482197636
486 124124033138950
487 128928294133754
488 133907781824584
489 139080283282446
490 144441190358192
491 150009374448007
492 155780104725758
493 161773402236012
494 167984416293780
495 174434386756648
496 181118346716688
497 188058828205155
498 195250752550020
499 202718021633131
500 210455450507292
501 218488393241007
502 226811565108060
503 235451859591678
504 244403899872188
505 253696211301003
506 263323333921608
507 273315522842133
508 283667245355728
509 294410590127725
510 305539963551330
511 317089397760049
512 329053251858492
513 341467617919792
514 354326823133586
515 367669142897133
516 381488889881548
517 395826653554822
518 410676751625036
519 426082226070105
520 442037421582966
521 458587979407800
522 475728295665512
523 493506766246953
524 511917866036202
525 531012910209626
526 550786482690952
527 571292992327491
528 592527165684118
529 614546690039176
530 637346471739084
531 660987672114027
532 685465418328634
533 710844553080659
534 737120469473092
535 764361911070120
536 792564586648816
537 821801373180108
538 852068349637692
539 883442772664393
540 915921151261612
541 949585382623485
542 984432471273356
543 1020549231151154
544 1057933233975118
545 1096676503078128
546 1136777255555388
547 1178333033956870
548 1221342786194964
549 1265909902196400
550 1312034153714172
551 1359825125554994
552 1409283514642702
553 1460525468719558
554 1513552720095712
555 1568488369087056
556 1625335303228644
557 1684223988162165
558 1745158596674712
559 1808277396673213
560 1873585987440636
561 1941230901879604
562 2011219318782816
563 2083706525994646
564 2158701447667764
565 2236368645407850
566 2316718968273312
567 2399926800835699
568 2486005111388292
569 2575138689121697
570 2667342831563784
571 2762813348216873
572 2861568092953570
573 2963814547507835
574 3069573367245810
575 3179064396280032
576 3292311356172018
577 3409547184129416
578 3530798953439936
579 3656313467826284
580 3786121460272330
581 3920484419966566
582 4059437071349670
583 4203256455851616
584 4351981646967912
585 4505906155980851
586 4665073790324268
587 4829795502420962
588 5000120247956912
589 5176377448704663
590 5358621654296020
591 5547201844000204
592 5742178640765688
593 5943921733342273
594 6152498333108728
595 6368300057389640
596 6591401259724648
597 6822216776392218
598 7060828697668708
599 7307676444430033
600 7562850482193440
601 7826816261823711
602 8099673309379468
603 8381914635182559
604 8673649561215884
605 8975400276112255
606 9287286686367336
607 9609861871852210
608 9943257169401604
609 10288058362873977
610 10644409125897904
611 11012929864475045
612 11393777560482818
613 11787609271876555
614 12194596329412250
615 12615434590565185
616 13050310849553700
617 13499962035957809
618 13964591600562490
619 14444979949345371
620 14941348466996624
621 15454523579803639
622 15984745972956728
623 16532890784436078
624 17099219462002866
625 17684658702827598
626 18289492280881430
627 18914701464693640
628 19560594026483874
629 20228208993030688
630 20917879921879228
631 21630706969068367
632 22367051387697528
633 23128078029144524
634 23914177882784646
635 24726584267435412
636 25565720088829596
637 26432891123328621
638 27328554521227636
639 28254092736567925
640 29209999650252300
641 30197738857990659
642 31217843624873554
643 32271863409299683
644 33360373693053980
645 34485014790443378
646 35646407422079570
647 36846288038835805
648 38085325824450816
649 39365358951094901
650 40687108504674348
651 42052520284245499
652 43462370945511600
653 44918720159858403
654 46422404062939888
655 47975602802314154
656 49579216162267644
657 51235551749655682
658 52945577440096664
659 54711735683377577
660 56535067180849100
661 58418157032374065
662 60362123809124612
663 62369703515094654
664 64442097964638198
665 66582202793038586
666 68791308780362084
667 71072480419326233
668 73427103549999280
669 75858421276430176
670 78367920986861488
671 80959034707861989
672 83633358282853900
673 86394523561156683
674 89244242192738400
675 92186357371535673
676 95222704377438568
677 98357349928515970
678 101592261258317384
679 104931741482208770
680 108377898643177614
681 111935285860462188
682 115606161405758026
683 119395342783025876
684 123305248510571974
685 127340975676073067
686 131505113697037922
687 135803055307196774
688 140237572149509538
689 144814369578979301
690 149536413504015724
691 154409739839040957
692 159437521555980588
693 164626144084497580
694 169979001060824172
695 175502847459831881
696 181201312034758700
697 187081540470364475
698 193147411992329896
699 199406485357219195
700 205862906575974092
701 212524671104273179
702 219396209065030132
703 226485977575021389
704 233798709271702820
705 241343349304891089
706 249124952367951920
707 257152979503736596
708 265432828210386818
709 273974504855145211
710 282783771768720408
711 291871211731883927
712 301242975291002104
713 310910254480875488
714 320879612881319900
715 331162886468771268
716 341767078195305906
717 352704704617239219
718 363983236007045214
719 375615908197405189
720 387610688434586552
721 399981572696855162
722 412737056662729032
723 425891939617250127
724 439455279041272024
725 453442723108109123
726 467863926493687964
727 482735434393499921
728 498067536213962024
729 513877725001111585
730 530176964693516356
731 546983749858571190
732 564309761168295306
733 582174551382052154
734 600590562645308700
735 619578465743773964
736 639151511723379258
737 659331552570244124
738 680132698499486666
739 701578049393139168
740 723682627912527834
741 746470852247271482
742 769958713962347152
743 794172023886101141
744 819127802310020052
745 844853331167502742
746 871366722858247054
747 898696813247317441
748 926862873988787268
749 955895382307198792
750 985814840236610744
751 1016653458639576262
752 1048433045265718830
753 1081187642011527701
754 1114940442126806020
755 1149727421333928807
756 1185573242872609052
757 1222515924774324229
758 1260581689731556980
759 1299810712568136214
760 1340230870149671942
761 1381884614904814929
762 1424801578148104036
763 1469026617396766264
764 1514591224563728688
765 1561542796774328242
766 1609914798894126952
767 1659757309593205243
768 1711105885602216952
769 1764013436893374311
770 1818517737903393032
771 1874674687907225057
772 1932524412209750416
773 1992125966081764900
774 2053521966590968742
775 2116774800857703909
776 2181929726778145880
777 2249052648833922628
778 2318191623443467668
779 2389416268140548000
780 2462777604674482142
781 2538349170051958806
782 2616185127787137378
783 2696363152087304445
784 2778940734831177964
785 2863999917073890600
786 2951601716390867096
787 3041832782890953680
788 3134757868513675732
789 3230468487864141970
790 3329033347877924028
791 3430549097046273187
792 3535088630566158892
793 3642754014902755333
794 3753622580114903728
795 3867802110214199103
796 3985374630799049400
797 4106453959318640485
798 4231127092444761714
799 4359514214144978867
800 4491707583380970148
801 4627834101832046943
802 4767991598513294900
803 4912314063089235897
804 5060905219855734186
805 5213906536837390419
806 5371427977264445632
807 5533618899068753364
808 5700595867511680416
809 5872516564285241739
810 6049504540289429344
811 6231726258320431593
812 6419312660166147314
813 6612439471816007428
814 6811245454021125368
815 7015916104113611667
816 7226598453963086276
817 7443488307841421866
818 7666741446288942904
819 7896564545017233795
820 8133122637576566202
821 8376633866059491665
822 8627273049612327514
823 8885270423701249818
824 9150811155446421424
825 9424138234432864734
826 9705447769542357024
827 9994996200761831047
828 10292991205644045532
829 10599703408280137203
830 10915352716722553260
831 11240224712262499203
832 11574552232096527632
833 11918636629290080897
834 12272724407635832562
835 12637133550209180663
836 13012125005763762278
837 13398034291587076806
838 13795137622877846870
839 14203789003722947222
840 14624280782701149272
841 15056986454218918260
842 15502215415069584402
843 15960361707106296200
844 16431752740652694606
845 16916804218563504138
846 17415862583201290488
847 17929366371360891212
848 18457682132008281396
849 19001272471318130839
850 19560525178482623008
851 20135928230268901244
852 20727891851945440080
853 21336930761302473725
854 21963478881090816678
855 22608079113387866842
856 23271190408895958290
857 23953385373888721785
858 24655149390236128632
859 25377086368957022615
860 26119709602938274008
861 26883655993343048928
862 27669468304633935856
863 28477818202786919234
864 29309279569407397504
865 30164560703872488599
866 31044268340021543344
867 31949149378022032607
868 32879845233317280092
869 33837143478197140493
870 34821722138352355968
871 35834411638860755480
872 36875928648841819702
873 37947148741838131057
874 39048829373640277800
875 40181893682902801366
876 41347142171211456332
877 42545548086218458487
878 43777957356423831780
879 45045396016181119813
880 46348757930453008644
881 47689124738742076356
882 49067440887209191336
883 50484846586960702342
884 51942339652396522072
885 53441121988332970336
886 54982247714224272880
887 56566983714377652602
888 58196443507757117652
889 59871962416052813272
890 61594716618094522024
891 63366113511812490408
892 65187395370849329862
893 67060045498513629831
894 68985375881924904100
895 70964949758959055817
896 73000152642200803244
897 75092631943610379479
898 77243850716630889464
899 79455545007938015443
900 81729259641241111560
901 84066823991013307044
902 86469869105793966282
903 88940322625283453577
904 91479906514286344308
905 94090651872019604901
906 96774376520161025952
907 99533220481714200179
908 102369102637953508080
909 105284277683716514636
910 108280771038293244352
911 111360958114657510980
912 114526976638515469660
913 117781329100745813898
914 121126271606851326940
915 124564440414812638131
916 128098216404054924306
917 131730376635064507679
918 135463433492611649876
919 139300312238894639028
920 143243663850153327332
921 147296569571799966309
922 151461826430632410344
923 155742679838478250733
924 160142080723946413018
925 164663447270561217517
926 169309892572315743702
927 174085016633175602114
928 178992103409589702668
929 184034944240639529122
930 189217003098030026812
931 194542272660124446962
932 200014406545778281712
933 205637609291045725704
934 211415734297435571588
935 217353209017312921804
936 223454097299713407526
937 229723061139409472470
938 236164386054246560218
939 242782980803580017817
940 249583364380158311660
941 256570705156215902332
942 263749768020112495176
943 271125994462879768095
944 278704408335127113032
945 286490738443304779093
946 294490281345689744802
947 302709068086175522636
948 311152682389412861258
949 319827473220590499026
950 328739326678937750236
951 337894926134822018910
952 347300476057776344932
953 356963011547372741436
954 366889072266587927200
955 377086063250422397760
956 387560877047749623476
957 398321307761570656939
958 409374619432367275910
959 420729015336363234668
960 432392150570766006708
961 444372658711483032994
962 456678606485383667700
963 469319079966712969824
964 482302579143576054212
965 495638665912881611248
966 509336296267492403940
967 523405532433044683064
968 537855810318595907860
969 552697718225149219210
970 567941197116002343168
971 583597388416434838894
972 599676764570249849528
973 616191048542906485818
974 633151272037821188800
975 650569769411391521084
976 668458160826410821844
977 686829423387032495681
978 705695796406968600000
979 725070932675639897109
980 744967722915639680508
981 765400530198162112103
982 786382930557328283214
983 807930033683695224951
984 830056136552369403048
985 852777133638037912307
986 876108080299184252504
987 900065695876824076599
988 924665833458491365412
989 949926079345826870113
990 975863125699107332036
991 1002495469986208950838
992 1029840686881254912252
993 1057918231439338904444
994 1086746606491140404784
995 1116346273424394437190
996 1146736711179957498486
997 1177939438662434831972
998 1209974961301988625754
999 1242865909262992956999
1000 1276633867389737660472