Jerry needs to delay his math test again, so this time he decides to tell a sob story.

Jerry's sob story is exactly ~N~ seconds long. He can divide his sob story into multiple segments with dramatic pauses in between, where each segment's length in seconds is a positive integer. The sadness value of a segment is equal to its length in seconds. Since sadness is all-encompassing, the total sadness value of his story is the sadness values of all the segments multiplied together.

For example, if Jerry's sob story is 10 seconds long, then he can divide it into segments of 3, 3, and 4 seconds, the product of which is 36 sadness value.

Jerry wants to maximize the sadness value so Ing will be too busy crying to give him a test. What is the maximum sadness value he can extract from his sob story?

Input Specification

The input will be a single integer ~N~ ~(2 \le N \le 1\,000)~.

Output Specification

The maximum sadness value that can be obtained from a sob story that is ~N~ seconds long. Because the maximum sadness value may be extremely large (Jerry is a great storyteller!), output it mod ~10^9 + 7~.

Sample Input 1

10

Sample Output 1

36

Sample Input 2

5

Sample Output 2

6