Problem #23
Crack The Safe
There is a safe with its 10-digit keypad (as shown below) which is to be cracked.
9 8 7
6 5 4
3 2 1
0
The restriction of the password for that safe is that every pair of neighboring keys in the password is adjacent on the keypad. Adjacent keys are the ones that share a common edge. You know that the password is 10^9 digits long. Let total number of possible passwords for this safe be X. Since X can be very large, enter X \mod 10^9+7.