1 0
2 1
3 6
4 15
5 29
6 50
7 80
8 120
9 171
10 235
11 313
12 407
13 517
14 646
15 795
16 965
17 1158
18 1374
19 1616
20 1885
21 2182
22 2509
23 2867
24 3258
25 3682
26 4142
27 4639
28 5174
29 5748
30 6363
31 7021
32 7723
33 8470
34 9264
35 10105
36 10996
37 11939
38 12933
39 13981
40 15084
41 16244
42 17462
43 18739
44 20078
45 21478
46 22942
47 24471
48 26066
49 27730
50 29462
51 31266
52 33141
53 35090
54 37114
55 39214
56 41393
57 43650
58 45988
59 48408
60 50911
61 53499
62 56174
63 58936
64 61787
65 64729
66 67763
67 70890
68 74112
69 77430
70 80845
71 84360
72 87975
73 91692
74 95512
75 99436
76 103467
77 107605
78 111852
79 116210
80 120679
81 125261
82 129958
83 134771
84 139701
85 144750
86 149919
87 155210
88 160624
89 166162
90 171826
91 177618
92 183538
93 189588
94 195770
95 202085
96 208534
97 215119
98 221841
99 228701
100 235702
101 242844
102 250129
103 257558
104 265132
105 272854
106 280725
107 288745
108 296916
109 305241
110 313719
111 322353
112 331144
113 340094
114 349203
115 358473
116 367906
117 377503
118 387266
119 397195
120 407293
121 417560
122 427999
123 438610
124 449395
125 460355
126 471493
127 482808
128 494303
129 505979
130 517837
131 529880
132 542107
133 554521
134 567124
135 579915
136 592898
137 606073
138 619442
139 633006
140 646767
141 660725
142 674883
143 689242
144 703803
145 718567
146 733537
147 748713
148 764097
149 779691
150 795495
151 811511
152 827741
153 844185
154 860846
155 877725
156 894823
157 912142
158 929683
159 947447
160 965436
161 983651
162 1002094
163 1020766
164 1039669
165 1058804
166 1078171
167 1097774
168 1117613
169 1137689
170 1158005
171 1178561
172 1199358
173 1220399
174 1241685
175 1263216
176 1284995
177 1307023
178 1329302
179 1351832
180 1374615
181 1397653
182 1420947
183 1444498
184 1468308
185 1492378
186 1516710
187 1541304
188 1566164
189 1591289
190 1616681
191 1642342
192 1668274
193 1694476
194 1720952
195 1747702
196 1774728
197 1802031
198 1829613
199 1857474
200 1885618
201 1914044
202 1942754
203 1971750
204 2001032
205 2030604
206 2060465
207 2090618
208 2121063
209 2151803
210 2182838
211 2214170
212 2245801
213 2277731
214 2309963
215 2342497
216 2375335
217 2408479
218 2441930
219 2475689
220 2509757
221 2544137
222 2578829
223 2613836
224 2649157
225 2684796
226 2720752
227 2757028
228 2793626
229 2830545
230 2867789
231 2905358
232 2943253
233 2981477
234 3020030
235 3058914
236 3098130
237 3137680
238 3177566
239 3217788
240 3258348
241 3299247
242 3340487
243 3382069
244 3423995
245 3466266
246 3508884
247 3551849
248 3595164
249 3638830
250 3682847
251 3727219
252 3771945
253 3817027
254 3862468
255 3908267
256 3954427
257 4000949
258 4047835
259 4095086
260 4142702
261 4190687
262 4239041
263 4287765
264 4336861
265 4386330
266 4436174
267 4486395
268 4536993
269 4587970
270 4639327
271 4691066
272 4743189
273 4795696
274 4848589
275 4901870
276 4955540
277 5009600
278 5064051
279 5118896
280 5174136
281 5229771
282 5285804
283 5342235
284 5399067
285 5456301
286 5513937
287 5571978
288 5630425
289 5689279
290 5748542
291 5808215
292 5868299
293 5928797
294 5989709
295 6051036
296 6112781
297 6174945
298 6237528
299 6300533
300 6363961
301 6427813
302 6492090
303 6556795
304 6621928
305 6687491
306 6753486
307 6819913
308 6886775
309 6954072
310 7021806
311 7089978
312 7158590
313 7227644
314 7297140
315 7367080
316 7437466
317 7508298
318 7579579
319 7651309
320 7723491
321 7796125
322 7869214
323 7942757
324 8016758
325 8091216
326 8166134
327 8241514
328 8317355
329 8393661
330 8470432
331 8547669
332 8625375
333 8703550
334 8782196
335 8861314
336 8940907
337 9020974
338 9101518
339 9182540
340 9264041
341 9346023
342 9428488
343 9511436
344 9594869
345 9678789
346 9763196
347 9848093
348 9933481
349 10019361
350 10105734
351 10192602
352 10279967
353 10367829
354 10456191
355 10545053
356 10634418
357 10724286
358 10814658
359 10905537
360 10996924
361 11088820
362 11181226
363 11274145
364 11367576
365 11461523
366 11555985
367 11650966
368 11746465
369 11842485
370 11939026
371 12036091
372 12133680
373 12231796
374 12330439
375 12429611
376 12529313
377 12629547
378 12730314
379 12831616
380 12933454
381 13035829
382 13138743
383 13242197
384 13346193
385 13450732
386 13555815
387 13661445
388 13767621
389 13874346
390 13981622
391 14089449
392 14197829
393 14306763
394 14416253
395 14526300
396 14636906
397 14748072
398 14859799
399 14972090
400 15084944
401 15198364
402 15312352
403 15426907
404 15542033
405 15657730
406 15774000
407 15890844
408 16008263
409 16126260
410 16244835
411 16363990
412 16483726
413 16604045
414 16724947
415 16846436
416 16968511
417 17091174
418 17214427
419 17338272
420 17462709
421 17587739
422 17713366
423 17839589
424 17966410
425 18093831
426 18221853
427 18350477
428 18479705
429 18609539
430 18739979
431 18871027
432 19002685
433 19134954
434 19267835
435 19401330
436 19535440
437 19670167
438 19805512
439 19941476
440 20078061
441 20215268
442 20353099
443 20491555
444 20630637
445 20770348
446 20910688
447 21051658
448 21193261
449 21335497
450 21478368
451 21621876
452 21766021
453 21910805
454 22056231
455 22202298
456 22349009
457 22496364
458 22644366
459 22793016
460 22942315
461 23092264
462 23242865
463 23394120
464 23546029
465 23698595
466 23851818
467 24005700
468 24160243
469 24315447
470 24471315
471 24627848
472 24785046
473 24942912
474 25101447
475 25260653
476 25420530
477 25581080
478 25742305
479 25904206
480 26066784
481 26230041
482 26393978
483 26558597
484 26723899
485 26889886
486 27056558
487 27223918
488 27391966
489 27560705
490 27730135
491 27900258
492 28071075
493 28242588
494 28414799
495 28587708
496 28761317
497 28935628
498 29110641
499 29286359
500 29462782
501 29639913
502 29817752
503 29996300
504 30175561
505 30355534
506 30536221
507 30717624
508 30899744
509 31082582
510 31266140
511 31450419
512 31635421
513 31821147
514 32007599
515 32194777
516 32382684
517 32571321
518 32760688
519 32950789
520 33141623
521 33333193
522 33525499
523 33718544
524 33912328
525 34106853
526 34302121
527 34498133
528 34694890
529 34892393
530 35090645
531 35289646
532 35489398
533 35689903
534 35891161
535 36093175
536 36295945
537 36499473
538 36703761
539 36908809
540 37114620
541 37321195
542 37528534
543 37736640
544 37945514
545 38155157
546 38365571
547 38576757
548 38788717
549 39001452
550 39214963
551 39429252
552 39644320
553 39860169
554 40076800
555 40294214
556 40512414
557 40731399
558 40951172
559 41171735
560 41393088
561 41615233
562 41838171
563 42061904
564 42286433
565 42511760
566 42737886
567 42964812
568 43192541
569 43421072
570 43650408
571 43880550
572 44111500
573 44343259
574 44575828
575 44809209
576 45043403
577 45278411
578 45514236
579 45750878
580 45988339
581 46226620
582 46465723
583 46705649
584 46946399
585 47187975
586 47430379
587 47673611
588 47917673
589 48162567
590 48408294
591 48654855
592 48902252
593 49150487
594 49399560
595 49649473
596 49900227
597 50151824
598 50404266
599 50657553
600 50911688
601 51166671
602 51422504
603 51679188
604 51936725
605 52195116
606 52454363
607 52714467
608 52975429
609 53237251
610 53499934
611 53763480
612 54027890
613 54293166
614 54559308
615 54826319
616 55094200
617 55362952
618 55632576
619 55903074
620 56174448
621 56446698
622 56719827
623 56993835
624 57268725
625 57544497
626 57821152
627 58098693
628 58377121
629 58656437
630 58936643
631 59217739
632 59499728
633 59782610
634 60066388
635 60351062
636 60636635
637 60923107
638 61210479
639 61498754
640 61787933
641 62078017
642 62369007
643 62660905
644 62953712
645 63247431
646 63542061
647 63837605
648 64134064
649 64431440
650 64729733
651 65028945
652 65329078
653 65630134
654 65932112
655 66235016
656 66538846
657 66843603
658 67149290
659 67455907
660 67763457
661 68071939
662 68381357
663 68691710
664 69003002
665 69315232
666 69628403
667 69942515
668 70257571
669 70573572
670 70890518
671 71208413
672 71527256
673 71847049
674 72167795
675 72489493
676 72812146
677 73135755
678 73460322
679 73785847
680 74112333
681 74439780
682 74768190
683 75097565
684 75427906
685 75759214
686 76091491
687 76424738
688 76758956
689 77094147
690 77430313
691 77767455
692 78105574
693 78444671
694 78784749
695 79125808
696 79467850
697 79810876
698 80154888
699 80499887
700 80845875
701 81192852
702 81540821
703 81889783
704 82239739
705 82590690
706 82942639
707 83295586
708 83649532
709 84004480
710 84360431
711 84717386
712 85075346
713 85434314
714 85794289
715 86155274
716 86517271
717 86880280
718 87244303
719 87609341
720 87975397
721 88342470
722 88710563
723 89079678
724 89449814
725 89820975
726 90193161
727 90566373
728 90940614
729 91315884
730 91692186
731 92069519
732 92447887
733 92827289
734 93207729
735 93589206
736 93971723
737 94355280
738 94739880
739 95125524
740 95512212
741 95899947
742 96288731
743 96678563
744 97069446
745 97461382
746 97854371
747 98248415
748 98643515
749 99039673
750 99436891
751 99835169
752 100234509
753 100634913
754 101036381
755 101438916
756 101842519
757 102247191
758 102652933
759 103059747
760 103467635
761 103876598
762 104286636
763 104697753
764 105109948
765 105523224
766 105937582
767 106353023
768 106769548
769 107187160
770 107605860
771 108025648
772 108446527
773 108868497
774 109291561
775 109715719
776 110140973
777 110567325
778 110994775
779 111423326
780 111852979
781 112283734
782 112715594
783 113148560
784 113582633
785 114017815
786 114454108
787 114891511
788 115330028
789 115769659
790 116210406
791 116652270
792 117095253
793 117539356
794 117984581
795 118430928
796 118878399
797 119326997
798 119776721
799 120227574
800 120679557
801 121132671
802 121586918
803 122042299
804 122498816
805 122956470
806 123415262
807 123875195
808 124336268
809 124798484
810 125261844
811 125726350
812 126192003
813 126658804
814 127126755
815 127595857
816 128066111
817 128537520
818 129010084
819 129483804
820 129958683
821 130434722
822 130911922
823 131390284
824 131869810
825 132350502
826 132832360
827 133315386
828 133799582
829 134284949
830 134771488
831 135259201
832 135748089
833 136238154
834 136729397
835 137221819
836 137715422
837 138210208
838 138706177
839 139203331
840 139701672
841 140201201
842 140701919
843 141203828
844 141706929
845 142211223
846 142716713
847 143223399
848 143731283
849 144240366
850 144750650
851 145262136
852 145774826
853 146288720
854 146803821
855 147320129
856 147837646
857 148356375
858 148876315
859 149397468
860 149919836
861 150443421
862 150968223
863 151494244
864 152021486
865 152549950
866 153079636
867 153610548
868 154142686
869 154676051
870 155210645
871 155746470
872 156283526
873 156821815
874 157361340
875 157902100
876 158444097
877 158987334
878 159531810
879 160077529
880 160624490
881 161172696
882 161722148
883 162272847
884 162824795
885 163377994
886 163932443
887 164488146
888 165045103
889 165603316
890 166162786
891 166723515
892 167285504
893 167848754
894 168413268
895 168979045
896 169546089
897 170114399
898 170683978
899 171254827
900 171826947
901 172400340
902 172975008
903 173550951
904 174128171
905 174706669
906 175286447
907 175867507
908 176449849
909 177033476
910 177618388
911 178204586
912 178792074
913 179380851
914 179970919
915 180562279
916 181154934
917 181748884
918 182344131
919 182940676
920 183538521
921 184137667
922 184738116
923 185339868
924 185942926
925 186547290
926 187152963
927 187759945
928 188368238
929 188977843
930 189588763
931 190200997
932 190814548
933 191429417
934 192045606
935 192663116
936 193281947
937 193902103
938 194523584
939 195146391
940 195770526
941 196395990
942 197022785
943 197650913
944 198280374
945 198911170
946 199543302
947 200176773
948 200811582
949 201447733
950 202085225
951 202724061
952 203364242
953 204005769
954 204648644
955 205292868
956 205938442
957 206585369
958 207233649
959 207883284
960 208534275
961 209186623
962 209840331
963 210495399
964 211151829
965 211809623
966 212468781
967 213129305
968 213791197
969 214454458
970 215119089
971 215785092
972 216452468
973 217121218
974 217791345
975 218462849
976 219135732
977 219809996
978 220485641
979 221162669
980 221841081
981 222520880
982 223202066
983 223884640
984 224568605
985 225253962
986 225940711
987 226628855
988 227318395
989 228009332
990 228701667
991 229395403
992 230090540
993 230787080
994 231485024
995 232184374
996 232885131
997 233587297
998 234290873
999 234995860
1000 2357022607