0 1
1 1
2 2
3 3
4 5
5 7
6 11
7 15
8 22
9 30
10 41
11 54
12 73
13 94
14 123
15 157
16 201
17 252
18 318
19 393
20 488
21 598
22 732
23 887
24 1076
25 1291
26 1549
27 1845
28 2194
29 2592
30 3060
31 3589
32 4206
33 4904
34 5708
35 6615
36 7657
37 8824
38 10156
39 11648
40 13338
41 15224
42 17354
43 19720
44 22380
45 25331
46 28629
47 32278
48 36347
49 40831
50 45812
51 51294
52 57358
53 64015
54 71362
55 79403
56 88252
57 97922
58 108527
59 120092
60 132751
61 146520
62 161554
63 177884
64 195666
65 214944
66 235899
67 258569
68 283161
69 309729
70 338484
71 369499
72 403016
73 439100
74 478025
75 519880
76 564945
77 613331
78 665355
79 721125
80 780997
81 845105
82 913815
83 987292
84 1065947
85 1149941
86 1239732
87 1335517
88 1437769
89 1546719
90 1662894
91 1786528
92 1918204
93 2058197
94 2207110
95 2365264
96 2533326
97 2711621
98 2900883
99 3101490
100 3314203
101 3539452
102 3778074
103 4030512
104 4297682
105 4580087
106 4878678
107 5194025
108 5527168
109 5878693
110 6249733
111 6640950
112 7053522
113 7488186
114 7946224
115 8428402
116 8936110
117 9470200
118 10032118
119 10622810
120 11243843
121 11896197
122 12581565
123 13301033
124 14056363
125 14848747
126 15680087
127 16551625
128 17465409
129 18422800
130 19425930
131 20476289
132 21576170
133 22727123
134 23931608
135 25191319
136 26508817
137 27885941
138 29325437
139 30829224
140 32400240
141 34040565
142 35753258
143 37540572
144 39405777
145 41351219
146 43380387
147 45495819
148 47701146
149 49999100
150 52393552
151 54887353
152 57484623
153 60188427
154 63003052
155 65931791
156 68979203
157 72148718
158 75445177
159 78872260
160 82435003
161 86137340
162 89984614
163 93980928
164 98131943
165 102442041
166 106917108
167 111561821
168 116382412
169 121383750
170 126572425
171 131953628
172 137534208
173 143319684
174 149317293
175 155532785
176 161973798
177 168646439
178 175558643
179 182716893
180 190129558
181 197803382
182 205747183
183 213968113
184 222475328
185 231276396
186 240380957
187 249796887
188 259534326
189 269601601
190 280009235
191 290766028
192 301883042
193 313369422
194 325236786
195 337494790
196 350155485
197 363229048
198 376728128
199 390663302
200 405047836
201 419892869
202 435212154
203 451017418
204 467323075
205 484141299
206 501487186
207 519373542
208 537816009
209 556828038
210 576426002
211 596623863
212 617438747
213 638885309
214 660981285
215 683742052
216 707186151
217 731329526
218 756191547
219 781788932
220 808141730
221 835267449
222 863187023
223 891918603
224 921484034
225 951902312
226 983196036
227 1015385081
228 1048493017
229 1082540428
230 1117551883
231 1153548904
232 1190556895
233 1228598336
234 1267699694
235 1307884246
236 1349179552
237 1391609911
238 1435203805
239 1479986592
240 1525987916
241 1573234010
242 1621755712
243 1671580383
244 1722739876
245 1775262704
246 1829181987
247 1884527214
248 1941332807
249 1999629479
250 2059452768
251 2120834654
252 2183812055
253 2248418018
254 2314690878
255 2382665027
256 2452380023
257 2523871631
258 2597180909
259 2672344805
260 2749405916
261 2828402646
262 2909378930
263 2992374676
264 3077435447
265 3164602439
266 3253922885
267 3345439573
268 3439201197
269 3535252170
270 3633642950
271 3734419369
272 3837633694
273 3943333476
274 4051572573
275 4162400309
276 4275872450
277 4392039861
278 4510960264
279 4632686396
280 4757277710
281 4884788853
282 5015281340
283 5148811507
284 5285442981
285 5425234114
286 5568250412
287 5714552303
288 5864207517
289 6017278309
290 6173834687
291 6333941094
292 6497669574
293 6665086802
294 6836267218
295 7011279491
296 7190200514
297 7373101306
298 7560060963
299 7751152921
300 7946458854
301 8146054349
302 8350023718
303 8558445090
304 8771405157
305 8988984640
306 9211273001
307 9438353299
308 9670317830
309 9907252377
310 10149251803
311 10396404689
312 10648808871
313 10906555445
314 11169745287
315 11438472431
316 11712840517
317 11992946574
318 12278897429
319 12570792834
320 12868742874
321 13172850442
322 13483228597
323 13799983455
324 14123231487
325 14453081731
326 14789654145
327 15133061145
328 15483425883
329 15840864217
330 16205502948
331 16577461088
332 16956869166
333 17343849799
334 17738536942
335 18141056907
336 18551547548
337 18970138552
338 19396971755
339 19832180710
340 20275910924
341 20728299888
342 21189497270
343 21659644193
344 22138894573
345 22627393651
346 23125299271
347 23632760891
348 24149940791
349 24676992308
350 25214082250
351 25761368359
352 26319021642
353 26887204327
354 27466092146
355 28055851489
356 28656662909
357 29268697480
358 29892140238
359 30527167049
360 31173967977
361 31832723323
362 32503628280
363 33186868149
364 33882642904
365 34591142935
366 35312573561
367 36047129919
368 36795022779
369 37556452584
370 38331635198
371 39120776489
372 39924097998
373 40741810642
374 41574141750
375 42421307891
376 43283541816
377 44161065845
378 45054118754
379 45962928253
380 46887739259
381 47828785471
382 48786317571
383 49760575376
384 50751815956
385 51760284851
386 52786245640
387 53829950230
388 54891668324
389 55971658305
390 57070196644
391 58187547820
392 59323995199
393 60479809995
394 61655282074
395 62850689526
396 64066329381
397 65302486190
398 66559464280
399 67837555349
400 69137070616
401 70458309046
402 71801589436
403 73167217620
404 74555520111
405 75966810293
406 77401421981
407 78859676261
408 80341914958
409 81848466425
410 83379680641
411 84935893956
412 86517464079
413 88124735489
414 89758074354
415 91417832864
416 93104385797
417 94818093779
418 96559339764
419 98328492979
420 100125945306
421 101952074118
422 103807280382
423 105691950392
424 107606493756
425 109551305833
426 111526805647
427 113533397185
428 115571509050
429 117641554627
430 119743971645
431 121879183065
432 124047636540
433 126249764132
434 128486023588
435 130756856893
436 133062731424
437 135404099246
438 137781438188
439 140195209938
440 142645902954
441 145133989364
442 147659967781
443 150224320966
444 152827558533
445 155470173380
446 158152686306
447 160875601216
448 163639449611
449 166444746573
450 169292035175
451 172181841200
452 175114719484
453 178091207377
454 181111870984
455 184177259429
456 187287950981
457 190444506022
458 193647515184
459 196897551027
460 200195216042
461 203541095152
462 206935803628
463 210379938259
464 213874127302
465 217418980328
466 221015138066
467 224663223092
468 228363889553
469 232117772493
470 235925539691
471 239787839631
472 243705353200
473 247678742522
474 251708702564
475 255795908574
476 259941069821
477 264144875644
478 268408049080
479 272731293798
480 277115347602
481 281560927933
482 286068787592
483 290639658818
484 295274308864
485 299973484983
486 304737969906
487 309568525363
488 314465949802
489 319431020451
490 324464550920
491 329567334191
492 334740200089
493 339983956772
494 345299450527
495 350687505768
496 356148984679
497 361684728163
498 367295615382
499 372982503171
500 378746287926
501 384587843490
502 390508082918
503 396507897335
504 402588217564
505 408749951412
506 414994047735
507 421321432160
508 427733070990
509 434229907922
510 440812927844
511 447483091946
512 454241403975
513 461088843747
514 468026433272
515 475055171285
516 482176099226
517 489390234128
518 496698637145
519 504102344803
520 511602437364
521 519199971116
522 526896046625
523 534691739344
524 542588170436
525 550586435711
526 558687676312
527 566893008718
528 575203595279
529 583620572501
530 592145124244
531 600778408297
532 609521629403
533 618375966922
534 627342647737
535 636422872161
536 645617889530
537 654928922362
538 664357241809
539 673904092927
540 683570769971
541 693358539872
542 703268720312
543 713302601415
544 723461523642
545 733746800618
546 744159796902
547 754701848982
548 765374345849
549 776178648168
550 787116168704
551 798188292653
552 809396457905
553 820742073503
554 832226602806
555 843851480086
556 855618193503
557 867528202887
558 879583022582
559 891784137317
560 904133087976
561 916631385565
562 929280596829
563 942082259428
564 955037967383
565 968149284303
566 981417831852
567 994845201035
568 1008433040470
569 1022182968909
570 1036096663373
571 1050175769682
572 1064421993638
573 1078837009573
574 1093422551371
575 1108180322275
576 1123112085733
577 1138219573173
578 1153504577997
579 1168968861333
580 1184614245827
581 1200442522681
582 1216455545301
583 1232655134264
584 1249043174138
585 1265621516386
586 1282392076018
587 1299356735807
588 1316517442756
589 1333876110200
590 1351434717549
591 1369195210284
592 1387159599492
593 1405329863198
594 1423708045751
595 1442296157001
596 1461096274985
597 1480110442959
598 1499340771908
599 1518789338942
600 1538458289615
601 1558349734123
602 1578465853028
603 1598808791267
604 1619380763659
605 1640183950305
606 1661220601938
607 1682492933083
608 1704003230839
609 1725753745807
610 1747746800691
611 1769984682643
612 1792469751665
613 1815204330671
614 1838190817426
615 1861431572334
616 1884929030152
617 1908685589222
618 1932703723023
619 1956985867076
620 1981534534060
621 2006352198400
622 2031441411194
623 2056804686273
624 2082444614921
625 2108363749565
626 2134564722167
627 2161050125553
628 2187822631572
629 2214884873924
630 2242239566150
631 2269889382044
632 2297837077345
633 2326085367742
634 2354637050370
635 2383494883343
636 2412661707035
637 2442140321155
638 2471933609836
639 2502044416261
640 2532475667511
641 2563230250746
642 2594311137877
643 2625721259242
644 2657463632116
645 2689541231892
646 2721957120388
647 2754714318611
648 2787815934843
649 2821265034854
650 2855064773939
651 2889218264590
652 2923728708283
653 2958599264764
654 2993833183651
655 3029433671125
656 3065404025510
657 3101747501378
658 3138467444918
659 3175567159682
660 3213050041725
661 3250919442708
662 3289178809131
663 3327831542803
664 3366881139818
665 3406331052695
666 3446184829163
667 3486445971613
668 3527118080004
669 3568204708636
670 3609709508837
671 3651636087436
672 3693988149213
673 3736769352635
674 3779983456544
675 3823634173167
676 3867725314537
677 3912260647234
678 3957244038607
679 4002679308731
680 4048570380897
681 4094921130795
682 4141735536778
683 4189017530804
684 4236771148454
685 4285000377043
686 4333709310023
687 4382901992272
688 4432582574223
689 4482755158942
690 4533423956052
691 4584593125931
692 4636266938051
693 4688449612307
694 4741145477120
695 4794358812588
696 4848094008334
697 4902355403728
698 4957147450271
699 5012474548898
700 5068341212079
701 5124751902972
702 5181711197312
703 5239223619585
704 5297293809484
705 5355926355115
706 5415125959210
707 5474897274216
708 5535245068244
709 5596174057132
710 5657689075081
711 5719794903701
712 5782496442355
713 5845798539118
714 5909706160900
715 5974224221327
716 6039357755584
717 6105111745229
718 6171491292785
719 6238501448498
720 6306147384659
721 6374434219233
722 6443367195025
723 6512951500192
724 6583192447106
725 6654095294844
726 6725665427821
727 6797908175102
728 6870828993910
729 6944433285769
730 7018726579754
731 7093714350642
732 7169402201882
733 7245795680516
734 7322900465150
735 7400722177656
736 7479266570832
737 7558539342145
738 7638546321154
739 7719293279971
740 7800786125718
741 7883030707717
742 7966033009679
743 8049798958967
744 8134334618497
745 8219645992667
746 8305739224419
747 8392620397846
748 8480295734933
749 8568771400271
750 8658053697552
751 8748148870897
752 8839063306546
753 8930803330810
754 9023375411485
755 9116785957943
756 9211041522248
757 9306148595808
758 9402113815816
759 9498943758473
760 9596645145100
761 9695224637533
762 9794689043982
763 9895045110934
764 9996299734368
765 10098459748179
766 10201532135106
767 10305523817363
768 10410441867260
769 10516293294287
770 10623085261226
771 10730824867699
772 10839519365942
773 10949175946592
774 11059801954199
775 11171404669413
776 11283991530020
777 11397569909540
778 11512147337968
779 11627731282647
780 11744329368692
781 11861949156209
782 11980598366376
783 12100284655019
784 12221015838344
785 12342799668821
786 12465644060646
787 12589556861915
788 12714546085778
789 12840619678915
790 12967785752387
791 13096052352454
792 13225427691101
793 13355919913091
794 13487537332319
795 13620288195112
796 13754180916223
797 13889223844510
798 14025425498650
799 14162794328997
800 14301338959160
801 14441067944051
802 14581990011151
803 14724113820971
804 14867448207982
805 15012001937200
806 15157783951116
807 15304803122417
808 15453068500547
809 15602589066875
810 15753373980969
811 15905432331830
812 16058773390203
813 16213406355889
814 16369340609734
815 16526585463425
816 16685150411134
817 16845044875324
818 17006278464569
819 17168860715382
820 17332801349655
821 17498110019008
822 17664796561931
823 17832870744085
824 18002342521657
825 18173221777625
826 18345518584782
827 18519242944556
828 18694405049680
829 18871015018906
830 19049083166030
831 19228619730512
832 19409635146112
833 19592139774102
834 19776144171595
835 19961658820595
836 20148694402715
837 20337261524077
838 20527370989688
839 20719033530969
840 20912260079767
841 21107061491660
842 21303448826506
843 21501433067537
844 21701025401508
845 21902236940457
846 22105079001538
847 22309562824500
848 22515699858092
849 22723501473273
850 22932979249266
851 23144144689471
852 23357009507144
853 23571585336970
854 23787884027459
855 24005917348191
856 24225697281802
857 24447235733969
858 24670544825071
859 24895636595773
860 25122523305443
861 25351217133348
862 25581730476710
863 25814075654680
864 26048265206009
865 26284311588561
866 26522227483888
867 26762025492295
868 27003718436993
869 27247319061980
870 27492840335860
871 27740295145202
872 27989696605301
873 28241057749028
874 28494391837220
875 28749712050385
876 29007031798695
877 29266364409110
878 29527723442462
879 29791122376009
880 30056574920088
881 30324094703560
882 30593695590120
883 30865391359097
884 31139196028895
885 31415123533162
886 31693188043849
887 31973403650311
888 32255784681960
889 32540345382660
890 32827100240662
891 33116063658307
892 33407250281517
893 33700674672469
894 33996351638731
895 34294295901168
896 34594522430400
897 34897046109952
898 35201882072322
899 35509045365139
900 35818551286815
901 36130415047872
902 36444652114070
903 36761277862916
904 37080307926337
905 37401757850239
906 37725643436815
907 38051980399211
908 38380784711348
909 38712072257708
910 39045859182754
911 39382161543804
912 39720995660025
913 40062377760348
914 40406324340134
915 40752851804145
916 41101976822744
917 41453715977995
918 41808086119488
919 42165104005418
920 42524786666122
921 42887151040149
922 43252214337385
923 43619993678292
924 43990506456594
925 44363769973431
926 44739801807914
927 45118619446207
928 45500240651605
929 45884683096825
930 46271964733700
931 46662103420319
932 47055117298631
933 47451024416449
934 47849843104630
935 48251591602329
936 48656288433730
937 49063952028084
938 49474601104511
939 49888254286835
940 50304930487898
941 50724648527686
942 51147427517248
943 51573286471541
944 52002244701460
945 52434321421416
946 52869536140931
947 53307908275550
948 53749457537974
949 54194203543625
950 54642166210053
951 55093365357167
952 55547821106143
953 56005553483027
954 56466582817239
955 56930929339762
956 57398613589961
957 57869656008373
958 58344077343080
959 58821898245915
960 59303139678363
961 59787822502287
962 60275967894308
963 60767596931065
964 61262731003082
965 61761391403487
966 62263599741462
967 62769377525414
968 63278746584948
969 63791728648503
970 64308345764870
971 64828619884327
972 65352573279674
973 65880228121753
974 66411606909170
975 66946732038215
976 67485626232059
977 68028312114217
978 68574812637318
979 69125150650885
980 69679349338835
981 70237431781590
982 70799421393110
983 71365341486589
984 71935215710993
985 72509067611004
986 73086921072457
987 73668799876547
988 74254728144729
989 74844729896554
990 75438829494131
991 76037051194142
992 76639419601247
993 77245959214292
994 77856694879235
995 78471651339026
996 79090853686026
997 79714326905998
998 80342096339637
999 80974187220686
1000 81610625136918