-1 1
0 0
1 1
2 1
3 1
4 0
5 2
6 1
7 3
8 3
9 3
10 2
11 6
12 4
13 6
14 6
15 8
16 6
17 11
18 9
19 13
20 14
21 16
22 14
23 24
24 19
25 27
26 27
27 33
28 30
29 43
30 38
31 51
32 51
33 61
34 58
35 79
36 72
37 92
38 94
39 110
40 106
41 138
42 130
43 160
44 164
45 189
46 188
47 235
48 226
49 270
50 279
51 321
52 320
53 388
54 381
55 448
56 462
57 525
58 530
59 631
60 626
61 724
62 750
63 846
64 860
65 1001
66 1006
67 1149
68 1192
69 1331
70 1364
71 1567
72 1587
73 1791
74 1862
75 2069
76 2126
77 2413
78 2459
79 2754
80 2866
81 3162
82 3262
83 3668
84 3754
85 4171
86 4348
87 4775
88 4938
89 5502
90 5658
91 6243
92 6512
93 7117
94 7378
95 8163
96 8419
97 9235
98 9645
99 10497
100 10900
101 11981
102 12390
103 13528
104 14129
105 15320
106 15934
107 17420
108 18048
109 19616
110 20500
111 22158
112 23066
113 25095
114 26046
115 28202
116 29480
117 31758
118 33094
119 35860
120 37262
121 40200
122 42034
123 45162
124 47090
125 50831
126 52878
127 56876
128 59471
129 63733
130 66486
131 71540
132 74476
133 79877
134 83526
135 89313
136 93198
137 99985
138 104156
139 111432
140 116516
141 124318
142 129766
143 138848
144 144702
145 154454
146 161490
147 171972
148 179528
149 191631
150 199787
151 212811
152 222470
153 236481
154 246892
155 262980
156 274220
157 291537
158 304728
159 323388
160 337614
161 358902
162 374301
163 397255
164 415138
165 439877
166 459210
167 487301
168 508234
169 538519
170 562648
171 595341
172 621432
173 658349
174 686642
175 726491
176 758856
177 801872
178 836910
179 885301
180 923286
181 975527
182 1018722
183 1075156
184 1121932
185 1185135
186 1235878
187 1304156
188 1361524
189 1435278
190 1497440
191 1579770
192 1647184
193 1736113
194 1811986
195 1908079
196 1990276
197 2097176
198 2186334
199 2301830
200 2401717
201 2526502
202 2634742
203 2773173
204 2890524
205 3040063
206 3171052
207 3332643
208 3474530
209 3653266
210 3807104
211 4000188
212 4171264
213 4379860
214 4565168
215 4795358
216 4996167
217 5244759
218 5467406
219 5735951
220 5977020
221 6272633
222 6533802
223 6853037
224 7141730
225 7486461
226 7798982
227 8177699
228 8516094
229 8924922
230 9298040
231 9739453
232 10143158
233 10627093
234 11064051
235 11586354
236 12066976
237 12630668
238 13150504
239 13767429
240 14329766
241 14995341
242 15612561
243 16330674
244 16997904
245 17782441
246 18503910
247 19350051
248 20140286
249 21052851
250 21906744
251 22902182
252 23824950
253 24898106
254 25907012
255 27064005
256 28153570
257 29413718
258 30590584
259 31948644
260 33233082
261 34696572
262 36083068
263 37674874
264 39171562
265 40886293
266 42517256
267 44364390
268 46123946
269 48130338
270 50028762
271 52189247
272 54254844
273 56581043
274 58808382
275 61332157
276 63733856
277 66450181
278 69059832
279 71983293
280 74795708
281 77963717
282 80994670
283 84402966
284 87691984
285 91358454
286 94901178
287 98870093
288 102685923
289 106953850
290 111089588
291 115678811
292 120131092
293 125093660
294 129886593
295 135220700
296 140409410
297 146142330
298 151725286
299 157918593
300 163925300
301 170579193
302 177074934
303 184223101
304 191208578
305 198923501
306 206435202
307 214720173
308 222834988
309 231731185
310 240453280
311 250046449
312 259420385
313 269717548
314 279834438
315 290886258
316 301754408
317 313661897
318 325336182
319 338111794
320 350699598
321 364405055
322 377920712
323 392675489
324 407185884
325 423008996
326 438641242
327 455608402
328 472384118
329 490636033
330 508637228
331 528201989
332 547578576
333 568548183
334 589331702
335 611872606
336 634162774
337 658314004
338 682288249
339 708162095
340 733864112
341 761656765
342 789208206
343 818973260
344 848583516
345 880457131
346 912185798
347 946399931
348 980394608
349 1017020440
350 1053528902
351 1092732024
352 1131833170
353 1173887221
354 1215760550
355 1260759322
356 1305697350
357 1353841239
358 1401947696
359 1453560159
360 1505052210
361 1560254536
362 1615478246
363 1674513368
364 1733602538
365 1796851991
366 1860069994
367 1927689816
368 1995445096
369 2067728577
370 2140193016
371 2217591101
372 2295082570
373 2377793258
374 2460794876
375 2549172669
376 2637902262
377 2732479121
378 2827320846
379 2928347361
380 3029871536
381 3137774506
382 3246256328
383 3361664391
384 3477566479
385 3600793394
386 3724789978
387 3856350207
388 3988785564
389 4129420722
390 4270852354
391 4420954330
392 4572178231
393 4732365110
394 4893810698
395 5064958545
396 5237295732
397 5419890313
398 5604059708
399 5798843961
400 5995377462
401 6203384787
402 6413087590
403 6634918753
404 6858900892
405 7095446730
406 7334365436
407 7586845895
408 7841666538
409 8110820370
410 8382854032
411 8669749341
412 8959803452
413 9265878927
414 9575110908
415 9901273084
416 10231229633
417 10578756235
418 10930427532
419 11301016205
420 11675786672
421 12070544676
422 12470240136
423 12890695896
424 13316524810
425 13764679420
426 14218297738
427 14695501110
428 15179061800
429 15687138551
430 16202113836
431 16743424045
432 17291790606
433 17867973440
434 18452271096
435 19065504406
436 19687519964
437 20340584258
438 21002676578
439 21697559326
440 22402721604
441 23142017514
442 23892414750
443 24679400602
444 25477843044
445 26314920608
446 27164936354
447 28055196015
448 28959400142
449 29906700156
450 30868439031
451 31875677500
452 32899106312
453 33969957984
454 35058230522
455 36197238867
456 37354333686
457 38564986298
458 39795797334
459 41082461637
460 42390782264
461 43758804446
462 45149362516
463 46602933369
464 48081488180
465 49625791253
466 51196898862
467 52838224692
468 54507495384
469 56250867834
470 58025079264
471 59876647061
472 61761258346
473 63728417703
474 65730082760
475 67818848337
476 69945536728
477 72163192602
478 74421437198
479 76776678533
480 79174360610
481 81674373273
482 84220862610
483 86874271058
484 89577369360
485 92394388081
486 95263424973
487 98252628783
488 101298612174
489 104470199816
490 107702435102
491 111068404033
492 114497921994
493 118068485433
494 121708215594
495 125495426673
496 129356448310
497 133374388470
498 137469735234
499 141730555281
500 146075403216
501 150593331993
502 155200856520
503 159992417190
504 164878001862
505 169957626494
506 175139078888
507 180523554043
508 186016517124
509 191725218341
510 197547837204
511 203597886954
512 209771042887
513 216182224944
514 222724470118
515 229519497059
516 236452211716
517 243651368444
518 250999029576
519 258625616861
520 266410194798
521 274490819507
522 282737490210
523 291296158402
524 300033594316
525 309097722473
526 318351914924
527 327952660622
528 337753225888
529 347918960822
530 358299473476
531 369062435400
532 380053602696
533 391450254664
534 403086893166
535 415150733680
536 427472132390
537 440241033084
538 453283435050
539 466800051081
540 480604348854
541 494908182696
542 509520332990
543 524655845979
544 540118573382
545 556135632595
546 572496933878
547 589442077882
548 606755675442
549 624681056067
550 642997267106
551 661961157924
552 681336269036
553 701393435815
554 721890218686
555 743101793745
556 764779441556
557 787213479684
558 810137956494
559 833858846872
560 858103452356
561 883182795414
562 908817101238
563 935334338256
564 962435586280
565 990466341540
566 1019120085264
567 1048748164236
568 1079036088186
569 1110354168189
570 1142366660232
571 1175463483994
572 1209300338892
573 1244273919928
574 1280030961864
575 1316989367359
576 1354772283684
577 1393819548459
578 1433744689975
579 1474995370193
580 1517175038028
581 1560755071226
582 1605312762050
583 1651344009010
584 1698415294558
585 1747031544567
586 1796747927474
587 1848095873002
588 1900601550780
589 1954823800777
590 2010276663692
591 2067529370358
592 2126083264756
593 2186537194786
594 2248360380822
595 2312182292322
596 2377458544102
597 2444830556927
598 2513739718228
599 2584860526117
600 2657598793289
601 2732663222753
602 2809444389060
603 2888664712770
604 2969698831570
605 3053306103958
606 3138821800558
607 3227043467328
608 3317289314258
609 3410372619233
610 3505593766668
611 3603807260861
612 3704269936944
613 3807878928871
614 3913871996154
615 4023164283303
616 4134973619548
617 4250261157726
618 4368196586236
619 4489788621487
620 4614185633632
621 4742416943112
622 4873608665732
623 5008841442172
624 5147188188950
625 5289782610688
626 5435673831178
627 5586019086558
628 5739842663632
629 5898359037667
630 6060533748876
631 6227640443903
632 6398618120336
633 6574767283256
634 6754999246262
635 6940678324720
636 7130650983792
637 7326347512795
638 7526584805596
639 7732823763102
640 7943850435258
641 8161196852240
642 8383577530688
643 8612598027061
644 8846939928056
645 9088243656785
646 9335156479844
647 9589398073776
648 9849536826303
649 10117374349119
650 10391442404717
651 10673582267851
652 10962287532842
653 11259487768346
654 11563589652466
655 11876614021858
656 12196926841622
657 12526594039872
658 12863939184976
659 13211126533282
660 13566383918036
661 13931977246947
662 14306089151918
663 14691036743427
664 15084955586934
665 15490272283571
666 15905017021278
667 16331729575872
668 16768389979712
669 17217596118306
670 17677275834424
671 18150148888548
672 18634027182478
673 19131756466424
674 19641093053578
675 20164948574847
676 20701021506880
677 21252359126463
678 21816532435190
679 22396728914408
680 22990457995400
681 23600981810247
682 24225745770364
683 24868162928624
684 25525538600718
685 26201441847440
686 26893109867360
687 27604196227908
688 28331867310056
689 29079944577514
690 29845440553192
691 30632350237087
692 31437610839284
693 32265312977241
694 33112315613832
695 33982896089530
696 34873744471862
697 35789331113764
698 36726262912366
699 37689118315723
700 38674417821790
701 39686947518651
702 40723042630191
703 41787703856274
704 42877174636828
705 43996577812028
706 45142061533102
707 46318979473504
708 47523276642680
709 48760545315871
710 50026629329224
711 51327258862212
712 52658172733374
713 54025357711185
714 55424330040012
715 56861341687974
716 58331797460492
717 59842104957876
718 61387553376742
719 62974835462394
720 64598996671386
721 66267024481896
722 67973841745525
723 69726611452641
724 71520129287464
725 73361875087189
726 75246377806673
727 77181444757206
728 79161470109818
729 81194459024181
730 83274665953260
731 85410448041219
732 87595768015600
733 89839346837500
734 92134999237224
735 94491669054765
736 96903017638892
737 99378379814306
738 101911098099102
739 104510911415637
740 107170999915776
741 109901353495137
742 112694984127372
743 115562315917419
744 118496012582470
745 121506947027257
746 124587605054234
747 127749142006527
748 130983859446440
749 134303394885564
750 137699669778636
751 141184819977978
752 144750572161704
753 148409379911232
754 152152768316006
755 155993726275137
756 159923364260742
757 163955224471301
758 168080204412726
759 172312203513530
760 176641898920424
761 181083784336270
762 185628085000468
763 190289908819842
764 195059248408040
765 199951613166318
766 204956755142350
767 210090843337617
768 215343137573422
769 220730488609297
770 226241902495640
771 231894681007692
772 237677567842688
773 243608596826902
774 249675975950484
775 255898495648389
776 262264087373070
777 268792048030602
778 275470023344122
779 282318122545252
780 289323408736198
781 296506830765959
782 303855150806488
783 311389886179380
784 319097488225066
785 327000375603331
786 335084366554568
787 343372811322087
788 351851201055854
789 360543523861512
790 369434933235184
791 378550417232472
792 387874441919082
793 397433028902512
794 407210289251026
795 417232959982077
796 427484785827692
797 437993613087575
798 448742440746624
799 459760261622400
800 471029689912773
801 482580520575300
802 494394970972270
803 506504066460528
804 518889216049834
805 531582716853411
806 544565561468890
807 557870946033870
808 571479433869258
809 585425585768885
810 599689089690198
811 614305916920603
812 629255305434188
813 644574233837902
814 660241476518852
815 676295525465938
816 692714207979456
817 709537580325549
818 726742984397466
819 744371604697977
820 762400283265408
821 780871882831436
822 799762221805398
823 819115897552528
824 838908205717844
825 859185006993839
826 879921059069540
827 901164083464991
828 922887732596688
829 945141651432494
830 967898930484124
831 991210628827257
832 1015049259038260
833 1039467943395181
834 1064438002387540
835 1090014690885796
836 1116168726535836
837 1142956946687859
838 1170349449405556
839 1198405359401783
840 1227093490404344
841 1256475331509535
842 1286519051100414
843 1317287908601569
844 1348749409529276
845 1380969349082403
846 1413913850758362
847 1447651330888619
848 1482147223617796
849 1517471925281668
850 1553590162550850
851 1590575142686623
852 1628390107009612
853 1667111168435862
854 1706700833792772
855 1747237429850730
856 1788682710162560
857 1831118117329430
858 1874503810665050
859 1918924453582492
860 1964339424804108
861 2010835862498778
862 2058372345598550
863 2107039465824937
864 2156794093306551
865 2207730389804033
866 2259804398328602
867 2313113046287680
868 2367611529949208
869 2423400604486978
870 2480433637356316
871 2538815340590259
872 2598498207926882
873 2659590041468565
874 2722042441488040
875 2785967452349188
876 2851314720071804
877 2918200674500336
878 2986574042015212
879 3056554704120238
880 3128090447746372
881 3201305855926729
882 3276146630883645
883 3352742215900378
884 3431037348898104
885 3511165327948294
886 3593069907219164
887 3676889595004373
888 3762565925521974
889 3850242793370878
890 3939860726130896
891 4031567922367650
892 4125303884066390
893 4221222583646835
894 4319261163799110
895 4419579565936114
896 4522113887003438
897 4627028872981906
898 4734259557163766
899 4843977083687439
900 4956113983599540
901 5070848015654015
902 5188110630736732
903 5308084949802019
904 5430701326971538
905 5556149973060923
906 5684358594464010
907 5815524731751636
908 5949574982758316
909 6086712871537494
910 6226863872796252
911 6370239366626412
912 6516762032886786
913 6666651373774330
914 6819828940214714
915 6976520909762669
916 7136647692297908
917 7300444170294381
918 7467827811582642
919 7639042498431458
920 7814004559286120
921 7992965322378782
922 8175839968076266
923 8362889469814678
924 8554025920078132
925 8749520264546111
926 8949283458472602
927 9153594751455573
928 9362363956903526
929 9575881011396743
930 9794052498214544
931 10017179403374199
932 10245167190366768
933 10478326104447375
934 10716560490022624
935 10960192433315631
936 11209122912114753
937 11463686255569304
938 11723782358002272
939 11989755871129574
940 12261505612786872
941 12539389354197116
942 12823302418963718
943 13113616143303436
944 13410224826213460
945 13713511310171568
946 14023368884461560
947 14340194927330320
948 14663879118239672
949 14994833865214811
950 15332947909297650
951 15678646482003753
952 16031817410084792
953 16392902029957407
954 16761784459257630
955 17138922686808274
956 17524200010283336
957 17918088707944808
958 18320471293020994
959 18731837886872563
960 19152067215036050
961 19581667849078253
962 20020517851612002
963 20469141714610143
964 20927416886519540
965 21395887628206070
966 21874427548383704
967 22363601349687201
968 22863282180167571
969 23374052477531574
970 23895784993935804
971 24429084069321797
972 24973818596707536
973 25530615564349813
974 26099343660366174
975 26680649626574962
976 27274402029489916
977 27881271876762874
978 28501123896768098
979 29134654189886824
980 29781727597659482
981 30443062219348617
982 31118523115068300
983 31808855268270415
984 32513919970661742
985 33234490006707840
986 33970427172437460
987 34722528748202347
988 35490657165254906
989 36275639489102168
990 37077334511379684
991 37896600098862440
992 38733296023372162
993 39588307424553320
994 40461495215427096
995 41353777534475350
996 42265011854095440
997 43196150438167685
998 44147052313850478
999 45118700105509083
1000 46110954590688360