1 0
2 1
3 0
4 17
5 118
6 81
7 129
8 417
9 0
10 49
11 124
12 945
13 1498
14 177
15 1782
16 1857
17 1958
18 729
19 3917
20 401
21 7398
22 8721
23 6466
24 4833
25 68
26 14049
27 0
28 3889
29 9718
30 26649
31 24648
32 16001
33 3294
34 6537
35 32457
36 41553
37 34857
38 33601
39 26703
40 32801
41 9310
42 62721
43 76070
44 50417
45 12393
46 88513
47 41316
48 50625
49 74413
50 20249
51 5994
52 136529
53 96357
54 59049
55 67882
56 21345
57 134946
58 29705
59 118652
60 177201
61 203316
62 234369
63 172773
64 179457
65 162093
66 105273
67 254402
68 284049
69 74547
70 103849
71 314320
72 193185
73 64316
74 148897
75 189432
76 90673
77 370753
78 273105
79 193790
80 193601
81 0
82 455929
83 560170
84 295569
85 26168
86 363961
87 443988
88 324065
89 457908
90 496449
91 438532
92 365873
93 639495
94 57913
95 548982
96 31617
97 566580
98 262033
99 372519
100 522001
101 943848
102 775521
103 640972
104 890145
105 523368
106 701729
107 1164912
108 531441
109 650842
110 543049
111 1310715
112 1114817
113 741961
114 210033
115 981032
116 480785
117 578826
118 1415065
119 1684541
120 1570401
121 676272
122 751041
123 750573
124 1374001
125 496068
126 898857
127 1813182
128 424449
129 506223
130 217649
131 1350875
132 8721
133 1697538
134 691449
135 1554957
136 2469793
137 2278450
138 1511001
139 2163399
140 2066801
141 340119
142 1815337
143 928339
144 123201
145 1580018
146 908129
147 2457594
148 511569
149 660669
150 2748249
151 407552
152 1328353
153 3167505
154 1179105
155 2172382
156 1003185
157 290767
158 2248665
159 2374056
160 899201
161 3657232
162 531441
163 4203121
164 3311569
165 2205468
166 2300105
167 1874244
168 1205793
169 2481573
170 14849
171 1917270
172 42737
173 686640
174 495585
175 5037182
176 3289025
177 289953
178 101825
179 4183233
180 2747601
181 2188836
182 1256537
183 1269864
184 3470177
185 385043
186 5886513
187 28686
188 5000881
189 5530923
190 6207449
191 1505656
192 5191425
193 2544708
194 1160129
195 5995107
196 5101457
197 3392934
198 2123577
199 3454444
200 3044001
201 7474815
202 6499561
203 4437998
204 1677105
205 138618
206 4885505
207 3725190
208 3919425
209 657353
210 2624049
211 3261430
212 2788305
213 1409022
214 9210569
215 7595032
216 7144929
217 2822970
218 8158441
219 9937809
220 532401
221 2369064
222 10454265
223 7427464
224 9205121
225 9179568
226 518905
227 7035641
228 8296209
229 9462970
230 6480649
231 12216042
232 4249377
233 8108403
234 9326097
235 6760582
236 12995185
237 1693629
238 5437401
239 6350711
240 2628801
241 10887419
242 13574273
243 0
244 5719441
245 11162268
246 8396217
247 13844288
248 8301665
249 430299
250 15101249
251 4368909
252 8043057
253 15474838
254 13169401
255 15794757
256 3208193
257 3401141
258 15753177
259 16915664
260 16949201
261 11478105
262 6869649
263 17601804
264 7056801
265 2422343
266 14889905
267 1242378
268 18479217
269 3031095
270 11868849
271 16265423
272 7342913
273 6250635
274 11831329
275 5791182
276 12752721
277 170912
278 13289521
279 12110148
280 15717601
281 3028059
282 8822817
283 3809466
284 21545457
285 2792043
286 14405537
287 14433900
288 3715713
289 18493334
290 14083449
291 3357585
292 13362001
293 151191
294 496665
295 1926357
296 5940769
297 21966228
298 19504705
299 22899522
300 566001
301 3777931
302 7233513
303 14466762
304 27810241
305 13633743
306 1948617
307 5946593
308 10482257
309 6994242
310 17729049
311 23431987
312 11005281
313 8230338
314 26985169
315 22641282
316 12516209
317 17506645
318 1237113
319 29887444
320 12038401
321 7340976
322 17856353
323 7699174
324 17537553
325 18659943
326 456409
327 9232218
328 268961
329 5730030
330 2672649
331 25403922
332 16932081
333 11213478
334 15540361
335 12336082
336 19621953
337 21232351
338 7174241
339 36581517
340 33798801
341 1827587
342 4135617
343 3487606
344 14963681
345 40704768
346 38179033
347 8512954
348 40821489
349 2510011
350 7954249
351 8463690
352 9826177
353 35204693
354 7009929
355 43461757
356 2466449
357 36966726
358 1389049
359 12639675
360 8871201
361 44257102
362 39145241
363 24188895
364 27387441
365 15335718
366 20950569
367 13810213
368 11278017
369 43478289
370 47433849
371 33669536
372 43573329
373 45414618
374 31643033
375 35451432
376 19561569
377 3389655
378 29189889
379 22179841
380 42631601
381 51133275
382 37999841
383 11037680
384 23031297
385 15282543
386 46035913
387 52996113
388 5978385
389 50872256
390 44479449
391 55847765
392 1178529
393 25353243
394 34251217
395 34447482
396 2117745
397 12174802
398 57238777
399 495585
400 6088001
401 62888833
402 6093441
403 57777359
404 39954065
405 65367243
406 55783529
407 31327151
408 38518497
409 11140754
410 63527049
411 68106015
412 11723953
413 16910997
414 34911081
415 70218907
416 29633665
417 37023372
418 40083697
419 10234078
420 24088401
421 63527640
422 55452497
423 46514574
424 54393889
425 780943
426 63292401
427 43190248
428 20342065
429 77529258
430 25953649
431 32162947
432 10294209
433 40156856
434 71023521
435 42713082
436 61688849
437 67398240
438 56071737
439 17996808
440 1064801
441 63256059
442 55888953
443 43364830
444 40235697
445 84459018
446 74501633
447 8846604
448 32779009
449 87007672
450 7932249
451 82033647
452 29362001
453 54097740
454 60558161
455 39303507
456 72727713
457 77091790
458 48701897
459 18580752
460 30841201
461 22030271
462 47733057
463 40402309
464 60678721
465 56222343
466 5219209
467 38330429
468 17210961
469 20698219
470 79648849
471 95699691
472 60947425
473 81443191
474 4505625
475 68736682
476 37337393
477 9138015
478 48157553
479 63027781
480 4745601
481 104524956
482 69506337
483 80869158
484 90899153
485 44671168
486 43046721
487 112915336
488 70177057
489 85507056
490 9335449
491 14498251
492 29508273
493 73052684
494 53358561
495 117994482
496 78524609
497 29430693
498 21747393
499 21183551
500 2610001
501 5424354
502 12857233
503 53181690
504 14329953
505 103260118
506 23381801
507 7373133
508 40920497
509 22478970
510 707049
511 11377047
512 116516865
513 74815083
514 50260985
515 132719657
516 47751633
517 113280814
518 35981073
519 92074779
520 123690401
521 89431216
522 56944377
523 87246340
524 115141745
525 28339443
526 3932385
527 22646080
528 48410433
529 136717523
530 56408649
531 83418012
532 34899729
533 4087287
534 41851377
535 144129457
536 20687585
537 106026381
538 5451025
539 42128651
540 38322801
541 27105726
542 65866017
543 26370279
544 34809473
545 123453643
546 108580473
547 84164158
548 43892689
549 78107247
550 62035249
551 24824859
552 111728673
553 97245578
554 71769601
555 62325882
556 35490673
557 114411702
558 95260617
559 50210553
560 90443201
561 162217080
562 155244641
563 148355570
564 151065297
565 68288968
566 123929105
567 44109603
568 158942049
569 29286433
570 175164849
571 123650053
572 35147121
573 50502528
574 115146441
575 130771932
576 145270017
577 95035365
578 45867369
579 86810076
580 188347601
581 157288598
582 76643145
583 79731525
584 176963233
585 101234043
586 119722153
587 193012647
588 76288689
589 109933824
590 63519449
591 79035048
592 202640449
593 51280864
594 138154977
595 27335857
596 169569233
597 138177468
598 123068481
599 94855846
600 137132001
601 185023262
602 45726193
603 151872570
604 219947889
605 194900993
606 167002209
607 214289820
608 95413121
609 15704793
610 121632049
611 87313534
612 63540369
613 68084687
614 143877401
615 137225907
616 21390625
617 113853162
618 73485873
619 195331643
620 57316401
621 91486584
622 189339297
623 204453254
624 31009473
625 175476068
626 203585225
627 78243570
628 94109649
629 247655529
630 13472649
631 137071502
632 226217057
633 241923132
634 187440841
635 68387457
636 12071025
637 149844334
638 224389929
639 218753217
640 130572801
641 136536
642 163333233
643 241226597
644 57233745
645 249975018
646 107828057
647 230475637
648 94065057
649 101340848
650 5388249
651 265259637
652 156151473
653 50555263
654 242551017
655 233726382
656 71113025
657 107039070
658 98289657
659 213597719
660 214557201
661 115792661
662 28619593
663 2308203
664 157576417
665 200555843
666 107548641
667 243754462
668 173525105
669 270360990
670 172208849
671 115874322
672 65937537
673 68589471
674 114674369
675 128510307
676 118052561
677 270184610
678 43349337
679 299469705
680 137453601
681 249787422
682 122056097
683 316830043
684 286252785
685 1870293
686 293864545
687 290897811
688 253183937
689 159438340
690 2818449
691 58960960
692 215062609
693 129232746
694 99963769
695 170070357
696 53527905
697 157108846
698 48189929
699 283422159
700 125654001
701 195035027
702 25095825
703 2807082
704 184622849
705 10121868
706 31292753
707 125513372
708 174609
709 249942355
710 343131049
711 255262995
712 108572321
713 177996834
714 6899985
715 21563532
716 180850225
717 139081536
718 348034713
719 84992993
720 172750401
721 62928183
722 39630969
723 331596747
724 265354769
725 271722068
726 303701049
727 14859156
728 291224033
729 0
730 177682649
731 75960257
732 180252081
733 118776789
734 313987593
735 270174582
736 53468545
737 195635108
738 378573345
739 258363271
740 38502801
741 298090989
742 229005193
743 264882475
744 261864225
745 179765018
746 17325113
747 403661880
748 29606065
749 327916741
750 384366249
751 196378242
752 334828737
753 140073840
754 358520633
755 318257507
756 260661969
757 430162225
758 362330073
759 414366759
760 139887201
761 410464378
762 116943345
763 323645423
764 333195761
765 310056093
766 126368561
767 412501475
768 272817153
769 433942858
770 229208849
771 207746748
772 268421393
773 205028204
774 327234249
775 2279932
776 170006433
777 298419309
778 464120577
779 413086425
780 333335601
781 15864313
782 147139881
783 368288613
784 363692865
785 237800293
786 468327825
787 322800645
788 76921489
789 51311853
790 438714449
791 193310948
792 44283105
793 172290745
794 210168633
795 426941982
796 138166577
797 371518365
798 158579289
799 405916724
800 332176001
801 158978133
802 299505305
803 427866554
804 426645009
805 491130118
806 125497225
807 142405668
808 502763553
809 233272726
810 472451049
811 395265183
812 55156145
813 153627759
814 128901865
815 200344032
816 283636161
817 295686552
818 50450977
819 69078582
820 258608401
821 152344763
822 531739377
823 363518280
824 353924449
825 219624318
826 491912929
827 162233420
828 563995953
829 14343361
830 60665649
831 450026415
832 385194241
833 304275319
834 49270113
835 535425957
836 311378257
837 535200453
838 289984881
839 325046222
840 70128801
841 492607807
842 463760137
843 516674727
844 260877105
845 284855268
846 17928297
847 79385568
848 273227841
849 604533024
850 45844249
851 480783571
852 469629009
853 437884141
854 606169769
855 277718382
856 389376993
857 594028696
858 559003329
859 122659190
860 164673201
861 465809238
862 323753417
863 51997479
864 298768257
865 283625093
866 193318921
867 79963335
868 20794001
869 329708504
870 365514849
871 42968565
872 303253281
873 195753267
874 174104217
875 452658932
876 486942705
877 337980894
878 640276241
879 620649621
880 2129601
881 442591497
882 507851289
883 530715674
884 596373137
885 177873543
886 124777161
887 538862260
888 327153249
889 77366523
890 402392449
891 235959804
892 200842801
893 383224576
894 553243689
895 29806607
896 392254977
897 645202962
898 420842321
899 157361973
900 219698001
901 255019827
902 253324641
903 234384786
904 716321697
905 527253243
906 462462993
907 691336264
908 253215857
909 665625843
910 123182049
911 369522556
912 505003329
913 403473317
914 592454809
915 34318782
916 681973073
917 143154009
918 181929969
919 425712049
920 217458401
921 613518651
922 601427985
923 405340438
924 104230449
925 196276568
926 107790113
927 215143938
928 764122241
929 136347475
930 170450649
931 575970384
932 149537617
933 259223814
934 619925697
935 419099957
936 263612961
937 45147474
938 547581057
939 230154561
940 641178801
941 99669782
942 163049625
943 134857378
944 837721025
945 521520768
946 533410353
947 17111346
948 308297745
949 196198161
950 76947249
951 640897947
952 50244961
953 787271397
954 178780689
955 340888257
956 136601009
957 441135396
958 344209409
959 625843258
960 879891201
961 376185034
962 757981753
963 747522432
964 281858257
965 63994218
966 484905177
967 411668342
968 272998049
969 376111890
970 852727849
971 163900919
972 272629233
973 886549191
974 161886601
975 567928557
976 849066561
977 111369210
978 363417705
979 690609154
980 464195601
981 399867435
982 254781873
983 526096688
984 812420577
985 614645168
986 927815825
987 283437657
988 196625393
989 144878687
990 52984449
991 768944651
992 928698753
993 224434908
994 640900369
995 665796732
996 443783313
997 128118491
998 95229169
999 549136017
1000 855220001