1 1
2 2
3 3
4 10
5 29
6 66
7 127
8 218
9 345
10 514
11 731
12 1002
13 1333
14 1730
15 2199
16 2746
17 3377
18 4098
19 4915
20 5834
21 6861
22 8002
23 9263
24 10650
25 12169
26 13826
27 15627
28 17578
29 19685
30 21954
31 24391
32 27002
33 29793
34 32770
35 35939
36 39306
37 42877
38 46658
39 50655
40 54874
41 59321
42 64002
43 68923
44 74090
45 79509
46 85186
47 91127
48 97338
49 103825
50 110594
51 117651
52 125002
53 132653
54 140610
55 148879
56 157466
57 166377
58 175618
59 185195
60 195114
61 205381
62 216002
63 226983
64 238330
65 250049
66 262146
67 274627
68 287498
69 300765
70 314434
71 328511
72 343002
73 357913
74 373250
75 389019
76 405226
77 421877
78 438978
79 456535
80 474554
81 493041
82 512002
83 531443
84 551370
85 571789
86 592706
87 614127
88 636058
89 658505
90 681474
91 704971
92 729002
93 753573
94 778690
95 804359
96 830586
97 857377
98 884738
99 912675
100 941194
101 970301
102 1000002
103 1030303
104 1061210
105 1092729
106 1124866
107 1157627
108 1191018
109 1225045
110 1259714
111 1295031
112 1331002
113 1367633
114 1404930
115 1442899
116 1481546
117 1520877
118 1560898
119 1601615
120 1643034
121 1685161
122 1728002
123 1771563
124 1815850
125 1860869
126 1906626
127 1953127
128 2000378
129 2048385
130 2097154
131 2146691
132 2197002
133 2248093
134 2299970
135 2352639
136 2406106
137 2460377
138 2515458
139 2571355
140 2628074
141 2685621
142 2744002
143 2803223
144 2863290
145 2924209
146 2985986
147 3048627
148 3112138
149 3176525
150 3241794
151 3307951
152 3375002
153 3442953
154 3511810
155 3581579
156 3652266
157 3723877
158 3796418
159 3869895
160 3944314
161 4019681
162 4096002
163 4173283
164 4251530
165 4330749
166 4410946
167 4492127
168 4574298
169 4657465
170 4741634
171 4826811
172 4913002
173 5000213
174 5088450
175 5177719
176 5268026
177 5359377
178 5451778
179 5545235
180 5639754
181 5735341
182 5832002
183 5929743
184 6028570
185 6128489
186 6229506
187 6331627
188 6434858
189 6539205
190 6644674
191 6751271
192 6859002
193 6967873
194 7077890
195 7189059
196 7301386
197 7414877
198 7529538
199 7645375
200 7762394
201 7880601
202 8000002
203 8120603
204 8242410
205 8365429
206 8489666
207 8615127
208 8741818
209 8869745
210 8998914
211 9129331
212 9261002
213 9393933
214 9528130
215 9663599
216 9800346
217 9938377
218 10077698
219 10218315
220 10360234
221 10503461
222 10648002
223 10793863
224 10941050
225 11089569
226 11239426
227 11390627
228 11543178
229 11697085
230 11852354
231 12008991
232 12167002
233 12326393
234 12487170
235 12649339
236 12812906
237 12977877
238 13144258
239 13312055
240 13481274
241 13651921
242 13824002
243 13997523
244 14172490
245 14348909
246 14526786
247 14706127
248 14886938
249 15069225
250 15252994
251 15438251
252 15625002
253 15813253
254 16003010
255 16194279
256 16387066
257 16581377
258 16777218
259 16974595
260 17173514
261 17373981
262 17576002
263 17779583
264 17984730
265 18191449
266 18399746
267 18609627
268 18821098
269 19034165
270 19248834
271 19465111
272 19683002
273 19902513
274 20123650
275 20346419
276 20570826
277 20796877
278 21024578
279 21253935
280 21484954
281 21717641
282 21952002
283 22188043
284 22425770
285 22665189
286 22906306
287 23149127
288 23393658
289 23639905
290 23887874
291 24137571
292 24389002
293 24642173
294 24897090
295 25153759
296 25412186
297 25672377
298 25934338
299 26198075
300 26463594
301 26730901
302 27000002
303 27270903
304 27543610
305 27818129
306 28094466
307 28372627
308 28652618
309 28934445
310 29218114
311 29503631
312 29791002
313 30080233
314 30371330
315 30664299
316 30959146
317 31255877
318 31554498
319 31855015
320 32157434
321 32461761
322 32768002
323 33076163
324 33386250
325 33698269
326 34012226
327 34328127
328 34645978
329 34965785
330 35287554
331 35611291
332 35937002
333 36264693
334 36594370
335 36926039
336 37259706
337 37595377
338 37933058
339 38272755
340 38614474
341 38958221
342 39304002
343 39651823
344 40001690
345 40353609
346 40707586
347 41063627
348 41421738
349 41781925
350 42144194
351 42508551
352 42875002
353 43243553
354 43614210
355 43986979
356 44361866
357 44738877
358 45118018
359 45499295
360 45882714
361 46268281
362 46656002
363 47045883
364 47437930
365 47832149
366 48228546
367 48627127
368 49027898
369 49430865
370 49836034
371 50243411
372 50653002
373 51064813
374 51478850
375 51895119
376 52313626
377 52734377
378 53157378
379 53582635
380 54010154
381 54439941
382 54872002
383 55306343
384 55742970
385 56181889
386 56623106
387 57066627
388 57512458
389 57960605
390 58411074
391 58863871
392 59319002
393 59776473
394 60236290
395 60698459
396 61162986
397 61629877
398 62099138
399 62570775
400 63044794
401 63521201
402 64000002
403 64481203
404 64964810
405 65450829
406 65939266
407 66430127
408 66923418
409 67419145
410 67917314
411 68417931
412 68921002
413 69426533
414 69934530
415 70444999
416 70957946
417 71473377
418 71991298
419 72511715
420 73034634
421 73560061
422 74088002
423 74618463
424 75151450
425 75686969
426 76225026
427 76765627
428 77308778
429 77854485
430 78402754
431 78953591
432 79507002
433 80062993
434 80621570
435 81182739
436 81746506
437 82312877
438 82881858
439 83453455
440 84027674
441 84604521
442 85184002
443 85766123
444 86350890
445 86938309
446 87528386
447 88121127
448 88716538
449 89314625
450 89915394
451 90518851
452 91125002
453 91733853
454 92345410
455 92959679
456 93576666
457 94196377
458 94818818
459 95443995
460 96071914
461 96702581
462 97336002
463 97972183
464 98611130
465 99252849
466 99897346
467 100544627
468 101194698
469 101847565
470 102503234
471 103161711
472 103823002
473 104487113
474 105154050
475 105823819
476 106496426
477 107171877
478 107850178
479 108531335
480 109215354
481 109902241
482 110592002
483 111284643
484 111980170
485 112678589
486 113379906
487 114084127
488 114791258
489 115501305
490 116214274
491 116930171
492 117649002
493 118370773
494 119095490
495 119823159
496 120553786
497 121287377
498 122023938
499 122763475
500 123505994
501 124251501
502 125000002
503 125751503
504 126506010
505 127263529
506 128024066
507 128787627
508 129554218
509 130323845
510 131096514
511 131872231
512 132651002
513 133432833
514 134217730
515 135005699
516 135796746
517 136590877
518 137388098
519 138188415
520 138991834
521 139798361
522 140608002
523 141420763
524 142236650
525 143055669
526 143877826
527 144703127
528 145531578
529 146363185
530 147197954
531 148035891
532 148877002
533 149721293
534 150568770
535 151419439
536 152273306
537 153130377
538 153990658
539 154854155
540 155720874
541 156590821
542 157464002
543 158340423
544 159220090
545 160103009
546 160989186
547 161878627
548 162771338
549 163667325
550 164566594
551 165469151
552 166375002
553 167284153
554 168196610
555 169112379
556 170031466
557 170953877
558 171879618
559 172808695
560 173741114
561 174676881
562 175616002
563 176558483
564 177504330
565 178453549
566 179406146
567 180362127
568 181321498
569 182284265
570 183250434
571 184220011
572 185193002
573 186169413
574 187149250
575 188132519
576 189119226
577 190109377
578 191102978
579 192100035
580 193100554
581 194104541
582 195112002
583 196122943
584 197137370
585 198155289
586 199176706
587 200201627
588 201230058
589 202262005
590 203297474
591 204336471
592 205379002
593 206425073
594 207474690
595 208527859
596 209584586
597 210644877
598 211708738
599 212776175
600 213847194
601 214921801
602 216000002
603 217081803
604 218167210
605 219256229
606 220348866
607 221445127
608 222545018
609 223648545
610 224755714
611 225866531
612 226981002
613 228099133
614 229220930
615 230346399
616 231475546
617 232608377
618 233744898
619 234885115
620 236029034
621 237176661
622 238328002
623 239483063
624 240641850
625 241804369
626 242970626
627 244140627
628 245314378
629 246491885
630 247673154
631 248858191
632 250047002
633 251239593
634 252435970
635 253636139
636 254840106
637 256047877
638 257259458
639 258474855
640 259694074
641 260917121
642 262144002
643 263374723
644 264609290
645 265847709
646 267089986
647 268336127
648 269586138
649 270840025
650 272097794
651 273359451
652 274625002
653 275894453
654 277167810
655 278445079
656 279726266
657 281011377
658 282300418
659 283593395
660 284890314
661 286191181
662 287496002
663 288804783
664 290117530
665 291434249
666 292754946
667 294079627
668 295408298
669 296740965
670 298077634
671 299418311
672 300763002
673 302111713
674 303464450
675 304821219
676 306182026
677 307546877
678 308915778
679 310288735
680 311665754
681 313046841
682 314432002
683 315821243
684 317214570
685 318611989
686 320013506
687 321419127
688 322828858
689 324242705
690 325660674
691 327082771
692 328509002
693 329939373
694 331373890
695 332812559
696 334255386
697 335702377
698 337153538
699 338608875
700 340068394
701 341532101
702 343000002
703 344472103
704 345948410
705 347428929
706 348913666
707 350402627
708 351895818
709 353393245
710 354894914
711 356400831
712 357911002
713 359425433
714 360944130
715 362467099
716 363994346
717 365525877
718 367061698
719 368601815
720 370146234
721 371694961
722 373248002
723 374805363
724 376367050
725 377933069
726 379503426
727 381078127
728 382657178
729 384240585
730 385828354
731 387420491
732 389017002
733 390617893
734 392223170
735 393832839
736 395446906
737 397065377
738 398688258
739 400315555
740 401947274
741 403583421
742 405224002
743 406869023
744 408518490
745 410172409
746 411830786
747 413493627
748 415160938
749 416832725
750 418508994
751 420189751
752 421875002
753 423564753
754 425259010
755 426957779
756 428661066
757 430368877
758 432081218
759 433798095
760 435519514
761 437245481
762 438976002
763 440711083
764 442450730
765 444194949
766 445943746
767 447697127
768 449455098
769 451217665
770 452984834
771 454756611
772 456533002
773 458314013
774 460099650
775 461889919
776 463684826
777 465484377
778 467288578
779 469097435
780 470910954
781 472729141
782 474552002
783 476379543
784 478211770
785 480048689
786 481890306
787 483736627
788 485587658
789 487443405
790 489303874
791 491169071
792 493039002
793 494913673
794 496793090
795 498677259
796 500566186
797 502459877
798 504358338
799 506261575
800 508169594
801 510082401
802 512000002
803 513922403
804 515849610
805 517781629
806 519718466
807 521660127
808 523606618
809 525557945
810 527514114
811 529475131
812 531441002
813 533411733
814 535387330
815 537367799
816 539353146
817 541343377
818 543338498
819 545338515
820 547343434
821 549353261
822 551368002
823 553387663
824 555412250
825 557441769
826 559476226
827 561515627
828 563559978
829 565609285
830 567663554
831 569722791
832 571787002
833 573856193
834 575930370
835 578009539
836 580093706
837 582182877
838 584277058
839 586376255
840 588480474
841 590589721
842 592704002
843 594823323
844 596947690
845 599077109
846 601211586
847 603351127
848 605495738
849 607645425
850 609800194
851 611960051
852 614125002
853 616295053
854 618470210
855 620650479
856 622835866
857 625026377
858 627222018
859 629422795
860 631628714
861 633839781
862 636056002
863 638277383
864 640503930
865 642735649
866 644972546
867 647214627
868 649461898
869 651714365
870 653972034
871 656234911
872 658503002
873 660776313
874 663054850
875 665338619
876 667627626
877 669921877
878 672221378
879 674526135
880 676836154
881 679151441
882 681472002
883 683797843
884 686128970
885 688465389
886 690807106
887 693154127
888 695506458
889 697864105
890 700227074
891 702595371
892 704969002
893 707347973
894 709732290
895 712121959
896 714516986
897 716917377
898 719323138
899 721734275
900 724150794
901 726572701
902 729000002
903 731432703
904 733870810
905 736314329
906 738763266
907 741217627
908 743677418
909 746142645
910 748613314
911 751089431
912 753571002
913 756058033
914 758550530
915 761048499
916 763551946
917 766060877
918 768575298
919 771095215
920 773620634
921 776151561
922 778688002
923 781229963
924 783777450
925 786330469
926 788889026
927 791453127
928 794022778
929 796597985
930 799178754
931 801765091
932 804357002
933 806954493
934 809557570
935 812166239
936 814780506
937 817400377
938 820025858
939 822656955
940 825293674
941 827936021
942 830584002
943 833237623
944 835896890
945 838561809
946 841232386
947 843908627
948 846590538
949 849278125
950 851971394
951 854670351
952 857375002
953 860085353
954 862801410
955 865523179
956 868250666
957 870983877
958 873722818
959 876467495
960 879217914
961 881974081
962 884736002
963 887503683
964 890277130
965 893056349
966 895841346
967 898632127
968 901428698
969 904231065
970 907039234
971 909853211
972 912673002
973 915498613
974 918330050
975 921167319
976 924010426
977 926859377
978 929714178
979 932574835
980 935441354
981 938313741
982 941192002
983 944076143
984 946966170
985 949862089
986 952763906
987 955671627
988 958585258
989 961504805
990 964430274
991 967361671
992 970299002
993 973242273
994 976191490
995 979146659
996 982107786
997 985074877
998 988047938
999 991026975
1000 994011994