Score : 300 points
How many integer sequences A_1,A_2,\ldots,A_N of length N satisfy all of the following conditions?
The answer can be very large, so output it modulo 10^9 + 7.
Input is given from Standard Input in the following format:
N
Print the answer modulo 10^9 + 7.
2
2
Two sequences \{0,9\} and \{9,0\} satisfy all conditions.
1
0
869121
2511445