0 4
1 5
2 12
3 31
4 68
5 129
6 220
7 347
8 516
9 733
10 1004
11 1335
12 1732
13 2201
14 2748
15 3379
16 4100
17 4917
18 5836
19 6863
20 8004
21 9265
22 10652
23 12171
24 13828
25 15629
26 17580
27 19687
28 21956
29 24393
30 27004
31 29795
32 32772
33 35941
34 39308
35 42879
36 46660
37 50657
38 54876
39 59323
40 64004
41 68925
42 74092
43 79511
44 85188
45 91129
46 97340
47 103827
48 110596
49 117653
50 125004
51 132655
52 140612
53 148881
54 157468
55 166379
56 175620
57 185197
58 195116
59 205383
60 216004
61 226985
62 238332
63 250051
64 262148
65 274629
66 287500
67 300767
68 314436
69 328513
70 343004
71 357915
72 373252
73 389021
74 405228
75 421879
76 438980
77 456537
78 474556
79 493043
80 512004
81 531445
82 551372
83 571791
84 592708
85 614129
86 636060
87 658507
88 681476
89 704973
90 729004
91 753575
92 778692
93 804361
94 830588
95 857379
96 884740
97 912677
98 941196
99 970303
100 1000004
101 1030305
102 1061212
103 1092731
104 1124868
105 1157629
106 1191020
107 1225047
108 1259716
109 1295033
110 1331004
111 1367635
112 1404932
113 1442901
114 1481548
115 1520879
116 1560900
117 1601617
118 1643036
119 1685163
120 1728004
121 1771565
122 1815852
123 1860871
124 1906628
125 1953129
126 2000380
127 2048387
128 2097156
129 2146693
130 2197004
131 2248095
132 2299972
133 2352641
134 2406108
135 2460379
136 2515460
137 2571357
138 2628076
139 2685623
140 2744004
141 2803225
142 2863292
143 2924211
144 2985988
145 3048629
146 3112140
147 3176527
148 3241796
149 3307953
150 3375004
151 3442955
152 3511812
153 3581581
154 3652268
155 3723879
156 3796420
157 3869897
158 3944316
159 4019683
160 4096004
161 4173285
162 4251532
163 4330751
164 4410948
165 4492129
166 4574300
167 4657467
168 4741636
169 4826813
170 4913004
171 5000215
172 5088452
173 5177721
174 5268028
175 5359379
176 5451780
177 5545237
178 5639756
179 5735343
180 5832004
181 5929745
182 6028572
183 6128491
184 6229508
185 6331629
186 6434860
187 6539207
188 6644676
189 6751273
190 6859004
191 6967875
192 7077892
193 7189061
194 7301388
195 7414879
196 7529540
197 7645377
198 7762396
199 7880603
200 8000004
201 8120605
202 8242412
203 8365431
204 8489668
205 8615129
206 8741820
207 8869747
208 8998916
209 9129333
210 9261004
211 9393935
212 9528132
213 9663601
214 9800348
215 9938379
216 10077700
217 10218317
218 10360236
219 10503463
220 10648004
221 10793865
222 10941052
223 11089571
224 11239428
225 11390629
226 11543180
227 11697087
228 11852356
229 12008993
230 12167004
231 12326395
232 12487172
233 12649341
234 12812908
235 12977879
236 13144260
237 13312057
238 13481276
239 13651923
240 13824004
241 13997525
242 14172492
243 14348911
244 14526788
245 14706129
246 14886940
247 15069227
248 15252996
249 15438253
250 15625004
251 15813255
252 16003012
253 16194281
254 16387068
255 16581379
256 16777220
257 16974597
258 17173516
259 17373983
260 17576004
261 17779585
262 17984732
263 18191451
264 18399748
265 18609629
266 18821100
267 19034167
268 19248836
269 19465113
270 19683004
271 19902515
272 20123652
273 20346421
274 20570828
275 20796879
276 21024580
277 21253937
278 21484956
279 21717643
280 21952004
281 22188045
282 22425772
283 22665191
284 22906308
285 23149129
286 23393660
287 23639907
288 23887876
289 24137573
290 24389004
291 24642175
292 24897092
293 25153761
294 25412188
295 25672379
296 25934340
297 26198077
298 26463596
299 26730903
300 27000004
301 27270905
302 27543612
303 27818131
304 28094468
305 28372629
306 28652620
307 28934447
308 29218116
309 29503633
310 29791004
311 30080235
312 30371332
313 30664301
314 30959148
315 31255879
316 31554500
317 31855017
318 32157436
319 32461763
320 32768004
321 33076165
322 33386252
323 33698271
324 34012228
325 34328129
326 34645980
327 34965787
328 35287556
329 35611293
330 35937004
331 36264695
332 36594372
333 36926041
334 37259708
335 37595379
336 37933060
337 38272757
338 38614476
339 38958223
340 39304004
341 39651825
342 40001692
343 40353611
344 40707588
345 41063629
346 41421740
347 41781927
348 42144196
349 42508553
350 42875004
351 43243555
352 43614212
353 43986981
354 44361868
355 44738879
356 45118020
357 45499297
358 45882716
359 46268283
360 46656004
361 47045885
362 47437932
363 47832151
364 48228548
365 48627129
366 49027900
367 49430867
368 49836036
369 50243413
370 50653004
371 51064815
372 51478852
373 51895121
374 52313628
375 52734379
376 53157380
377 53582637
378 54010156
379 54439943
380 54872004
381 55306345
382 55742972
383 56181891
384 56623108
385 57066629
386 57512460
387 57960607
388 58411076
389 58863873
390 59319004
391 59776475
392 60236292
393 60698461
394 61162988
395 61629879
396 62099140
397 62570777
398 63044796
399 63521203
400 64000004
401 64481205
402 64964812
403 65450831
404 65939268
405 66430129
406 66923420
407 67419147
408 67917316
409 68417933
410 68921004
411 69426535
412 69934532
413 70445001
414 70957948
415 71473379
416 71991300
417 72511717
418 73034636
419 73560063
420 74088004
421 74618465
422 75151452
423 75686971
424 76225028
425 76765629
426 77308780
427 77854487
428 78402756
429 78953593
430 79507004
431 80062995
432 80621572
433 81182741
434 81746508
435 82312879
436 82881860
437 83453457
438 84027676
439 84604523
440 85184004
441 85766125
442 86350892
443 86938311
444 87528388
445 88121129
446 88716540
447 89314627
448 89915396
449 90518853
450 91125004
451 91733855
452 92345412
453 92959681
454 93576668
455 94196379
456 94818820
457 95443997
458 96071916
459 96702583
460 97336004
461 97972185
462 98611132
463 99252851
464 99897348
465 100544629
466 101194700
467 101847567
468 102503236
469 103161713
470 103823004
471 104487115
472 105154052
473 105823821
474 106496428
475 107171879
476 107850180
477 108531337
478 109215356
479 109902243
480 110592004
481 111284645
482 111980172
483 112678591
484 113379908
485 114084129
486 114791260
487 115501307
488 116214276
489 116930173
490 117649004
491 118370775
492 119095492
493 119823161
494 120553788
495 121287379
496 122023940
497 122763477
498 123505996
499 124251503
500 125000004
501 125751505
502 126506012
503 127263531
504 128024068
505 128787629
506 129554220
507 130323847
508 131096516
509 131872233
510 132651004
511 133432835
512 134217732
513 135005701
514 135796748
515 136590879
516 137388100
517 138188417
518 138991836
519 139798363
520 140608004
521 141420765
522 142236652
523 143055671
524 143877828
525 144703129
526 145531580
527 146363187
528 147197956
529 148035893
530 148877004
531 149721295
532 150568772
533 151419441
534 152273308
535 153130379
536 153990660
537 154854157
538 155720876
539 156590823
540 157464004
541 158340425
542 159220092
543 160103011
544 160989188
545 161878629
546 162771340
547 163667327
548 164566596
549 165469153
550 166375004
551 167284155
552 168196612
553 169112381
554 170031468
555 170953879
556 171879620
557 172808697
558 173741116
559 174676883
560 175616004
561 176558485
562 177504332
563 178453551
564 179406148
565 180362129
566 181321500
567 182284267
568 183250436
569 184220013
570 185193004
571 186169415
572 187149252
573 188132521
574 189119228
575 190109379
576 191102980
577 192100037
578 193100556
579 194104543
580 195112004
581 196122945
582 197137372
583 198155291
584 199176708
585 200201629
586 201230060
587 202262007
588 203297476
589 204336473
590 205379004
591 206425075
592 207474692
593 208527861
594 209584588
595 210644879
596 211708740
597 212776177
598 213847196
599 214921803
600 216000004
601 217081805
602 218167212
603 219256231
604 220348868
605 221445129
606 222545020
607 223648547
608 224755716
609 225866533
610 226981004
611 228099135
612 229220932
613 230346401
614 231475548
615 232608379
616 233744900
617 234885117
618 236029036
619 237176663
620 238328004
621 239483065
622 240641852
623 241804371
624 242970628
625 244140629
626 245314380
627 246491887
628 247673156
629 248858193
630 250047004
631 251239595
632 252435972
633 253636141
634 254840108
635 256047879
636 257259460
637 258474857
638 259694076
639 260917123
640 262144004
641 263374725
642 264609292
643 265847711
644 267089988
645 268336129
646 269586140
647 270840027
648 272097796
649 273359453
650 274625004
651 275894455
652 277167812
653 278445081
654 279726268
655 281011379
656 282300420
657 283593397
658 284890316
659 286191183
660 287496004
661 288804785
662 290117532
663 291434251
664 292754948
665 294079629
666 295408300
667 296740967
668 298077636
669 299418313
670 300763004
671 302111715
672 303464452
673 304821221
674 306182028
675 307546879
676 308915780
677 310288737
678 311665756
679 313046843
680 314432004
681 315821245
682 317214572
683 318611991
684 320013508
685 321419129
686 322828860
687 324242707
688 325660676
689 327082773
690 328509004
691 329939375
692 331373892
693 332812561
694 334255388
695 335702379
696 337153540
697 338608877
698 340068396
699 341532103
700 343000004
701 344472105
702 345948412
703 347428931
704 348913668
705 350402629
706 351895820
707 353393247
708 354894916
709 356400833
710 357911004
711 359425435
712 360944132
713 362467101
714 363994348
715 365525879
716 367061700
717 368601817
718 370146236
719 371694963
720 373248004
721 374805365
722 376367052
723 377933071
724 379503428
725 381078129
726 382657180
727 384240587
728 385828356
729 387420493
730 389017004
731 390617895
732 392223172
733 393832841
734 395446908
735 397065379
736 398688260
737 400315557
738 401947276
739 403583423
740 405224004
741 406869025
742 408518492
743 410172411
744 411830788
745 413493629
746 415160940
747 416832727
748 418508996
749 420189753
750 421875004
751 423564755
752 425259012
753 426957781
754 428661068
755 430368879
756 432081220
757 433798097
758 435519516
759 437245483
760 438976004
761 440711085
762 442450732
763 444194951
764 445943748
765 447697129
766 449455100
767 451217667
768 452984836
769 454756613
770 456533004
771 458314015
772 460099652
773 461889921
774 463684828
775 465484379
776 467288580
777 469097437
778 470910956
779 472729143
780 474552004
781 476379545
782 478211772
783 480048691
784 481890308
785 483736629
786 485587660
787 487443407
788 489303876
789 491169073
790 493039004
791 494913675
792 496793092
793 498677261
794 500566188
795 502459879
796 504358340
797 506261577
798 508169596
799 510082403
800 512000004
801 513922405
802 515849612
803 517781631
804 519718468
805 521660129
806 523606620
807 525557947
808 527514116
809 529475133
810 531441004
811 533411735
812 535387332
813 537367801
814 539353148
815 541343379
816 543338500
817 545338517
818 547343436
819 549353263
820 551368004
821 553387665
822 555412252
823 557441771
824 559476228
825 561515629
826 563559980
827 565609287
828 567663556
829 569722793
830 571787004
831 573856195
832 575930372
833 578009541
834 580093708
835 582182879
836 584277060
837 586376257
838 588480476
839 590589723
840 592704004
841 594823325
842 596947692
843 599077111
844 601211588
845 603351129
846 605495740
847 607645427
848 609800196
849 611960053
850 614125004
851 616295055
852 618470212
853 620650481
854 622835868
855 625026379
856 627222020
857 629422797
858 631628716
859 633839783
860 636056004
861 638277385
862 640503932
863 642735651
864 644972548
865 647214629
866 649461900
867 651714367
868 653972036
869 656234913
870 658503004
871 660776315
872 663054852
873 665338621
874 667627628
875 669921879
876 672221380
877 674526137
878 676836156
879 679151443
880 681472004
881 683797845
882 686128972
883 688465391
884 690807108
885 693154129
886 695506460
887 697864107
888 700227076
889 702595373
890 704969004
891 707347975
892 709732292
893 712121961
894 714516988
895 716917379
896 719323140
897 721734277
898 724150796
899 726572703
900 729000004
901 731432705
902 733870812
903 736314331
904 738763268
905 741217629
906 743677420
907 746142647
908 748613316
909 751089433
910 753571004
911 756058035
912 758550532
913 761048501
914 763551948
915 766060879
916 768575300
917 771095217
918 773620636
919 776151563
920 778688004
921 781229965
922 783777452
923 786330471
924 788889028
925 791453129
926 794022780
927 796597987
928 799178756
929 801765093
930 804357004
931 806954495
932 809557572
933 812166241
934 814780508
935 817400379
936 820025860
937 822656957
938 825293676
939 827936023
940 830584004
941 833237625
942 835896892
943 838561811
944 841232388
945 843908629
946 846590540
947 849278127
948 851971396
949 854670353
950 857375004
951 860085355
952 862801412
953 865523181
954 868250668
955 870983879
956 873722820
957 876467497
958 879217916
959 881974083
960 884736004
961 887503685
962 890277132
963 893056351
964 895841348
965 898632129
966 901428700
967 904231067
968 907039236
969 909853213
970 912673004
971 915498615
972 918330052
973 921167321
974 924010428
975 926859379
976 929714180
977 932574837
978 935441356
979 938313743
980 941192004
981 944076145
982 946966172
983 949862091
984 952763908
985 955671629
986 958585260
987 961504807
988 964430276
989 967361673
990 970299004
991 973242275
992 976191492
993 979146661
994 982107788
995 985074879
996 988047940
997 991026977
998 994011996
999 997003003
1000 1000000004