Problem Description

BISCO, the dog owned by Takahashi, works at Disco Corporation. One day, BISCO was recognized for his 10 years of service and was given 100 square chips as a present by the president, WISCO.

BISCO arranged these chips in a 10 by 10 grid as follows:

Here, the chip in the $a$-th row from the top and the $b$-th column from the left is referred to as "chip $(a, b)$".

BISCO decided to write integers on these chips as follows:

• First, decide on sequences $P = (P_1, P_2, P_3, ..., P_{10})$ and $Q = (Q_1, Q_2, Q_3, ..., Q_{10})$. All terms in these sequences must be positive integers.
• Next, write the integer $P_i \times Q_j$ on each chip $(i, j)$.
• The integer written on each chip must be between $1$ and $N$ inclusive. Only when this condition is met, the writing is successful.

BISCO is interested in how many ways there are to decide sequences $P$ and $Q$ such that the writing is successful. For him, calculate the number of possible combinations of $(P_1, P_2, P_3, ..., P_{10}, Q_1, Q_2, Q_3, ..., Q_{10})$ that allow successful writing, modulo $1,000,000,007$.

Input Format

The input is given from the standard input in the following format:

$ N $

Output Format

Output the number of combinations of $(P_1, P_2, P_3, ..., P_{10}, Q_1, Q_2, Q_3, ..., Q_{10})$ that allow successful writing, modulo $1,000,000,007$.

Sample Input and Output

Sample Input #1

1

Sample Output #1

1

Sample Input #2

2

Sample Output #2

2047

Sample Input #3

3

Sample Output #3

118097

Sample Input #4

116

Sample Output #4

795526989

Notes/Hints

Constraints

• $ N $ is an integer between $1$ and $100,000$ inclusive.

Sample Explanation 1

When $ N = 1 $, the only way is to set all terms of sequences $P$ and $Q$ to $1$. In this case, all chips will have $1 \times 1 = 1$ written on them, and the writing is successful.

Sample Explanation 4

Output the number of desired combinations modulo $1,000,000,007$.

见题面 Input 部分

见题面 Output 部分