Count Valid Numeric Strings

Little Blue wants to construct a numeric string of length 10000 with the following conditions:

1. The digit 0 is not allowed (only digits 1 through 9 are permitted).
2. The string must contain the digits 3 and 7 at least once.

Determine the total number of valid numeric strings that satisfy these requirements. Since the answer can be very large, output it modulo \(10^9+7\).

inputFormat

This problem does not use any input. The length of the numeric string is fixed at 10000.

outputFormat

Output a single integer representing the number of valid numeric strings modulo \(10^9+7\).

sample

228155372