-1 1
0 0
1 1
2 1
3 1
4 2
5 2
6 3
7 3
8 3
9 4
10 6
11 7
12 8
13 9
14 10
15 12
16 14
17 17
18 19
19 21
20 24
21 29
22 33
23 38
24 43
25 48
26 54
27 61
28 70
29 79
30 88
31 98
32 111
33 124
34 140
35 157
36 174
37 193
38 214
39 239
40 266
41 295
42 326
43 361
44 398
45 441
46 488
47 538
48 592
49 650
50 715
51 786
52 864
53 948
54 1041
55 1138
56 1246
57 1364
58 1492
59 1632
60 1780
61 1942
62 2116
63 2306
64 2514
65 2740
66 2979
67 3238
68 3518
69 3822
70 4152
71 4506
72 4887
73 5294
74 5734
75 6211
76 6730
77 7281
78 7874
79 8509
80 9192
81 9931
82 10724
83 11577
84 12486
85 13459
86 14506
87 15636
88 16843
89 18138
90 19520
91 20996
92 22580
93 24278
94 26100
95 28043
96 30115
97 32329
98 34701
99 37234
100 39946
101 42837
102 45916
103 49200
104 52706
105 56454
106 60450
107 64706
108 69236
109 74066
110 79206
111 84692
112 90534
113 96746
114 103354
115 110378
116 117858
117 125816
118 134280
119 143276
120 152834
121 162977
122 173762
123 185223
124 197396
125 210318
126 224022
127 238565
128 253995
129 270374
130 287752
131 306183
132 325700
133 346390
134 368320
135 391566
136 416204
137 442290
138 469910
139 499143
140 530096
141 562875
142 597580
143 634281
144 673102
145 714154
146 757574
147 803505
148 852068
149 903401
150 957631
151 1014927
152 1075474
153 1139463
154 1207042
155 1278410
156 1353744
157 1433264
158 1517218
159 1605840
160 1699378
161 1798052
162 1902127
163 2011898
164 2127694
165 2249805
166 2378576
167 2514312
168 2657358
169 2808114
170 2966984
171 3134411
172 3310798
173 3496581
174 3692232
175 3898269
176 4115210
177 4343649
178 4584130
179 4837230
180 5103572
181 5383821
182 5678712
183 5988965
184 6315336
185 6658590
186 7019558
187 7399081
188 7798144
189 8217698
190 8658724
191 9122248
192 9609324
193 10121134
194 10658886
195 11223861
196 11817358
197 12440719
198 13095307
199 13782682
200 14504425
201 15262196
202 16057700
203 16892662
204 17768950
205 18688507
206 19653432
207 20665890
208 21728104
209 22842297
210 24010924
211 25236519
212 26521788
213 27869547
214 29282644
215 30764072
216 32316919
217 33944518
218 35650374
219 37438130
220 39311440
221 41274210
222 43330456
223 45484464
224 47740766
225 50104009
226 52579030
227 55170768
228 57884462
229 60725652
230 63700156
231 66813917
232 70073196
233 73484375
234 77054190
235 80789758
236 84698500
237 88788167
238 93066676
239 97542304
240 102223704
241 107120006
242 112240653
243 117595609
244 123195044
245 129049538
246 135170200
247 141568630
248 148257044
249 155248023
250 162554636
251 170190442
252 178169614
253 186506909
254 195217930
255 204318729
256 213825958
257 223756916
258 234129610
259 244962980
260 256276700
261 268091274
262 280427900
263 293308595
264 306756187
265 320794777
266 335449352
267 350745900
268 366711356
269 383373586
270 400761742
271 418906171
272 437838614
273 457591999
274 478200438
275 499699158
276 522125108
277 545516693
278 569913990
279 595358636
280 621893648
281 649563767
282 678415448
283 708497263
284 739859792
285 772555524
286 806638646
287 842165640
288 879195087
289 917788139
290 958008472
291 999922058
292 1043597344
293 1089105171
294 1136519367
295 1185916812
296 1237377514
297 1290984250
298 1346823072
299 1404983007
300 1465556688
301 1528640615
302 1594334994
303 1662743892
304 1733974938
305 1808139868
306 1885354808
307 1965740585
308 2049422542
309 2136530999
310 2227200680
311 2321571374
312 2419788342
313 2522002512
314 2628370806
315 2739055719
316 2854225726
317 2974055446
318 3098726250
319 3228426355
320 3363351584
321 3503704635
322 3649695540
323 3801542068
324 3959470110
325 4123714484
326 4294518688
327 4472135258
328 4656825708
329 4848861068
330 5048522272
331 5256101438
332 5471901324
333 5696235761
334 5929429796
335 6171820036
336 6423755822
337 6685599458
338 6957726915
339 7240527678
340 7534405036
341 7839776414
342 8157075142
343 8486750376
344 8829267966
345 9185110491
346 9554777356
347 9938785991
348 10337672466
349 10751992931
350 11182323790
351 11629262006
352 12093425095
353 12575453020
354 13076008550
355 13595778858
356 14135476100
357 14695837383
358 15277625796
359 15881631023
360 16508671366
361 17159594817
362 17835279822
363 18536635288
364 19264602320
365 20020154520
366 20804300398
367 21618084796
368 22462589532
369 23338934469
370 24248277828
371 25191818465
372 26170797600
373 27186500749
374 28240258340
375 29333447664
376 30467492884
377 31643867640
378 32864097434
379 34129761390
380 35442494252
381 36803986778
382 38215987884
383 39680306656
384 41198815263
385 42773450931
386 44406219010
387 46099193039
388 47854517352
389 49674409766
390 51561164512
391 53517155874
392 55544839639
393 57646755651
394 59825529716
395 62083876997
396 64424605290
397 66850620064
398 69364925684
399 71970628552
400 74670939814
401 77469178846
402 80368778574
403 83373288874
404 86486380810
405 89711849025
406 93053615340
407 96515732713
408 100102392272
409 103817926790
410 107666815664
411 111653688444
412 115783328528
413 120060679520
414 124490850742
415 129079124194
416 133830959130
417 138751996562
418 143848063662
419 149125182204
420 154589574280
421 160247670639
422 166106116566
423 172171776852
424 178451742926
425 184953339719
426 191684135766
427 198651951200
428 205864865296
429 213331222286
430 221059640980
431 229059022242
432 237338560720
433 245907755008
434 254776415856
435 263954675388
436 273452995248
437 283282179020
438 293453384270
439 303978134789
440 314868330362
441 326136259047
442 337794606152
443 349856469008
444 362335371668
445 375245278657
446 388600608960
447 402416247024
448 416707557670
449 431490401448
450 446781152379
451 462596714007
452 478954537424
453 495872633696
454 513369591708
455 531464597046
456 550177452022
457 569528597224
458 589539128806
459 610230818082
460 631626130492
461 653748248467
462 676621094798
463 700269359524
464 724718519706
465 749994862848
466 776125510484
467 803138444218
468 831062536096
469 859927575811
470 889764299244
471 920604414128
472 952480628624
473 985426681969
474 1019477381910
475 1054668635681
476 1091037484196
477 1128622133553
478 1167461988148
479 1207597690101
480 1249071158126
481 1291925629932
482 1336205699918
483 1381957357581
484 1429228026726
485 1478066613784
486 1528523552643
487 1580650854570
488 1634502154262
489 1690132754465
490 1747599676134
491 1806961710038
492 1868279475574
493 1931615476864
494 1997034157988
495 2064601956069
496 2134387362924
497 2206460984668
498 2280895611252
499 2357766283672
500 2437150358424
501 2519127574608
502 2603780120884
503 2691192712838
504 2781452671382
505 2874650002972
506 2970877475816
507 3070230701907
508 3172808215174
509 3278711562842
510 3388045399132
511 3500917578506
512 3617439250375
513 3737724949718
514 3861892697322
515 3990064103916
516 4122364481354
517 4258922952454
518 4399872565548
519 4545350400669
520 4695497688336
521 4850459933894
522 5010387046932
523 5175433475535
524 5345758334440
525 5521525539218
526 5702903942940
527 5890067483697
528 6083195336716
529 6282472075410
530 6488087821168
531 6700238402688
532 6919125519040
533 7144956912026
534 7377946550508
535 7618314811722
536 7866288667816
537 8122101869727
538 8385995141146
539 8658216381356
540 8939020884928
541 9228671553776
542 9527439117326
543 9835602351980
544 10153448308340
545 10481272555836
546 10819379432232
547 11168082303153
548 11527703817264
549 11898576166643
550 12281041354715
551 12675451487680
552 13082169065656
553 13501567288513
554 13934030358558
555 14379953786118
556 14839744712002
557 15313822240245
558 15802617791634
559 16306575457818
560 16826152359456
561 17361819006510
562 17914059681800
563 18483372830364
564 19070271474764
565 19675283633630
566 20298952741314
567 20941838079635
568 21604515218732
569 22287576486861
570 22991631452220
571 23717307416115
572 24465249906648
573 25236123191268
574 26030610793276
575 26849416043996
576 27693262650578
577 28562895272915
578 29459080111931
579 30382605500978
580 31334282526660
581 32314945670736
582 33325453477836
583 34366689232228
584 35439561653826
585 36545005591050
586 37683982750920
587 38857482454836
588 40066522418916
589 41312149556599
590 42595440782744
591 43917503843049
592 45279478164212
593 46682535742195
594 48127882056537
595 49616757015976
596 51150435899918
597 52730230332554
598 54357489283724
599 56033600107374
600 57759989621685
601 59538125203184
602 61369515906976
603 63255713602538
604 65198314149462
605 67198958613628
606 69259334537444
607 71381177217895
608 73566271020530
609 75816450714402
610 78133602847256
611 80519667179955
612 82976638156838
613 85506566419952
614 88111560339646
615 90793787581425
616 93555476716550
617 96398918906308
618 99326469618768
619 102340550400452
620 105443650672000
621 108638329560018
622 111927217793600
623 115313019657255
624 118798515017000
625 122386561382902
626 126080096012442
627 129882138054200
628 133795790773148
629 137824243829784
630 141970775647988
631 146238755829142
632 150631647608214
633 155153010373400
634 159806502249126
635 164595882780031
636 169525015686012
637 174597871684589
638 179818531360732
639 185191188119292
640 190720151199114
641 196409848807660
642 202264831340736
643 208289774673296
644 214489483524788
645 220868894887407
646 227433081569396
647 234187255842024
648 241136773198407
649 248287136192792
650 255643998376122
651 263213168294488
652 271000613624780
653 279012465433006
654 287255022552806
655 295734756076708
656 304458313925302
657 313432525537454
658 322664406682236
659 332161164426150
660 341930202234796
661 351979125216262
662 362315745443024
663 372948087422046
664 383884393708864
665 395133130690086
666 406702994541892
667 418602917312786
668 430842073152996
669 443429884675610
670 456376029500576
671 469690446988042
672 483383345183526
673 497465207894996
674 511946801947638
675 526839184598047
676 542153711148914
677 557902042802685
678 574096154716212
679 590748344265476
680 607871239475304
681 625477807653117
682 643581364249524
683 662195582004204
684 681334500306890
685 701012534810241
686 721244487241372
687 742045555440314
688 763431343684462
689 785417873292440
690 808021593537710
691 831259392806592
692 855148610009338
693 879707046250895
694 904952976843184
695 930905163620648
696 957582867619776
697 985005862048618
698 1013194445539986
699 1042169455733967
700 1071952283201794
701 1102564885785019
702 1134029803301162
703 1166370172607746
704 1199609742993342
705 1233772891963683
706 1268884641403114
707 1304970674220152
708 1342057351421048
709 1380171729586342
710 1419341578757588
711 1459595400727253
712 1500962447833318
713 1543472742252974
714 1587157095812284
715 1632047130257348
716 1678175298018448
717 1725574903420833
718 1774280124486480
719 1824326035314624
720 1875748629041304
721 1928584841366588
722 1982872574592485
723 2038650722260178
724 2095959194404812
725 2154838943499861
726 2215331991062631
727 2277481454931110
728 2341331577114240
729 2406927752344966
730 2474316557351636
731 2543545780905508
732 2614664454662228
733 2687722884714542
734 2762772683897176
735 2839866804838224
736 2919059573865032
737 3000406725793582
738 3083965439648756
739 3169794375182233
740 3257953710274184
741 3348505179206185
742 3441512111900024
743 3537039474208353
744 3635153909202216
745 3735923779475940
746 3839419210402218
747 3945712134424863
748 4054876336455790
749 4166987500496548
750 4282123257380358
751 4400363233699970
752 4521789101844944
753 4646484631219089
754 4774535740768440
755 4906030552835301
756 5041059448402446
757 5179715123626425
758 5322092647687160
759 5468289521993142
760 5618405740912380
761 5772543853996517
762 5930809029814458
763 6093309121282056
764 6260154732494320
765 6431459287165161
766 6607339098735904
767 6787913442306739
768 6973304628330616
769 7163638078068086
770 7359042400768920
771 7559649472730148
772 7765594518239340
773 7977016192622452
774 8194056667325518
775 8416861717002822
776 8645580808648178
777 8880367192793950
778 9121377996997294
779 9368774321644942
780 9622721338131028
781 9883388389338169
782 10150949092496896
783 10425581444395137
784 10707467929227258
785 10996795629111560
786 11293756337308656
787 11598546674141417
788 11911368205557514
789 12232427564527005
790 12561936575368224
791 12900112381174046
792 13247177574326127
793 13603360330143831
794 13968894543540046
795 14344019968955448
796 14728982363664188
797 15124033634605600
798 15529431988815560
799 15945442087351122
800 16372335202820717
801 16810389380573016
802 17259889603797974
803 17721127962657338
804 18194403827568808
805 18680024026466667
806 19178303026227448
807 19689563118313254
808 20214134608873420
809 20752356013521381
810 21304574256754868
811 21871144876097325
812 22452432230909164
813 23048809716092918
814 23660659980897350
815 24288375153104112
816 24932357068492518
817 25593017505743374
818 26270778426723094
819 26966072222357020
820 27679341964410996
821 28411041663306285
822 29161636532147036
823 29931603256859200
824 30721430272563408
825 31531618046348458
826 32362679366845664
827 33215139640660319
828 34089537195937624
829 34986423592953853
830 35906363941830160
831 36849937227661430
832 37817736643291984
833 38810369930116925
834 39828459726910502
835 40872643926765046
836 41943576042191122
837 43041925578751271
838 44168378417398364
839 45323637206014064
840 46508421760148168
841 47723469473018995
842 48969535734948102
843 50247394362425712
844 51557838037330210
845 52901678756514736
846 54279748291983028
847 55692898661656541
848 57142002610995220
849 58627954105593458
850 60151668835415244
851 61714084730896710
852 63316162491118560
853 64958886124191042
854 66643263499908272
855 68370326915180748
856 70141133672612180
857 71956766672703205
858 73818335019839426
859 75726974642294626
860 77683848926226572
861 79690149364320897
862 81747096219477980
863 83855939204025768
864 86017958174774707
865 88234463843930792
866 90506798506251266
867 92836336782778807
868 95224486381837632
869 97672688877742231
870 100182420507649128
871 102755192986477994
872 105392554340442594
873 108096089759557529
874 110867422469818000
875 113708214625698572
876 116620168223181660
877 119605026033686247
878 122664572559084022
879 125800635008483025
880 129015084297456032
881 132309836070506444
882 135686851746902775
883 139148139590421902
884 142695755803217292
885 146331805644506298
886 150058444574984536
887 153877879427545708
888 157792369604937262
889 161804228304514689
890 165915823770641596
891 170129580575415553
892 174447980928799456
893 178873566018682434
894 183408937381703144
895 188056758305031052
896 192819755259669438
897 197700719366204910
898 202702507893879442
899 207828045794074020
900 213080327268651050
901 218462417373719152
902 223977453659355836
903 229628647846412668
904 235419287541235602
905 241352737989643350
906 247432443870674334
907 253661931130681636
908 260044808858583760
909 266584771203171558
910 273285599333945072
911 280151163446442656
912 287185424812990670
913 294392437879441399
914 301776352408909078
915 309341415673373733
916 317091974694924956
917 325032478537711922
918 333167480651583376
919 341501641268277871
920 350039729850941196
921 358786627598535734
922 367747330006533968
923 376926949485460871
924 386330718038280462
925 395963989997726022
926 405832244824310952
927 415941089966921258
928 426296263787529220
929 436903638551694170
930 447769223486204626
931 458899167904717319
932 470299764402886638
933 481977452124487248
934 493938820100643672
935 506190610663898983
936 518739722938771106
937 531593216409629524
938 544758314567749624
939 558242408639224622
940 572053061395998420
941 586198011052194309
942 600685175247170196
943 615522655116966574
944 630718739455584764
945 646281908968409628
946 662220840620161874
947 678544412079929438
948 695261706264734614
949 712382015983720212
950 729914848684587450
951 747869931304790958
952 766257215230396660
953 785086881364989593
954 804369345311039814
955 824115262665380562
956 844335534431135628
957 865041312548748540
958 886244005549489332
959 907955284333921894
960 930187088078249264
961 952951630270439807
962 976261404878681588
963 1000129192655422554
964 1024568067580250504
965 1049591403445205166
966 1075212880585048544
967 1101446492755180891
968 1128306554159942671
969 1155807706635089820
970 1183964926987877660
971 1212793534498982658
972 1242309198589122800
973 1272527946653345909
974 1303466172066388852
975 1335140642362817297
976 1367568507596649484
977 1400767308884365716
978 1434754987135102160
979 1469549891971241206
980 1505170790843415544
981 1541636878343872136
982 1578967785723672420
983 1617183590618104506
984 1656304826984490512
985 1696352495256382858
986 1737348072718111124
987 1779313524105051795
988 1822271312434842588
989 1866244410075038742
990 1911256310051766968
991 1957331037604088026
992 2004493161988334820
993 2052767808538693667
994 2102180670989866116
995 2152758024067857746
996 2204526736354398948
997 2257514283429727467
998 2311748761299584876
999 2367258900112497362
1000 2424074078174504180