-1 1
0 1
1 0
2 1
3 1
4 1
5 1
6 1
7 2
8 2
9 2
10 2
11 3
12 3
13 3
14 4
15 5
16 5
17 5
18 6
19 7
20 8
21 8
22 10
23 12
24 12
25 13
26 15
27 17
28 18
29 19
30 22
31 25
32 27
33 28
34 32
35 36
36 38
37 41
38 46
39 51
40 54
41 58
42 64
43 71
44 76
45 81
46 89
47 99
48 105
49 112
50 123
51 134
52 143
53 153
54 167
55 182
56 194
57 207
58 225
59 244
60 260
61 277
62 301
63 325
64 346
65 369
66 398
67 429
68 458
69 487
70 524
71 565
72 600
73 638
74 686
75 735
76 782
77 832
78 891
79 954
80 1014
81 1076
82 1151
83 1231
84 1306
85 1386
86 1480
87 1579
88 1674
89 1776
90 1892
91 2016
92 2137
93 2263
94 2409
95 2564
96 2713
97 2872
98 3053
99 3243
100 3431
101 3630
102 3852
103 4088
104 4322
105 4567
106 4842
107 5133
108 5421
109 5725
110 6064
111 6419
112 6776
113 7152
114 7566
115 8001
116 8441
117 8902
118 9408
119 9942
120 10478
121 11043
122 11662
123 12309
124 12967
125 13658
126 14408
127 15197
128 15999
129 16839
130 17750
131 18707
132 19680
133 20702
134 21806
135 22962
136 24142
137 25383
138 26713
139 28109
140 29540
141 31035
142 32641
143 34325
144 36046
145 37852
146 39785
147 41805
148 43880
149 46055
150 48371
151 50797
152 53292
153 55899
154 58676
155 61582
156 64569
157 67695
158 71018
159 74488
160 78064
161 81803
162 85765
163 89907
164 94179
165 98638
166 103360
167 108296
168 113382
169 118697
170 124316
171 130177
172 136232
173 142554
174 149221
175 156183
176 163374
177 170874
178 178780
179 187031
180 195552
181 204443
182 213804
183 223563
184 233650
185 244171
186 255229
187 266758
188 278683
189 291106
190 304156
191 317761
192 331824
193 346480
194 361860
195 377876
196 394449
197 411713
198 429804
199 448647
200 468146
201 488441
202 509702
203 531836
204 554738
205 578576
206 603528
207 629486
208 656355
209 684317
210 713548
211 743960
212 775446
213 808185
214 842402
215 877990
216 914820
217 953120
218 993120
219 1034695
220 1077740
221 1122488
222 1169178
223 1217708
224 1267950
225 1320152
226 1374600
227 1431177
228 1489738
229 1550581
230 1614002
231 1679870
232 1748062
233 1818887
234 1892662
235 1969274
236 2048588
237 2130928
238 2216668
239 2305683
240 2397810
241 2493445
242 2592981
243 2696270
244 2803190
245 2914145
246 3029555
247 3149307
248 3273252
249 3401827
250 3535524
251 3674211
252 3817732
253 3966589
254 4121311
255 4281752
256 4447781
257 4619946
258 4798800
259 4984236
260 5176120
261 5375022
262 5581593
263 5795716
264 6017234
265 6246824
266 6485176
267 6732162
268 6987676
269 7252435
270 7527178
271 7811832
272 8106276
273 8411283
274 8727708
275 9055471
276 9394443
277 9745521
278 10109623
279 10486660
280 10876568
281 11280311
282 11698873
283 12132237
284 12580343
285 13044218
286 13524998
287 14022678
288 14537186
289 15069719
290 15621498
291 16192516
292 16782805
293 17393639
294 18026341
295 18681001
296 19357658
297 20057697
298 20782630
299 21532563
300 22307565
301 23109218
302 23939153
303 24797512
304 25684470
305 26601747
306 27551112
307 28532830
308 29547124
309 30595848
310 31681022
311 32802963
312 33961932
313 35160057
314 36399520
315 37680696
316 39004018
317 40371788
318 41786378
319 43248349
320 44758194
321 46318432
322 47931748
323 49598790
324 51320157
325 53098685
326 54937311
327 56836789
328 58797926
329 60823835
330 62917704
331 65080529
332 67313262
333 69619285
334 72002208
335 74463182
336 77003300
337 79626396
338 82336408
339 85134656
340 88022556
341 91004282
342 94084148
343 97263810
344 100544888
345 103931954
346 107429866
347 111040526
348 114765791
349 118610817
350 122580916
351 126678265
352 130905148
353 135267213
354 139770280
355 144416984
356 149209952
357 154155364
358 159259759
359 164526153
360 169957516
361 175560817
362 181343222
363 187308153
364 193459190
365 199803964
366 206350342
367 213102403
368 220064189
369 227244105
370 234650968
371 242289384
372 250163981
373 258284153
374 266659588
375 275295525
376 284197380
377 293375502
378 302840528
379 312598585
380 322655824
381 333023607
382 343713850
383 354733467
384 366089411
385 377794407
386 389861553
387 402298657
388 415113814
389 428321007
390 441934658
391 455963797
392 470417550
393 485311335
394 500661233
395 516477428
396 532770224
397 549556817
398 566854926
399 584676018
400 603031927
401 621941611
402 641424586
403 661493989
404 682163162
405 703452981
406 725385188
407 747974572
408 771236106
409 795193085
410 819869454
411 845281818
412 871447298
413 898391544
414 926140950
415 954714436
416 984131205
417 1014419549
418 1045608844
419 1077720291
420 1110775452
421 1144805803
422 1179843724
423 1215912978
424 1253038016
425 1291253567
426 1330595321
427 1371090192
428 1412765590
429 1455659782
430 1499812448
431 1545253706
432 1592014215
433 1640136525
434 1689664384
435 1740631456
436 1793072400
437 1847034109
438 1902564837
439 1959702565
440 2018485980
441 2078966853
442 2141198728
443 2205224001
444 2271085932
445 2338841942
446 2408551084
447 2480260690
448 2554019390
449 2629890544
450 2707939266
451 2788218724
452 2870783186
453 2955702513
454 3043048904
455 3132881634
456 3225261176
457 3320265021
458 3417972756
459 3518450424
460 3621765832
461 3728004413
462 3837253956
463 3949588396
464 4065083237
465 4183832712
466 4305934031
467 4431469485
468 4560523118
469 4693199262
470 4829605094
471 4969832158
472 5113974372
473 5262146794
474 5414467586
475 5571038951
476 5731965344
477 5897373591
478 6067394425
479 6242141418
480 6421730612
481 6606302335
482 6796000682
483 6990951752
484 7191284977
485 7397155006
486 7608720632
487 7826122391
488 8049503900
489 8279035644
490 8514893138
491 8757232271
492 9006212445
493 9262022026
494 9524854418
495 9794882508
496 10072283597
497 10357265283
498 10650040596
499 10950801753
500 11259745320
501 11577099968
502 11903100952
503 12237961253
504 12581898628
505 12935165604
506 13298021242
507 13670701422
508 14053447977
509 14446538951
510 14850259660
511 15264871851
512 15690643202
513 16127879938
514 16576896803
515 17037983420
516 17511436032
517 17997592412
518 18496799028
519 19009376256
520 19535652418
521 20075999332
522 20630798346
523 21200404343
524 21785180379
525 22385535624
526 23001890446
527 23634637079
528 24284176730
529 24950960400
530 25635450572
531 26338080576
532 27059294428
533 27799588267
534 28559470844
535 29339421478
536 30139930486
537 30961543633
538 31804821209
539 32670292335
540 33558498332
541 34470040147
542 35405533896
543 36365563498
544 37350727062
545 38361685393
546 39399115824
547 40463663321
548 41555987692
549 42676815325
550 43826891590
551 45006927726
552 46217651244
553 47459861434
554 48734377421
555 50041983172
556 51383481621
557 52759750997
558 54171691306
559 55620167415
560 57106064004
561 58630345978
562 60194002936
563 61797987555
564 63443274409
565 65130924258
566 66862023982
567 68637622672
568 70458794440
569 72326704223
570 74242545460
571 76207474015
572 78222672332
573 80289419362
574 82409026372
575 84582765337
576 86811937408
577 89097947648
578 91442235219
579 93846199463
580 96311272872
581 98838997378
582 101430952336
583 104088677780
584 106813748994
585 109607857902
586 112472738384
587 115410083555
588 118421625291
589 121509220766
590 124674771848
591 127920139431
592 131247228042
593 134658074601
594 138154764818
595 141739344522
596 145413906246
597 149180683496
598 153041964343
599 156999995966
600 161057076664
601 165215656322
602 169478243136
603 173847304615
604 178325365751
605 182915111697
606 187619291342
607 192440614774
608 197381853594
609 202445950334
610 207635918364
611 212954731781
612 218405432204
613 223991244711
614 229715470464
615 235581372405
616 241592288768
617 247751752201
618 254063378300
619 260530747313
620 267157520548
621 273947566541
622 280904846005
623 288033284688
624 295336896915
625 302819919909
626 310486689736
627 318341509756
628 326388781932
629 334633144370
630 343079343160
631 351732095950
632 360596226532
633 369676810929
634 378979044510
635 388508095880
636 398269249778
637 408268061873
638 418510216330
639 429001374378
640 439747325786
641 450754148162
642 462028059130
643 473575259539
644 485402089026
645 497515194608
646 509921377856
647 522627426979
648 535640281786
649 548967212490
650 562615655797
651 576593041028
652 590906965021
653 605565375715
654 620576402656
655 635948176686
656 651689009491
657 667807588321
658 684312800128
659 701213539051
660 718518896828
661 736238368573
662 754381665083
663 772958513111
664 791978857026
665 811453070718
666 831391762940
667 851805570403
668 872705365268
669 894102479054
670 916008501216
671 938435058522
672 961394034374
673 984897806071
674 1008959029492
675 1033590410375
676 1058804936752
677 1084616122809
678 1111037786148
679 1138083810694
680 1165768385664
681 1194106263765
682 1223112530102
683 1252802349833
684 1283191221012
685 1314295247208
686 1346130891440
687 1378714714541
688 1412063642344
689 1446195246977
690 1481127491494
691 1516878459036
692 1553466628042
693 1590911168910
694 1629231680160
695 1668447899882
696 1708579996612
697 1749648883145
698 1791675935001
699 1834682691765
700 1878691164534
701 1923724159053
702 1969804984477
703 2016957143736
704 2065204650238
705 2114572369245
706 2165085716077
707 2216770327158
708 2269652394684
709 2323759026677
710 2379117926382
711 2435757051259
712 2493704966348
713 2552991215860
714 2613645990932
715 2675699776396
716 2739183715169
717 2804130000153
718 2870571530318
719 2938541535882
720 3008073962764
721 3079203886318
722 3151967145833
723 3226399956228
724 3302539314112
725 3380423424239
726 3460091321469
727 3541582468441
728 3624937174102
729 3710197044074
730 3797404588642
731 3886602796562
732 3977835576762
733 4071148232707
734 4166587047064
735 4264198840050
736 4364031435107
737 4466134149299
738 4570557362710
739 4677352061195
740 4786570317420
741 4898265806992
742 5012493363344
743 5129308493418
744 5248767884542
745 5370929948942
746 5495854351626
747 5623601509029
748 5754233123500
749 5887812745458
750 6024405285116
751 6164076493074
752 6306893512345
753 6452925470782
754 6602242975411
755 6754917563242
756 6911022283238
757 7070632319793
758 7233824458136
759 7400676515452
760 7571267954004
761 7745680526051
762 7923997719975
763 8106304171788
764 8292686298724
765 8483232977838
766 8678034973508
767 8877184315374
768 9080774965599
769 9288903533849
770 9501668671592
771 9719170428377
772 9941510954889
773 10168795241775
774 10401130493464
775 10638625461885
776 10881391173054
777 11129541705277
778 11383193540792
779 11642464863010
780 11907476321596
781 12178351850994
782 12455217986336
783 12738203136063
784 13027438387201
785 13323058352651
786 13625200463385
787 13934004215847
788 14249612005373
789 14572170017086
790 14901827494292
791 15238735945170
792 15583050019564
793 15934928446735
794 16294533263255
795 16662028992544
796 17037583567896
797 17421369302547
798 17813562092096
799 18214340565652
800 18623887041021
801 19042388545482
802 19470035990790
803 19907023279448
804 20353548310072
805 20809814049980
806 21276027666943
807 21752399604719
808 22239144640208
809 22736482995462
810 23244639439258
811 23763842331883
812 24294324720314
813 24836325506276
814 25390088518960
815 25955861509813
816 26533897304176
817 27124455029879
818 27727799140761
819 28344198378074
820 28973926981696
821 29617265962864
822 30274502095940
823 30945926844955
824 31631837618462
825 32332539107822
826 33048342245256
827 33779563076339
828 34526524079414
829 35289555571708
830 36068994614708
831 36865183848897
832 37678472881138
833 38509219742726
834 39357789758807
835 40224554345164
836 41109892446664
837 42014192068867
838 42937849111576
839 43881266105838
840 44844853725552
841 45829032397618
842 46834231076608
843 47860885940700
844 48909441981336
845 49980354672359
846 51074088706530
847 52191116649150
848 53331920586682
849 54496993881060
850 55686839865624
851 56901970433705
852 58142907771813
853 59410186201630
854 60704350813192
855 62025956008458
856 63375567322128
857 64753763334404
858 66161134260682
859 67598280449341
860 69065814272096
861 70564362132156
862 72094563011376
863 73657066896555
864 75252536765639
865 76881650697832
866 78545100350838
867 80243589338763
868 81977835319234
869 83748572183880
870 85556548489966
871 87402525788078
872 89287280789168
873 91211607665935
874 93176316436478
875 95182231215468
876 97230192491307
877 99321059542092
878 101455708745911
879 103635031778249
880 105859938004368
881 108131356990340
882 110450236762238
883 112817541950096
884 115234256274134
885 117701385180696
886 120219954051697
887 122791006265217
888 125415605807042
889 128094840039701
890 130829817831008
891 133621667557701
892 136471539849716
893 139380610467480
894 142350078378110
895 145381163700613
896 148475110558816
897 151633190103555
898 154856698534062
899 158146954954383
900 161505304370586
901 164933120863920
902 168431805526990
903 172002784259016
904 175647510914446
905 179367470603829
906 183164177572745
907 187039172935815
908 190994027952482
909 195030347492208
910 199149767857348
911 203353954421715
912 207644605071310
913 212023453844413
914 216492268662276
915 221052848903768
916 225707029020612
917 230456682324470
918 235303718659172
919 240250081910523
920 245297753768646
921 250448757706190
922 255705156589977
923 261069050090177
924 266542578634044
925 272127927581823
926 277827324743972
927 283643037722902
928 289577378065923
929 295632705615120
930 301811425961970
931 308115987722451
932 314548886862979
933 321112671267187
934 327809938130918
935 334643331130885
936 341615544969628
937 348729330172555
938 355987490381900
939 363392879456994
940 370948406250100
941 378657039603135
942 386521805581000
943 394545784502370
944 402732115917080
945 411084003854928
946 419604713996336
947 428297570594617
948 437165961705742
949 446213344700581
950 455443243333978
951 464859244596736
952 474465004211148
953 484264252378567
954 494260790786180
955 504458489390760
956 514861292150435
957 525473223060698
958 536298383102168
959 547340946912280
960 558605168807850
961 570095389127292
962 581816031073146
963 593771597316033
964 605966676324916
965 618405948981862
966 631094185367104
967 644036241296491
968 657237064926598
969 670701703705262
970 684435301099572
971 698443093020657
972 712730414767256
973 727302708326886
974 742165519002091
975 757324491770621
976 772785378583702
977 788554045988822
978 804636471701327
979 821038740903910
980 837767053868272
981 854827733963323
982 872227224179135
983 889972083315008
984 908068993991992
985 926524771069781
986 945346358070600
987 964540823310528
988 984115368324562
989 1004077336656617
990 1024434210241216
991 1045193605481070
992 1066363282049973
993 1087951152133295
994 1109965276768824
995 1132413861820708
996 1155305267237030
997 1178648016760756
998 1202450794181789
999 1226722439264389
1000 1251471957482372