1 1
2 2
3 11
4 34
5 77
6 146
7 247
8 386
9 569
10 802
11 1091
12 1442
13 1861
14 2354
15 2927
16 3586
17 4337
18 5186
19 6139
20 7202
21 8381
22 9682
23 11111
24 12674
25 14377
26 16226
27 18227
28 20386
29 22709
30 25202
31 27871
32 30722
33 33761
34 36994
35 40427
36 44066
37 47917
38 51986
39 56279
40 60802
41 65561
42 70562
43 75811
44 81314
45 87077
46 93106
47 99407
48 105986
49 112849
50 120002
51 127451
52 135202
53 143261
54 151634
55 160327
56 169346
57 178697
58 188386
59 198419
60 208802
61 219541
62 230642
63 242111
64 253954
65 266177
66 278786
67 291787
68 305186
69 318989
70 333202
71 347831
72 362882
73 378361
74 394274
75 410627
76 427426
77 444677
78 462386
79 480559
80 499202
81 518321
82 537922
83 558011
84 578594
85 599677
86 621266
87 643367
88 665986
89 689129
90 712802
91 737011
92 761762
93 787061
94 812914
95 839327
96 866306
97 893857
98 921986
99 950699
100 980002
101 1009901
102 1040402
103 1071511
104 1103234
105 1135577
106 1168546
107 1202147
108 1236386
109 1271269
110 1306802
111 1342991
112 1379842
113 1417361
114 1455554
115 1494427
116 1533986
117 1574237
118 1615186
119 1656839
120 1699202
121 1742281
122 1786082
123 1830611
124 1875874
125 1921877
126 1968626
127 2016127
128 2064386
129 2113409
130 2163202
131 2213771
132 2265122
133 2317261
134 2370194
135 2423927
136 2478466
137 2533817
138 2589986
139 2646979
140 2704802
141 2763461
142 2822962
143 2883311
144 2944514
145 3006577
146 3069506
147 3133307
148 3197986
149 3263549
150 3330002
151 3397351
152 3465602
153 3534761
154 3604834
155 3675827
156 3747746
157 3820597
158 3894386
159 3969119
160 4044802
161 4121441
162 4199042
163 4277611
164 4357154
165 4437677
166 4519186
167 4601687
168 4685186
169 4769689
170 4855202
171 4941731
172 5029282
173 5117861
174 5207474
175 5298127
176 5389826
177 5482577
178 5576386
179 5671259
180 5767202
181 5864221
182 5962322
183 6061511
184 6161794
185 6263177
186 6365666
187 6469267
188 6573986
189 6679829
190 6786802
191 6894911
192 7004162
193 7114561
194 7226114
195 7338827
196 7452706
197 7567757
198 7683986
199 7801399
200 7920002
201 8039801
202 8160802
203 8283011
204 8406434
205 8531077
206 8656946
207 8784047
208 8912386
209 9041969
210 9172802
211 9304891
212 9438242
213 9572861
214 9708754
215 9845927
216 9984386
217 10124137
218 10265186
219 10407539
220 10551202
221 10696181
222 10842482
223 10990111
224 11139074
225 11289377
226 11441026
227 11594027
228 11748386
229 11904109
230 12061202
231 12219671
232 12379522
233 12540761
234 12703394
235 12867427
236 13032866
237 13199717
238 13367986
239 13537679
240 13708802
241 13881361
242 14055362
243 14230811
244 14407714
245 14586077
246 14765906
247 14947207
248 15129986
249 15314249
250 15500002
251 15687251
252 15876002
253 16066261
254 16258034
255 16451327
256 16646146
257 16842497
258 17040386
259 17239819
260 17440802
261 17643341
262 17847442
263 18053111
264 18260354
265 18469177
266 18679586
267 18891587
268 19105186
269 19320389
270 19537202
271 19755631
272 19975682
273 20197361
274 20420674
275 20645627
276 20872226
277 21100477
278 21330386
279 21561959
280 21795202
281 22030121
282 22266722
283 22505011
284 22744994
285 22986677
286 23230066
287 23475167
288 23721986
289 23970529
290 24220802
291 24472811
292 24726562
293 24982061
294 25239314
295 25498327
296 25759106
297 26021657
298 26285986
299 26552099
300 26820002
301 27089701
302 27361202
303 27634511
304 27909634
305 28186577
306 28465346
307 28745947
308 29028386
309 29312669
310 29598802
311 29886791
312 30176642
313 30468361
314 30761954
315 31057427
316 31354786
317 31654037
318 31955186
319 32258239
320 32563202
321 32870081
322 33178882
323 33489611
324 33802274
325 34116877
326 34433426
327 34751927
328 35072386
329 35394809
330 35719202
331 36045571
332 36373922
333 36704261
334 37036594
335 37370927
336 37707266
337 38045617
338 38385986
339 38728379
340 39072802
341 39419261
342 39767762
343 40118311
344 40470914
345 40825577
346 41182306
347 41541107
348 41901986
349 42264949
350 42630002
351 42997151
352 43366402
353 43737761
354 44111234
355 44486827
356 44864546
357 45244397
358 45626386
359 46010519
360 46396802
361 46785241
362 47175842
363 47568611
364 47963554
365 48360677
366 48759986
367 49161487
368 49565186
369 49971089
370 50379202
371 50789531
372 51202082
373 51616861
374 52033874
375 52453127
376 52874626
377 53298377
378 53724386
379 54152659
380 54583202
381 55016021
382 55451122
383 55888511
384 56328194
385 56770177
386 57214466
387 57661067
388 58109986
389 58561229
390 59014802
391 59470711
392 59928962
393 60389561
394 60852514
395 61317827
396 61785506
397 62255557
398 62727986
399 63202799
400 63680002
401 64159601
402 64641602
403 65126011
404 65612834
405 66102077
406 66593746
407 67087847
408 67584386
409 68083369
410 68584802
411 69088691
412 69595042
413 70103861
414 70615154
415 71128927
416 71645186
417 72163937
418 72685186
419 73208939
420 73735202
421 74263981
422 74795282
423 75329111
424 75865474
425 76404377
426 76945826
427 77489827
428 78036386
429 78585509
430 79137202
431 79691471
432 80248322
433 80807761
434 81369794
435 81934427
436 82501666
437 83071517
438 83643986
439 84219079
440 84796802
441 85377161
442 85960162
443 86545811
444 87134114
445 87725077
446 88318706
447 88915007
448 89513986
449 90115649
450 90720002
451 91327051
452 91936802
453 92549261
454 93164434
455 93782327
456 94402946
457 95026297
458 95652386
459 96281219
460 96912802
461 97547141
462 98184242
463 98824111
464 99466754
465 100112177
466 100760386
467 101411387
468 102065186
469 102721789
470 103381202
471 104043431
472 104708482
473 105376361
474 106047074
475 106720627
476 107397026
477 108076277
478 108758386
479 109443359
480 110131202
481 110821921
482 111515522
483 112212011
484 112911394
485 113613677
486 114318866
487 115026967
488 115737986
489 116451929
490 117168802
491 117888611
492 118611362
493 119337061
494 120065714
495 120797327
496 121531906
497 122269457
498 123009986
499 123753499
500 124500002
501 125249501
502 126002002
503 126757511
504 127516034
505 128277577
506 129042146
507 129809747
508 130580386
509 131354069
510 132130802
511 132910591
512 133693442
513 134479361
514 135268354
515 136060427
516 136855586
517 137653837
518 138455186
519 139259639
520 140067202
521 140877881
522 141691682
523 142508611
524 143328674
525 144151877
526 144978226
527 145807727
528 146640386
529 147476209
530 148315202
531 149157371
532 150002722
533 150851261
534 151702994
535 152557927
536 153416066
537 154277417
538 155141986
539 156009779
540 156880802
541 157755061
542 158632562
543 159513311
544 160397314
545 161284577
546 162175106
547 163068907
548 163965986
549 164866349
550 165770002
551 166676951
552 167587202
553 168500761
554 169417634
555 170337827
556 171261346
557 172188197
558 173118386
559 174051919
560 174988802
561 175929041
562 176872642
563 177819611
564 178769954
565 179723677
566 180680786
567 181641287
568 182605186
569 183572489
570 184543202
571 185517331
572 186494882
573 187475861
574 188460274
575 189448127
576 190439426
577 191434177
578 192432386
579 193434059
580 194439202
581 195447821
582 196459922
583 197475511
584 198494594
585 199517177
586 200543266
587 201572867
588 202605986
589 203642629
590 204682802
591 205726511
592 206773762
593 207824561
594 208878914
595 209936827
596 210998306
597 212063357
598 213131986
599 214204199
600 215280002
601 216359401
602 217442402
603 218529011
604 219619234
605 220713077
606 221810546
607 222911647
608 224016386
609 225124769
610 226236802
611 227352491
612 228471842
613 229594861
614 230721554
615 231851927
616 232985986
617 234123737
618 235265186
619 236410339
620 237559202
621 238711781
622 239868082
623 241028111
624 242191874
625 243359377
626 244530626
627 245705627
628 246884386
629 248066909
630 249253202
631 250443271
632 251637122
633 252834761
634 254036194
635 255241427
636 256450466
637 257663317
638 258879986
639 260100479
640 261324802
641 262552961
642 263784962
643 265020811
644 266260514
645 267504077
646 268751506
647 270002807
648 271257986
649 272517049
650 273780002
651 275046851
652 276317602
653 277592261
654 278870834
655 280153327
656 281439746
657 282730097
658 284024386
659 285322619
660 286624802
661 287930941
662 289241042
663 290555111
664 291873154
665 293195177
666 294521186
667 295851187
668 297185186
669 298523189
670 299865202
671 301211231
672 302561282
673 303915361
674 305273474
675 306635627
676 308001826
677 309372077
678 310746386
679 312124759
680 313507202
681 314893721
682 316284322
683 317679011
684 319077794
685 320480677
686 321887666
687 323298767
688 324713986
689 326133329
690 327556802
691 328984411
692 330416162
693 331852061
694 333292114
695 334736327
696 336184706
697 337637257
698 339093986
699 340554899
700 342020002
701 343489301
702 344962802
703 346440511
704 347922434
705 349408577
706 350898946
707 352393547
708 353892386
709 355395469
710 356902802
711 358414391
712 359930242
713 361450361
714 362974754
715 364503427
716 366036386
717 367573637
718 369115186
719 370661039
720 372211202
721 373765681
722 375324482
723 376887611
724 378455074
725 380026877
726 381603026
727 383183527
728 384768386
729 386357609
730 387951202
731 389549171
732 391151522
733 392758261
734 394369394
735 395984927
736 397604866
737 399229217
738 400857986
739 402491179
740 404128802
741 405770861
742 407417362
743 409068311
744 410723714
745 412383577
746 414047906
747 415716707
748 417389986
749 419067749
750 420750002
751 422436751
752 424128002
753 425823761
754 427524034
755 429228827
756 430938146
757 432651997
758 434370386
759 436093319
760 437820802
761 439552841
762 441289442
763 443030611
764 444776354
765 446526677
766 448281586
767 450041087
768 451805186
769 453573889
770 455347202
771 457125131
772 458907682
773 460694861
774 462486674
775 464283127
776 466084226
777 467889977
778 469700386
779 471515459
780 473335202
781 475159621
782 476988722
783 478822511
784 480660994
785 482504177
786 484352066
787 486204667
788 488061986
789 489924029
790 491790802
791 493662311
792 495538562
793 497419561
794 499305314
795 501195827
796 503091106
797 504991157
798 506895986
799 508805599
800 510720002
801 512639201
802 514563202
803 516492011
804 518425634
805 520364077
806 522307346
807 524255447
808 526208386
809 528166169
810 530128802
811 532096291
812 534068642
813 536045861
814 538027954
815 540014927
816 542006786
817 544003537
818 546005186
819 548011739
820 550023202
821 552039581
822 554060882
823 556087111
824 558118274
825 560154377
826 562195426
827 564241427
828 566292386
829 568348309
830 570409202
831 572475071
832 574545922
833 576621761
834 578702594
835 580788427
836 582879266
837 584975117
838 587075986
839 589181879
840 591292802
841 593408761
842 595529762
843 597655811
844 599786914
845 601923077
846 604064306
847 606210607
848 608361986
849 610518449
850 612680002
851 614846651
852 617018402
853 619195261
854 621377234
855 623564327
856 625756546
857 627953897
858 630156386
859 632364019
860 634576802
861 636794741
862 639017842
863 641246111
864 643479554
865 645718177
866 647961986
867 650210987
868 652465186
869 654724589
870 656989202
871 659259031
872 661534082
873 663814361
874 666099874
875 668390627
876 670686626
877 672987877
878 675294386
879 677606159
880 679923202
881 682245521
882 684573122
883 686906011
884 689244194
885 691587677
886 693936466
887 696290567
888 698649986
889 701014729
890 703384802
891 705760211
892 708140962
893 710527061
894 712918514
895 715315327
896 717717506
897 720125057
898 722537986
899 724956299
900 727380002
901 729809101
902 732243602
903 734683511
904 737128834
905 739579577
906 742035746
907 744497347
908 746964386
909 749436869
910 751914802
911 754398191
912 756887042
913 759381361
914 761881154
915 764386427
916 766897186
917 769413437
918 771935186
919 774462439
920 776995202
921 779533481
922 782077282
923 784626611
924 787181474
925 789741877
926 792307826
927 794879327
928 797456386
929 800039009
930 802627202
931 805220971
932 807820322
933 810425261
934 813035794
935 815651927
936 818273666
937 820901017
938 823533986
939 826172579
940 828816802
941 831466661
942 834122162
943 836783311
944 839450114
945 842122577
946 844800706
947 847484507
948 850173986
949 852869149
950 855570002
951 858276551
952 860988802
953 863706761
954 866430434
955 869159827
956 871894946
957 874635797
958 877382386
959 880134719
960 882892802
961 885656641
962 888426242
963 891201611
964 893982754
965 896769677
966 899562386
967 902360887
968 905165186
969 907975289
970 910791202
971 913612931
972 916440482
973 919273861
974 922113074
975 924958127
976 927809026
977 930665777
978 933528386
979 936396859
980 939271202
981 942151421
982 945037522
983 947929511
984 950827394
985 953731177
986 956640866
987 959556467
988 962477986
989 965405429
990 968338802
991 971278111
992 974223362
993 977174561
994 980131714
995 983094827
996 986063906
997 989038957
998 992019986
999 995006999
1000 998000002