0 1
1 1
2 1
3 2
4 2
5 3
6 3
7 5
8 5
9 6
10 8
11 9
12 9
13 13
14 14
15 15
16 19
17 21
18 22
19 28
20 30
21 32
22 39
23 42
24 44
25 54
26 58
27 61
28 72
29 77
30 82
31 96
32 102
33 108
34 124
35 133
36 141
37 160
38 171
39 180
40 203
41 218
42 230
43 256
44 273
45 289
46 320
47 342
48 361
49 395
50 423
51 447
52 486
53 520
54 548
55 594
56 635
57 669
58 721
59 769
60 811
61 871
62 928
63 978
64 1044
65 1114
66 1174
67 1249
68 1329
69 1398
70 1486
71 1582
72 1662
73 1761
74 1869
75 1965
76 2078
77 2206
78 2316
79 2441
80 2589
81 2718
82 2859
83 3031
84 3177
85 3339
86 3535
87 3704
88 3884
89 4107
90 4303
91 4509
92 4761
93 4985
94 5213
95 5504
96 5758
97 6016
98 6343
99 6630
100 6922
101 7296
102 7619
103 7946
104 8361
105 8733
106 9100
107 9571
108 9987
109 10394
110 10922
111 11395
112 11850
113 12445
114 12970
115 13484
116 14145
117 14736
118 15307
119 16046
120 16709
121 17350
122 18169
123 18911
124 19617
125 20537
126 21365
127 22153
128 23168
129 24090
130 24967
131 26099
132 27121
133 28097
134 29340
135 30484
136 31566
137 32945
138 34208
139 35405
140 36927
141 38333
142 39655
143 41338
144 42883
145 44352
146 46201
147 47915
148 49533
149 51568
150 53461
151 55251
152 57478
153 59569
154 61535
155 63991
156 66291
157 68461
158 71143
159 73672
160 76062
161 79010
162 81783
163 84413
164 87624
165 90679
166 93566
167 97084
168 100428
169 103594
170 107432
171 111105
172 114570
173 118762
174 122771
175 126581
176 131144
177 135534
178 139698
179 144667
180 149462
181 154025
182 159424
183 164662
184 169637
185 175525
186 181233
187 186669
188 193054
189 199275
190 205208
191 212153
192 218919
193 225388
194 232904
195 240283
196 247331
197 255489
198 263499
199 271167
200 280000
201 288713
202 297049
203 306623
204 316064
205 325140
206 335493
207 345739
208 355585
209 366781
210 377890
211 388589
212 400677
213 412716
214 424301
215 437376
216 450406
217 462971
218 477068
219 491160
220 504773
221 519998
222 535222
223 549961
224 566354
225 582821
226 598765
227 616443
228 634206
229 651433
230 670471
231 689661
232 708266
233 728769
234 749440
235 769542
236 791595
237 813887
238 835569
239 859282
240 883294
241 906696
242 932170
243 958026
244 983224
245 1010617
246 1038438
247 1065592
248 1094991
249 1124901
250 1154133
251 1185716
252 1217860
253 1249318
254 1283168
255 1317721
256 1351552
257 1387870
258 1424959
259 1461314
260 1500236
261 1540066
262 1579117
263 1620830
264 1663522
265 1705472
266 1750147
267 1795939
268 1840948
269 1888770
270 1937837
271 1986139
272 2037303
273 2089878
274 2141633
275 2196389
276 2252685
277 2308161
278 2366689
279 2426930
280 2486352
281 2548943
282 2613379
283 2677009
284 2743839
285 2812762
286 2880866
287 2952273
288 3025926
289 3098760
290 3174984
291 3253705
292 3331576
293 3412948
294 3496982
295 3580227
296 3667040
297 3756777
298 3845694
299 3938267
300 4034017
301 4129005
302 4227688
303 4329845
304 4431198
305 4536392
306 4645323
307 4753494
308 4865551
309 4981647
310 5097012
311 5216398
312 5340088
313 5463102
314 5590159
315 5721931
316 5853043
317 5988306
318 6128594
319 6268254
320 6412151
321 6561511
322 6710246
323 6863328
324 7022192
325 7180555
326 7343324
327 7512324
328 7680844
329 7853857
330 8033531
331 8212852
332 8396693
333 8587690
334 8778333
335 8973663
336 9176617
337 9379321
338 9586743
339 9802306
340 10017707
341 10237980
342 10466875
343 10695741
344 10929467
345 11172471
346 11415547
347 11663590
348 11921448
349 12179496
350 12442590
351 12716201
352 12990080
353 13269125
354 13559232
355 13849840
356 14145682
357 14453313
358 14761546
359 15075092
360 15401131
361 15728021
362 16060240
363 16405758
364 16752212
365 17104170
366 17470188
367 17837379
368 18210088
369 18597684
370 18986670
371 19381352
372 19791698
373 20203714
374 20621396
375 21055743
376 21492001
377 21934055
378 22393639
379 22855393
380 23323020
381 23809268
382 24297897
383 24792542
384 25306701
385 25823664
386 26346711
387 26890390
388 27437136
389 27990049
390 28564687
391 29142871
392 29727232
393 30334535
394 30945631
395 31563124
396 32204738
397 32850603
398 33502890
399 34180557
400 34862893
401 35551886
402 36267472
403 36988244
404 37715632
405 38471116
406 39232272
407 40000208
408 40797568
409 41601115
410 42411533
411 43253002
412 44101126
413 44956321
414 45843922
415 46738908
416 47641078
417 48577315
418 49521481
419 50472972
420 51460153
421 52456080
422 53459368
423 54500155
424 55550215
425 56607944
426 57704944
427 58812033
428 59926851
429 61082799
430 62249607
431 63424482
432 64642296
433 65871893
434 67109551
435 68392312
436 69687741
437 70991501
438 72342318
439 73706734
440 75079661
441 76502002
442 77938809
443 79384444
444 80881506
445 82394244
446 83916038
447 85491678
448 87083984
449 88685594
450 90343398
451 92019243
452 93704523
453 95448602
454 97211730
455 98984773
456 100819164
457 102673990
458 104538920
459 106467862
460 108418565
461 110379940
462 112407947
463 114459251
464 116521342
465 118653131
466 120809715
467 122977573
468 125217960
469 127484720
470 129763106
471 132117351
472 134499492
473 136893819
474 139366905
475 141869855
476 144385446
477 146983204
478 149612528
479 152254996
480 154982950
481 157744683
482 160519935
483 163384345
484 166284273
485 169198521
486 172205540
487 175250325
488 178309892
489 181466007
490 184662065
491 187873849
492 191185884
493 194540353
494 197910935
495 201386036
496 204906035
497 208443032
498 212088521
499 215781482
500 219492161
501 223315946
502 227189727
503 231082247
504 235091966
505 239154755
506 243237174
507 247441541
508 251701759
509 255982584
510 260389993
511 264856701
512 269344829
513 273964625
514 278646611
515 283351376
516 288192836
517 293100052
518 298031022
519 303103911
520 308246015
521 313413480
522 318728007
523 324115658
524 329529608
525 335096481
526 340740351
527 346412090
528 352242273
529 358153503
530 364093978
531 370199235
532 376389556
533 382610898
534 389002706
535 395484312
536 401998581
537 408689827
538 415475295
539 422295212
540 429298460
541 436401185
542 443539979
543 450869045
544 458302199
545 465773748
546 473442458
547 481220709
548 489039221
549 497062065
550 505199795
551 513380472
552 521772571
553 530285522
554 538843295
555 547620446
556 556524405
557 565475877
558 574654294
559 583965769
560 593327234
561 602924221
562 612660474
563 622449748
564 632482337
565 642661324
566 652896246
567 663383322
568 674023567
569 684722858
570 695682968
571 706804101
572 717987234
573 729440611
574 741062124
575 752749458
576 764716393
577 776859671
578 789072091
579 801573843
580 814260059
581 827019803
582 840078509
583 853330597
584 866659655
585 880298383
586 894139446
587 908061993
588 922304493
589 936758680
590 951298603
591 966170024
592 981262480
593 996445681
594 1011971021
595 1027727939
596 1043580474
597 1059787061
598 1076235406
599 1092784559
600 1109699485
601 1126867742
602 1144141862
603 1161794418
604 1179711018
605 1197739655
606 1216159340
607 1234855176
608 1253668704
609 1272886401
610 1292392276
611 1312022822
612 1332070568
613 1352419566
614 1372899151
615 1393810327
616 1415035961
617 1436399432
618 1458208372
619 1480345542
620 1502627537
621 1525370463
622 1548455479
623 1571693325
624 1595406477
625 1619477058
626 1643708400
627 1668431005
628 1693526023
629 1718790218
630 1744561446
631 1770721814
632 1797059652
633 1823921502
634 1851188261
635 1878642205
636 1906637147
637 1935054563
638 1963668317
639 1992840684
640 2022453066
641 2052272617
642 2082668345
643 2113523038
644 2144594569
645 2176261475
646 2208406492
647 2240779717
648 2273766971
649 2307252286
650 2340976981
651 2375336331
652 2410213846
653 2445343212
654 2481126626
655 2517450181
656 2554038068
657 2591301380
658 2629126518
659 2667229134
660 2706028345
661 2745413278
662 2785088787
663 2825483581
664 2866486986
665 2907795897
666 2949846833
667 2992531495
668 3035536041
669 3079306174
670 3123735232
671 3168500732
672 3214055412
673 3260295991
674 3306888247
675 3354295297
676 3402415583
677 3450904960
678 3500234223
679 3550305178
680 3600762462
681 3652087122
682 3704182251
683 3756682643
684 3810076516
685 3864272026
686 3918891916
687 3974433806
688 4030808271
689 4087627181
690 4145396415
691 4204031945
692 4263132114
693 4323212889
694 4384192594
695 4445659398
696 4508137246
697 4571549447
698 4635470742
699 4700434649
700 4766368591
701 4832836324
702 4900378326
703 4968928348
704 5038035450
705 5108250981
706 5179513157
707 5251358487
708 5324345860
709 5398419963
710 5473103248
711 5548965141
712 5625954405
713 5703581136
714 5782421561
715 5862432961
716 5943110472
717 6025039744
718 6108183492
719 6192023314
720 6277152896
721 6363543998
722 6450661449
723 6539109065
724 6628864151
725 6719378711
726 6811264178
727 6904506635
728 6998541390
729 7093989219
730 7190843988
731 7288527308
732 7387666114
733 7488264774
734 7589726856
735 7692689943
736 7797166722
737 7902545267
738 8009469875
739 8117963944
740 8227398279
741 8338427446
742 8451082774
743 8564719751
744 8679998697
745 8796964201
746 8914953389
747 9034635380
748 9156064539
749 9278561270
750 9402801663
751 9528854211
752 9656018848
753 9784981018
754 9915819307
755 10047817867
756 10181668463
757 10317463566
758 10454467015
759 10593378879
760 10734304358
761 10876490598
762 11020642190
763 11166880334
764 11314430258
765 11464006251
766 11615743113
767 11768847148
768 11924037672
769 12081466024
770 12240317448
771 12401320311
772 12564639304
773 12729440987
774 12896457345
775 13065872754
776 13236831658
777 13410073112
778 13585797077
779 13763127794
780 13942809166
781 14125061937
782 14308985834
783 14495332377
784 14684338385
785 14875084441
786 15068326098
787 15264320837
788 15462124783
789 15662499748
790 15865722640
791 16070829409
792 16278583514
793 16489285219
794 16701944213
795 16917331486
796 17135768031
797 17356240907
798 17579523038
799 17805959528
800 18034512269
801 18265960847
802 18500670811
803 18737581771
804 18977473544
805 19220739541
806 19466293047
807 19714918040
808 19967031162
809 20221521566
810 20479174696
811 20740436727
812 21004167649
813 21271157406
814 21541876251
815 21815161303
816 22091802740
817 22372300396
818 22655462481
819 22942081793
820 23232686226
821 23526060172
822 23822993639
823 24124047232
824 24427974478
825 24735569350
826 25047422219
827 25362259921
828 25680873783
829 26003887987
830 26329999641
831 26660002951
832 26994551843
833 27332317088
834 27674087980
835 28020556858
836 28370363580
837 28724296998
838 29083082637
839 29445332103
840 29811830410
841 30183343660
842 30558449422
843 30937932337
844 31322592735
845 31710981512
846 32103878026
847 32502123320
848 32904234530
849 33310988318
850 33723264743
851 34139553177
852 34560621275
853 34987393737
854 35418323932
855 35854178002
856 36295922046
857 36741978422
858 37193103948
859 37650310905
860 38111987187
861 38578886580
862 39052062840
863 39529873432
864 40013059923
865 40502727554
866 40997198255
867 41497206578
868 42003903275
869 42515577696
870 43032953180
871 43557234791
872 44086672620
873 44621982831
874 45164417574
875 45712196136
876 46266021589
877 46827200846
878 47393914327
879 47966854757
880 48547381893
881 49133644512
882 49726317519
883 50326820057
884 50933259711
885 51546302035
886 52167421923
887 52794691753
888 53428758698
889 54071158926
890 54719925433
891 55375694202
892 56040057431
893 56711013463
894 57389176361
895 58076206019
896 58770060331
897 59471337194
898 60181757437
899 60899241982
900 61624367386
901 62358925853
902 63100793885
903 63850531194
904 64609992880
905 65377020766
906 66152150833
907 66937310067
908 67730296498
909 68531625495
910 69343293580
911 70163063388
912 70991420912
913 71830440007
914 72677836805
915 73534077515
916 74401309407
917 75277209157
918 76162212500
919 77058546547
920 77963843657
921 78878517252
922 79804868489
923 80740491202
924 81685763803
925 82643074732
926 83609972796
927 84586807951
928 85576048258
929 86575201637
930 87584583475
931 88606753561
932 89639170362
933 90682119761
934 91738243590
935 92804961970
936 93882523368
937 94973662317
938 96075750214
939 97189001305
940 98316240028
941 99454799006
942 100604847949
943 101769310486
944 102945467836
945 104133455872
946 105336292857
947 106551216959
948 107778317791
949 109020715650
950 110275600079
951 111543023933
952 112826202910
953 114122284673
954 115431270430
955 116756486498
956 118095031295
957 119446861946
958 120815406897
959 122197720077
960 123593706948
961 125006912177
962 126434335632
963 127875836737
964 129335065395
965 130808980290
966 132297385571
967 133804048587
968 135325875164
969 136862617592
970 138418157269
971 139989358949
972 141575911303
973 143181820548
974 144803895755
975 146441773870
976 148099580868
977 149774079935
978 151464842032
979 153176121611
980 154904629376
981 156649880987
982 158416251848
983 160200408317
984 162001793250
985 163824920523
986 165666404070
987 167525622477
988 169407218279
989 171307758613
990 173226548684
991 175168375955
992 177129750133
993 179109909640
994 181113774164
995 183137810531
996 185181179663
997 187248947654
998 189337525282
999 191445999739
1000 193579579695