-1 1
0 0
1 2
2 1
3 3
4 3
5 5
6 5
7 10
8 8
9 14
10 14
11 23
12 21
13 33
14 32
15 49
16 49
17 69
18 70
19 99
20 100
21 136
22 142
23 190
24 198
25 259
26 271
27 351
28 370
29 469
30 498
31 627
32 665
33 824
34 884
35 1084
36 1162
37 1413
38 1518
39 1833
40 1974
41 2360
42 2548
43 3031
44 3272
45 3865
46 4185
47 4917
48 5321
49 6218
50 6739
51 7838
52 8501
53 9837
54 10675
55 12310
56 13358
57 15339
58 16657
59 19060
60 20696
61 23601
62 25633
63 29141
64 31652
65 35869
66 38962
67 44041
68 47826
69 53913
70 58556
71 65847
72 71492
73 80208
74 87074
75 97477
76 105802
77 118184
78 128247
79 142990
80 155114
81 172606
82 187207
83 207951
84 225458
85 250018
86 270984
87 300021
88 325074
89 359336
90 389212
91 429624
92 465163
93 512721
94 554957
95 610876
96 660935
97 726592
98 785845
99 862851
100 932861
101 1023034
102 1105624
103 1211144
104 1308388
105 1431663
106 1546050
107 1689937
108 1824219
109 1991965
110 2149416
111 2344775
112 2529124
113 2756352
114 2971910
115 3236005
116 3487683
117 3794226
118 4087768
119 4443278
120 4785142
121 5197005
122 5594718
123 6071419
124 6533537
125 7084706
126 7621056
127 8257819
128 8879563
129 9614439
130 10334490
131 11181893
132 12014788
133 12991054
134 13953546
135 15077318
136 16188410
137 17480799
138 18762173
139 20247355
140 21723596
141 23428781
142 25128045
143 27084321
144 29038326
145 31280848
146 33525825
147 36094487
148 38671436
149 41611315
150 44566759
151 47929103
152 51315648
153 55158123
154 59035572
155 63423626
156 67859295
157 72866735
158 77937018
159 83647244
160 89438324
161 95945299
162 102554549
163 109964529
164 117501673
165 125934046
166 134523164
167 144112712
168 153893218
169 164791513
170 175920796
171 188298473
172 200953544
173 215002286
174 229382361
175 245318015
176 261646922
177 279711434
178 298241124
179 318706549
180 339719480
181 362890887
182 386704576
183 412924247
184 439894728
185 469546107
186 500072733
187 533585934
188 568116077
189 605972162
190 645007492
191 687745461
192 731846998
193 780069586
194 829865768
195 884247192
196 940440651
197 1001734179
198 1065110644
199 1134158499
200 1205595708
201 1283337613
202 1363816622
203 1451302212
204 1541917474
205 1640317484
206 1742291068
207 1852911386
208 1967606055
209 2091902005
210 2220837356
211 2360431408
212 2505300586
213 2661998827
214 2824688778
215 3000502886
216 3183113610
217 3380281888
218 3585151680
219 3806164369
220 4035894220
221 4283519944
222 4541002686
223 4818319876
224 5106770830
225 5417198684
226 5740191772
227 6087528985
228 6449032614
229 6837496093
230 7241917662
231 7676187782
232 8128418412
233 8613686949
234 9119153574
235 9661179462
236 10225900156
237 10831066100
238 11461714020
239 12137094533
240 12841063414
241 13594494809
242 14379976973
243 15220137534
244 16096204610
245 17032700421
246 18009395335
247 19052858143
248 20141293942
249 21303483019
250 22515955116
251 23809876115
252 25159979524
253 26600009073
254 28102774643
255 29704801072
256 31376838623
257 33158413552
258 35018073264
259 36998582292
260 39066128716
261 41266971714
262 43564779165
263 46009576608
264 48562336226
265 51277147968
266 54112103680
267 57125673850
268 60272873296
269 63616894853
270 67109469486
271 70818879624
272 74693347848
273 78806642931
274 83103247676
275 87662838651
276 92425908045
277 97478500363
278 102756853619
279 108353869272
280 114201251440
281 120399286183
282 126874849945
283 133736180201
284 140905008537
285 148498135138
286 156431819666
287 164832075422
288 173609337630
289 182899540157
290 192606924246
291 202878097188
292 213610715183
293 224962870407
294 236825224241
295 249368224697
296 262475098426
297 276329587333
298 290807029862
299 306105461249
300 322091845763
301 338979595490
302 356626792349
303 375263380196
304 394738022718
305 415298438475
306 436783313296
307 459459473758
308 483155030412
309 508157352448
310 534283360074
311 561842494973
312 590639831898
313 621008539529
314 652741164344
315 686196367016
316 721153449046
317 757998460808
318 796496713178
319 837063681009
320 879449893378
321 924102436692
322 970756246304
323 1019892354502
324 1071229243415
325 1125284410279
326 1181758992731
327 1241209642101
328 1303319221056
329 1368686424091
330 1436974875952
331 1508828410695
332 1583890400790
333 1662853145165
334 1745338728328
335 1832091465614
336 1922711065448
337 2017997685380
338 2117527537096
339 2222160706952
340 2331448748772
341 2446316064486
342 2566288357876
343 2692359046690
344 2824026739800
345 2962358914942
346 3106825826218
347 3258574400846
348 3417045227433
349 3583470480819
350 3757259748152
351 3939736647219
352 4130278395328
353 4330306699367
354 4539165019088
355 4758380269748
356 4987260722744
357 5227446137228
358 5478208170579
359 5741307586789
360 6015977968012
361 6304109852483
362 6604897285002
363 6920369951091
364 7249680889014
365 7595008981248
366 7955464803182
367 8333387196531
368 8727842806025
369 9141341969525
370 9572905983872
371 10025229016072
372 10497285605103
373 10991966987405
374 11508199587412
375 12049085865757
376 12613502827310
377 13204779326324
378 13821741725948
379 14467961514857
380 15142213252184
381 15848328463557
382 16585028883598
383 17356424680483
384 18161183841787
385 19003715137591
386 19882632048225
387 20802663285585
388 21762367232294
389 22766815402591
390 23814510708534
391 24910891936469
392 26054406356852
393 27250886238105
394 28498723349513
395 29804171466012
396 31165567268904
397 32589616083327
398 34074600280866
399 35627708860210
400 37247171050115
401 38940693923191
402 40706455195558
403 42552716827875
404 44477607117254
405 46489982331497
406 48587924055440
407 50780925012492
408 53067023372246
409 55456393474607
410 57947034093938
411 60549849473698
412 63262803789626
413 66097582882056
414 69052122017878
415 72138943943852
416 75355961631071
417 78716593937163
418 82218739284484
419 85876775943443
420 89688596675652
421 93669606959019
422 97817704118948
423 102149393326038
424 106662588135348
425 111374970984815
426 116284484948305
427 121410072716576
428 126749721878666
429 132323724181146
430 138130128731744
431 144190671276458
432 150503481517063
433 157091840838201
434 163953980974084
435 171114837611388
436 178572768505936
437 186354479907065
438 194458482417777
439 202913377194387
440 211717857522756
441 220902552491329
442 230466371349540
443 240442113327395
444 250828940528152
445 261661974503958
446 272940671148348
447 284702637016910
448 296947667098242
449 309716026958668
450 323007900801906
451 336866399272704
452 351292151045706
453 366331310848003
454 381985012856060
455 398302668596330
456 415285984881444
457 432987857589573
458 451410640068468
459 470610955768768
460 490591885771460
461 511414041184367
462 533081320014132
463 555658599076340
464 579150691048609
465 603627035756652
466 629093467791927
467 655624307731321
468 683226529416138
469 711979673963062
470 741891982895106
471 773048580994158
472 805459117859788
473 839214690139466
474 874326508943898
475 910892057706907
476 948924276456952
477 988527478945951
478 1029716516906445
479 1072603008345754
480 1117203915885088
481 1163638668448627
482 1211926556649150
483 1262195361685960
484 1314466938568219
485 1368877999354150
486 1425453220813880
487 1484338864126573
488 1545562707663504
489 1609281222438298
490 1675525592843406
491 1744463205590541
492 1816128981771539
493 1890701978163226
494 1968221211794706
495 2048878215364940
496 2132716491816349
497 2219940910802931
498 2310599884433464
499 2404912539165331
500 2502932655219424
501 2604894598590928
502 2710858015397508
503 2821073560826745
504 2935607286215612
505 3054727257375788
506 3178506515202398
507 3307231733830998
508 3440983576457559
509 3580068604882001
510 3724575789618844
511 3874832946499875
512 4030938094435864
513 4193241762654150
514 4361851820306715
515 4537143068375476
516 4719234093124032
517 4908525631689048
518 5105147924583428
519 5309529422250004
520 5521813032072994
521 5742456815534972
522 5971617440867130
523 6209784606857927
524 6457129923775661
525 6714176891250296
526 6981113337025758
527 7258498871265935
528 7546538915495094
529 7845831656488690
530 8156601594598500
531 8479488125642272
532 8814736430553180
533 9163029924390853
534 9524636195986148
535 9900285679302686
536 10290270232930078
537 10695370511634975
538 11115904650661801
539 11552706942830531
540 12006123962133832
541 12477047286895965
542 12965854258944008
543 13473497634498574
544 14000388031366510
545 14547543537619665
546 15115410747549708
547 15705077513756751
548 16317029313522452
549 16952428494020245
550 17611802543636466
551 18296393350810890
552 19006773780214998
553 19744270646451114
554 20509505810317525
555 21303896757379460
556 22128118237231939
557 22983684535287421
558 23871327475311426
559 24792664680643127
560 25748489547858612
561 26740530012665442
562 27769645879518628
563 28837682835549867
564 29945572287901315
565 31095285610064890
566 32287831392570018
567 33525315157912792
568 34808828673786362
569 36140620637171419
570 37521872429351676
571 38954985546755063
572 40441237894123744
573 41983194031293070
574 43582235804030472
575 45241101779806367
576 46961285705595124
577 48745711826297330
578 50595994331611515
579 52515255585754897
580 54505239384460212
581 56569279476187242
582 58709259091622044
583 60928737504780684
584 63229747921663672
585 65616090216905766
586 68089958874131944
587 70655410437515429
588 73314812784536965
589 76072496257234186
590 78931015114209032
591 81894991750876129
592 84967180725173110
593 88152515942364685
594 91453967173528430
595 94876800568676458
596 98424217089286242
597 102101837226532956
598 105913110247228983
599 109864034528952270
600 113958325973383966
601 118202385933266420
602 122600216573224704
603 127158648951903983
604 131881992511796377
605 136777536496793205
606 141849920124016606
607 147106921162753038
608 152553532683360030
609 158198053301591358
610 164045855710187108
611 170105793799832107
612 176383647458622012
613 182888862524606407
614 189627655580959944
615 196610103472101225
616 203842891032357816
617 211336767711899037
618 219098920347692200
619 227140815297539921
620 235470177494634344
621 244099237382063595
622 253036296583609857
623 262294399863781664
624 271882466798151843
625 281814409963895911
626 292099810995799712
627 302753507236024964
628 313785789521643740
629 325212480594618490
630 337044630875863576
631 349299113058144438
632 361987790980518784
633 375128656003140153
634 388734442901152086
635 402824334847564524
636 417411998997560374
637 432517888193892119
638 448156667602645086
639 464350142601311822
640 481114046460456278
641 498471625283521850
642 516439755296656986
643 535043217182727399
644 554300110043844770
645 574236849016218096
646 594872841402471192
647 616236243065007821
648 638347860588047272
649 661237703637139258
650 684928075293898621
651 709450959334369932
652 734830259088191883
653 761100060435685225
654 788285977667037504
655 816424334929147450
656 845542575599070959
657 875679406934423413
658 906864227423474420
659 939138281503248859
660 972533057205958124
661 1007092500021141305
662 1042850330912512871
663 1079853370710617343
664 1118137726231501158
665 1157753279002984270
666 1198738684764170756
667 1241147082854191573
668 1285019851808613764
669 1330413598383681510
670 1377372609285519112
671 1425957181561425874
672 1476214707699468110
673 1528209412008210613
674 1581992003393474268
675 1637630885365095185
676 1695180307740357096
677 1754713121071470541
678 1816287355326323408
679 1879980592826959550
680 1945854898616280744
681 2013992889447241309
682 2084460937050609194
683 2157347014312948919
684 2232722089013793100
685 2310679832097875000
686 2391296115632849352
687 2474670672013958901
688 2560884605911958408
689 2650044097359309821
690 2742235833294060834
691 2837572851770666324
692 2936147794356689614
693 3038080993202358878
694 3143471441002597456
695 3252447227343835806
696 3365114118201214566
697 3481608452882957353
698 3602043220070963073
699 3726563531798923163
700 3855290077870051590
701 3988377298650859421
702 4125954094290671313
703 4268184823695196096
704 4415207139324792550
705 4567195945547732593
706 4724298223894773877
707 4886700090078346518
708 5054558468425512604
709 5228071393214788061
710 5407406384573240906
711 5592774146424792899
712 5784353489425755356
713 5982368584756597310
714 6187010272657454556
715 6398517038538375596
716 6617092538356469519
717 6842990471088476747
718 7076428144547758350
719 7317675426155760330
720 7566964164823669652
721 7824581410210065254
722 8090774497958940393
723 8365848736238338656
724 8650067952938503444
725 8943756857274371493
726 9247196838473373945
727 9560733219605057389
728 9884666087819246970
729 10219362667364535596
730 10565142951553498110
731 10922397432147971186
732 11291467292919769510
733 11672767743255446163
734 12066662522412567532
735 12473593096330589598
736 12893947210457837361
737 13328194220377552611
738 13776747419361317334
739 14240105785545717281
740 14718709798142545788
741 15213089896563566340
742 15723715486460576888
743 16251150419395432202
744 16795894876581400212
745 17358548191481910278
746 17939643285235274702
747 18539817168941767157
748 19159637590278313476
749 19799781567235628658
750 20460853890322001924
751 21143574055160619586
752 21848586248926387401
753 22576655065547292534
754 23328466588582913427
755 24104833289797966278
756 24906485803558668622
757 25734287427320348869
758 26589016164735757712
759 27471589265128674104
760 28382835093875255188
761 29323728167266541629
762 30295150389284469359
763 31298137058414557388
764 32333626989671060880
765 33402719990955066398
766 34506415368047965332
767 35645881390029400526
768 36822181652931716633
769 38036557076607629549
770 39290139579757116344
771 40584247174478206663
772 41920084381436426899
773 43299051013198783655
774 44722428733347033720
775 46191704145619210795
776 47708240874743387666
777 49273617605452370469
778 50889285035683612960
779 52556919537706836742
780 54278064306067610808
781 56054499342460181406
782 57887866091310015316
783 59780054480653728261
784 61732810307548340885
785 63748140099154891675
786 65827900478147587353
787 67974221641482054271
788 70189077902618563383
789 72474730620163324618
790 74833279078953241196
791 77267123736913204426
792 79778496570834830172
793 82369945547497695683
794 85043843522217803983
795 87802894879563913992
796 90649622033433950540
797 93586895223643065967
798 96617395625308657624
799 99744169330252075308
800 102970066030786176199
801 106298318259348377034
802 109731954567309807850
803 113274405142578571036
804 116928888357733319108
805 120699043933627232532
806 124588291682877692555
807 128600493437803344425
808 132739282765045889484
809 137008756928588665538
810 141412776298925729270
811 145955687676514567933
812 150641592064377579130
813 155475100734246003444
814 160460569974681066808
815 165602891341420172425
816 170906691933970002924
817 176377160333421108311
818 182019210898855043105
819 187838346960205050666
820 193839787561690387236
821 200029369544297637084
822 206412635096660776212
823 212995774431514398285
824 219784672434894801066
825 226785893713611939218
826 234005686561232036472
827 241451012229297103107
828 249128504353173480442
829 257045544378600533128
830 265209174511983823700
831 273627221315953737779
832 282307160166985166112
833 291257289119151809878
834 300485542766887108759
835 310000718565151828092
836 319811237906606480656
837 329926427179140386937
838 340355223774551068768
839 351107514260903993678
840 362192782943893640664
841 373621509632038847874
842 385403758272028202084
843 397550636889408113908
844 410072823715306957408
845 422982091994239283799
846 436289770911440028826
847 450008338072842848438
848 464149812429700427146
849 478727417353910624520
850 493753902639461087940
851 509243281219196416933
852 525209077200756506687
853 541666139398874479218
854 558628812236627949584
855 576112829400566610298
856 594133404306148781684
857 612707207321664039570
858 631850372359417032726
859 651580561258730443327
860 671914882921588592224
861 692872048595243074796
862 714470199822403379944
863 736729158520284097681
864 759668159860839202681
865 783308201205819061072
866 807669675871683194394
867 832774825149556249089
868 858645268742167167002
869 885304564273809062768
870 912775630012614593946
871 941083416458984119730
872 970252216785494214160
873 1000308455283088240495
874 1031277880762633281470
875 1063188476836680458044
876 1096067533330893998837
877 1129944683585792348352
878 1164848848722597836851
879 1200811407364297736441
880 1237863007388700895416
881 1276036873691786331172
882 1315365481840505512782
883 1355884009734029754760
884 1397626867339820114862
885 1440631298350448500584
886 1484933759948306353837
887 1530573680807435751147
888 1577589684584657461274
889 1626023510877805130789
890 1675916075883566070096
891 1727311563195967832457
892 1780253314803575446076
893 1834788098895501158292
894 1890961824092302312342
895 1948823991721569726089
896 2008423225887562454996
897 2069811917985079674249
898 2133041564912099603774
899 2198167613909513498257
900 2265244600908419630566
901 2334331204115005385408
902 2405485174159124765082
903 2478768605188548284808
904 2554242648147679322634
905 2631973008504128796165
906 2712024433635305585793
907 2794466446683315954139
908 2879367598662244037514
909 2966801448325345910904
910 3056840569226557329684
911 3149562785887312454103
912 3245044925651690590958
913 3343369321859686501653
914 3444617299925752766712
915 3548875958661486993984
916 3656231379581697525100
917 3766775697972968195638
918 3880600023989043177272
919 3997801815533214395675
920 4118477499245217766982
921 4242730157755631683102
922 4370661838188908292161
923 4502381566857567542199
924 4637997332409841441588
925 4777624441561312498595
926 4921377163500090715764
927 5069377440804323990102
928 5221746181182288204825
929 5378612338296776639726
930 5540103836361071149854
931 5706357036186392610943
932 5877507277576722647673
933 6053698746534221257325
934 6235074619795426685718
935 6421787349772578015797
936 6613988394950068597008
937 6811838939808074002759
938 7015499194150250299308
939 7225139565950785165522
940 7440929512011491904488
941 7663049182395471819463
942 7891677804112867545520
943 8127005816554745637040
944 8369222769180946378064
945 8618529968147748088248
946 8875127868217426791152
947 9139229251583713104707
948 9411046093439894973586
949 9690803294848403557211
950 9978725000591306845034
951 10275048908805609550476
952 10580012018895876400780
953 10893865541566362987091
954 11216860053698941288980
955 11549261033358244258504
956 11891333397627929428677
957 12243357688147082280870
958 12605613966952841404780
959 12978398679126588789752
960 13362007880709875838706
961 13756754806099127110192
962 14162952401083124140982
963 14580931623726389382393
964 15011023254519044838176
965 15453576960633409370010
966 15908942354079221749204
967 16377488850406842720209
968 16859585944621230924844
969 17355623896640301808382
970 17865993193538062388644
971 18391106095349690996597
972 18931375250986384419624
973 19487236139311668408998
974 20059124804795923403143
975 20647501230172991825343
976 21252826156579568594318
977 21875585425539422658754
978 22516265846959874608399
979 23175380549684854281254
980 23853443859295817542764
981 24550997698026660246651
982 25268585432837671954539
983 26006779367096973241180
984 26766153517861617152062
985 27547312243404272675641
986 28350861907043088002412
987 29177440686330920831144
988 30027689079123244127686
989 30902280942052904583161
990 31801892792810750354928
991 32727236127404127226334
992 33679025470845903239323
993 34658012024642461164197
994 35664950416240956783612
995 36700633730214896230484
996 37765858904904502533350
997 38861463202868226867080
998 39988288201164232762841
999 41147217758817039154321
1000 42339140545127081667412