0 1
1 1
2 3
3 5
4 9
5 11
6 20
7 26
8 36
9 48
10 64
11 80
12 106
13 128
14 160
15 195
16 238
17 281
18 340
19 397
20 467
21 544
22 633
23 724
24 838
25 950
26 1083
27 1226
28 1385
29 1550
30 1745
31 1942
32 2165
33 2402
34 2663
35 2933
36 3242
37 3555
38 3902
39 4270
40 4667
41 5079
42 5539
43 6007
44 6518
45 7055
46 7631
47 8227
48 8880
49 9547
50 10266
51 11020
52 11820
53 12646
54 13542
55 14457
56 15435
57 16455
58 17531
59 18642
60 19833
61 21051
62 22343
63 23686
64 25096
65 26548
66 28095
67 29676
68 31342
69 33070
70 34876
71 36735
72 38701
73 40709
74 42817
75 44997
76 47268
77 49601
78 52056
79 54564
80 57184
81 59889
82 62698
83 65580
84 68600
85 71682
86 74893
87 78201
88 81626
89 85137
90 88802
91 92542
92 96425
93 100418
94 104545
95 108770
96 113167
97 117650
98 122293
99 127062
100 131979
101 137009
102 142229
103 147548
104 153045
105 158682
106 164486
107 170417
108 176556
109 182809
110 189258
111 195865
112 202655
113 209587
114 216749
115 224039
116 231545
117 239225
118 247107
119 255149
120 263440
121 271876
122 280548
123 289412
124 298498
125 307760
126 317295
127 326991
128 336943
129 347107
130 357513
131 368115
132 379011
133 390085
134 401439
135 413024
136 424873
137 436936
138 449317
139 461896
140 474776
141 487909
142 501328
143 514981
144 528977
145 543189
146 557728
147 572541
148 587662
149 603039
150 618784
151 634767
152 651100
153 667729
154 684692
155 701932
156 719567
157 737460
158 755729
159 774319
160 793266
161 812514
162 832184
163 852134
164 872487
165 893184
166 914266
167 935672
168 957527
169 979686
170 1002275
171 1025235
172 1048605
173 1072323
174 1096521
175 1121046
176 1146030
177 1171410
178 1197228
179 1223421
180 1250122
181 1277176
182 1304718
183 1332683
184 1361115
185 1389947
186 1419320
187 1449071
188 1479339
189 1510059
190 1541275
191 1572920
192 1605136
193 1637756
194 1670926
195 1704576
196 1738753
197 1773386
198 1808623
199 1844293
200 1880543
201 1917304
202 1954623
203 1992427
204 2030869
205 2069771
206 2109288
207 2149346
208 2189993
209 2231156
210 2272991
211 2315317
212 2358290
213 2401835
214 2446004
215 2490719
216 2536142
217 2582085
218 2628710
219 2675941
220 2723828
221 2772294
222 2821504
223 2871265
224 2921744
225 2972861
226 3024671
227 3077092
228 3130293
229 3184078
230 3238617
231 3293830
232 3349770
233 3406354
234 3463758
235 3521778
236 3580590
237 3640110
238 3700394
239 3761358
240 3823179
241 3885651
242 3948953
243 4012999
244 4077847
245 4143409
246 4209870
247 4277016
248 4345030
249 4413826
250 4483462
251 4553850
252 4625176
253 4697222
254 4770178
255 4843953
256 4918608
257 4994051
258 5070474
259 5147655
260 5225785
261 5304774
262 5384683
263 5465418
264 5547176
265 5629728
266 5713273
267 5797716
268 5883119
269 5969388
270 6056723
271 6144892
272 6234095
273 6324236
274 6415381
275 6507431
276 6600592
277 6694625
278 6789736
279 6885828
280 6982965
281 7081049
282 7180289
283 7280441
284 7381716
285 7484013
286 7587401
287 7691777
288 7797354
289 7903885
290 8011584
291 8120350
292 8230250
293 8341180
294 8453360
295 8566535
296 8680925
297 8796425
298 8913105
299 9030860
300 9149911
301 9270001
302 9391353
303 9513860
304 9637594
305 9762446
306 9888645
307 10015926
308 10144516
309 10274308
310 10405374
311 10537605
312 10671231
313 10805983
314 10942095
315 11079455
316 11218138
317 11358031
318 11499370
319 11641882
320 11785802
321 11931019
322 12077608
323 12225454
324 12374798
325 12525360
326 12677383
327 12830751
328 12985540
329 13141635
330 13299280
331 13458192
332 13618615
333 13780432
334 13943723
335 14108368
336 14274617
337 14442180
338 14611307
339 14781880
340 14953977
341 15127479
342 15302639
343 15479162
344 15657303
345 15836940
346 16018156
347 16200827
348 16385210
349 16571007
350 16758476
351 16947495
352 17138145
353 17330301
354 17524227
355 17719617
356 17916735
357 18115455
358 18315861
359 18517827
360 18721618
361 18926926
362 19134018
363 19342766
364 19553256
365 19765358
366 19979345
367 20194901
368 20412297
369 20631405
370 20852311
371 21074885
372 21299401
373 21525539
374 21753577
375 21983382
376 22215043
377 22448426
378 22683811
379 22920874
380 23159894
381 23400739
382 23643498
383 23888035
384 24134635
385 24382967
386 24633318
387 24885551
388 25139756
389 25395797
390 25653962
391 25913917
392 26175950
393 26439923
394 26705930
395 26973830
396 27243917
397 27515850
398 27789923
399 28065997
400 28344164
401 28624284
402 28906654
403 29190928
404 29477405
405 29765942
406 30056636
407 30349342
408 30644361
409 30941344
410 31240593
411 31541965
412 31845555
413 32151217
414 32459259
415 32769324
416 33081720
417 33396300
418 33713162
419 34032159
420 34353600
421 34677126
422 35003048
423 35331217
424 35661733
425 35994445
426 36329670
427 36667041
428 37006873
429 37349017
430 37693573
431 38040390
432 38389786
433 38741390
434 39095524
435 39452034
436 39811023
437 40172336
438 40536297
439 40902531
440 41271361
441 41642634
442 42016453
443 42392661
444 42771587
445 43152849
446 43536778
447 43923216
448 44312267
449 44703774
450 45098069
451 45494767
452 45894200
453 46296209
454 46700902
455 47108117
456 47518192
457 47930735
458 48346084
459 48764079
460 49184826
461 49608164
462 50034434
463 50463239
464 50894922
465 51329319
466 51766541
467 52206422
468 52649307
469 53094796
470 53543235
471 53994460
472 54448580
473 54905428
474 55365356
475 55827956
476 56293580
477 56762060
478 57233508
479 57707756
480 58185157
481 58665301
482 59148543
483 59634713
484 60123925
485 60616007
486 61111320
487 61609446
488 62110744
489 62615044
490 63122460
491 63632820
492 64146486
493 64663036
494 65182836
495 65705711
496 66231778
497 66760861
498 67293328
499 67828753
500 68367503
501 68909404
502 69454573
503 70002832
504 70554554
505 71109306
506 71667463
507 72228846
508 72793573
509 73361466
510 73932901
511 74507442
512 75085465
513 75666790
514 76251539
515 76839529
516 77431142
517 78025935
518 78624290
519 79226026
520 79831263
521 80439819
522 81052079
523 81667595
524 82286754
525 82909371
526 83535571
527 84165167
528 84798548
529 85435263
530 86075702
531 86719680
532 87367320
533 88018434
534 88673418
535 89331813
536 89994015
537 90659835
538 91329399
539 92002518
540 92679589
541 93360151
542 94044603
543 94732754
544 95424732
545 96120344
546 96819995
547 97523216
548 98230410
549 98941386
550 99656272
551 100374875
552 101097601
553 101823977
554 102554413
555 103288713
556 104027008
557 104769101
558 105515404
559 106265440
560 107019620
561 107777749
562 108539958
563 109306048
564 110076436
565 110850638
566 111629073
567 112411541
568 113198174
569 113988773
570 114783758
571 115582642
572 116385845
573 117193166
574 118004741
575 118820366
576 119640467
577 120464550
578 121293041
579 122125738
580 122962775
581 123803949
582 124649689
583 125499496
584 126353801
585 127212398
586 128075426
587 128942677
588 129814584
589 130690645
590 131571294
591 132456325
592 133345875
593 134239735
594 135138345
595 136041195
596 136948725
597 137860725
598 138777335
599 139698345
600 140624196
601 141554376
602 142489328
603 143428840
604 144373054
605 145321756
606 146275395
607 147233451
608 148196371
609 149163943
610 150136309
611 151113255
612 152095231
613 153081713
614 154073155
615 155069340
616 156070413
617 157076156
618 158087025
619 159102492
620 160123012
621 161148369
622 162178708
623 163213809
624 164254133
625 165299145
626 166349308
627 167404401
628 168464570
629 169529595
630 170599940
631 171675067
632 172755440
633 173840837
634 174931408
635 176026928
636 177127867
637 178233680
638 179344837
639 180461115
640 181582662
641 182709254
642 183841364
643 184978442
644 186120963
645 187268700
646 188421806
647 189580052
648 190743915
649 191912842
650 193087311
651 194267095
652 195452345
653 196642831
654 197839037
655 199040402
656 200247410
657 201459830
658 202677816
659 203901137
660 205130278
661 206364676
662 207604818
663 208850471
664 210101791
665 211358543
666 212621220
667 213889251
668 215163127
669 216442615
670 217727871
671 219018660
672 220315476
673 221617744
674 222925962
675 224239892
676 225559693
677 226885126
678 228216691
679 229553809
680 230896979
681 232245964
682 233600923
683 234961615
684 236328545
685 237701127
686 239079868
687 240464526
688 241855261
689 243251832
690 244654747
691 246063417
692 247478350
693 248899303
694 250326440
695 251759515
696 253199042
697 254644425
698 256096178
699 257554057
700 259018224
701 260488434
702 261965204
703 263447933
704 264937140
705 266432577
706 267934411
707 269442392
708 270957041
709 272477754
710 274005053
711 275538690
712 277078830
713 278625222
714 280178394
715 281737734
716 283303770
717 284876250
718 286455342
719 288040794
720 289633135
721 291231751
722 292837173
723 294449147
724 296067843
725 297693005
726 299325170
727 300963716
728 302609178
729 304261302
730 305920258
731 307585790
732 309258436
733 310937570
734 312623734
735 314316669
736 316016548
737 317723111
738 319436902
739 321157291
740 322884821
741 324619234
742 326360703
743 328108966
744 329864572
745 331626884
746 333396453
747 335173016
748 336956747
749 338747384
750 340545479
751 342350392
752 344162675
753 345982064
754 347808737
755 349642427
756 351483692
757 353331885
758 355187564
759 357050464
760 358920761
761 360798189
762 362683309
763 364575469
764 366475232
765 368382329
766 370296941
767 372218797
768 374148462
769 376085281
770 378029820
771 379981810
772 381941430
773 383908408
774 385883316
775 387865491
776 389855505
777 391853085
778 393858413
779 395871216
780 397892067
781 399920301
782 401956493
783 404000368
784 406052110
785 408111442
786 410178945
787 412253946
788 414337024
789 416427904
790 418526770
791 420633345
792 422748211
793 424870691
794 427001371
795 429139971
796 431286678
797 433441211
798 435604158
799 437774838
800 439953838
801 442140879
802 444336148
803 446539362
804 448751114
805 450970716
806 453198763
807 455434971
808 457679528
809 459932151
810 462193436
811 464462692
812 466740515
813 469026620
814 471321199
815 473623964
816 475935517
817 478255160
818 480583495
819 482920236
820 485265573
821 487619219
822 489981779
823 492352550
824 494732139
825 497120256
826 499517096
827 501922367
828 504336678
829 506759323
830 509190912
831 511631155
832 514080245
833 516537889
834 519004703
835 521479973
836 523964315
837 526457435
838 528959529
839 531470303
840 533990374
841 536519026
842 539056878
843 541603634
844 544159492
845 546724154
846 549298245
847 551881041
848 554473165
849 557074321
850 559684707
851 562304025
852 564932901
853 567570607
854 570217773
855 572874098
856 575539783
857 578214526
858 580898959
859 583592350
860 586295330
861 589007599
862 591729358
863 594460303
864 597201071
865 599950923
866 602710498
867 605479491
868 608258104
869 611046033
870 613843918
871 616651017
872 619467970
873 622294471
874 625130726
875 627976426
876 630832217
877 633697350
878 636572471
879 639457273
880 642351960
881 645256224
882 648170714
883 651094676
884 654028761
885 656972658
886 659926576
887 662890202
888 665864189
889 668847780
890 671841629
891 674845425
892 677859375
893 680883165
894 683917455
895 686961480
896 690015900
897 693080400
898 696155190
899 699239955
900 702335356
901 705440626
902 708556428
903 711682445
904 714818889
905 717965441
906 721122770
907 724290101
908 727468101
909 730656453
910 733855369
911 737064530
912 740284606
913 743514818
914 746755840
915 750007350
916 753269563
917 756542156
918 759825805
919 763119727
920 766424597
921 769740094
922 773066433
923 776403289
924 779751343
925 783109805
926 786479358
927 789859676
928 793250975
929 796652930
930 800066225
931 803490067
932 806925140
933 810371117
934 813828218
935 817296113
936 820775492
937 824265555
938 827766992
939 831279475
940 834803222
941 838337904
942 841884214
943 845441347
944 849009998
945 852589835
946 856181081
947 859783402
948 863397495
949 867022552
950 870659271
951 874307320
952 877966920
953 881637736
954 885320472
955 889014312
956 892719960
957 896437080
958 900165896
959 903906072
960 907658313
961 911421801
962 915197243
963 918984301
964 922783201
965 926593603
966 930416220
967 934250226
968 938096332
969 941954200
970 945824056
971 949705560
972 953599426
973 957504824
974 961422472
975 965352027
976 969293718
977 973247201
978 977213196
979 981190869
980 985180939
981 989183064
982 993197473
983 997223820
984 1001262830
985 1005313662
986 1009377043
987 1013452626
988 1017540641
989 1021640742
990 1025753657
991 1029878542
992 1034016125
993 1038166058
994 1042328575
995 1046503325
996 1050691042
997 1054890875
998 1059103558
999 1063328742
1000 1067566659