Counting Constrained Numbers

Under the dazzling starry sky, Genius_Star is challenged with a mathematical problem by Bai Guo. A positive integer with n digits is called constrained if and only if:

• The number’s digits are drawn exclusively from the set \(\{0,1,2,3,4\}\) and each of these five digits appears at least once.
• All occurrences of \(0\) appear before any occurrence of \(1\). That is, if the digit \(0\) is present at some position and \(1\) at another, then all \(0\)s must come before all \(1\)s (when looking at their positions in the number).
• All occurrences of \(3\) appear before any occurrence of \(4\).
• The most significant digit (the first digit) is not \(0\).

Your task is to compute the number of n-digit constrained numbers modulo \(10^9+7\).

Note: The ordering restrictions imply that once the positions of the digits \(0\) and \(1\) (or \(3\) and \(4\)) are chosen, their internal order is fixed (i.e. all chosen positions for \(0\) will be filled with \(0\) and the remainder with \(1\), and similarly for \(3\) and \(4\)).

inputFormat

The input consists of a single integer n representing the number of digits.

Constraints: \(1 \le n \le 1000\) (Note: since each of the 5 digits must appear at least once, if \(n < 5\) the answer is 0.)

outputFormat

Output a single integer – the number of constrained n-digit numbers modulo \(10^9+7\).

sample

5

1