Eefun is a young man who lives at Schematics village. His village will be visited by a school named Enpeesee. Eefun want to prepare a game for the students. After thinking for several days, he came up with a game called "Funny Eefun is fun".

Enpeesee's students have finally arrived. However, none of the students want to play with Eefun. Eefun gets disappointed.

Seeing tears on Eefun's face, one of the student, Andee, decide to play with Eefun. Eefun happily explains his game to Andee. Eefun currently has a number N. Then, Andee can think about numbers which sum is equal to N. However, the product of Andee's number should be maximum. Andee tried this game several times, but he never answered it right. Therefore, Andee gets frustrated and think that the game's title should be "Eefun is not so Fun". As Andee's best friends, help him to beat this game. 

Input

Input contains a number N

Output

Output a number, the maximum product of Andee's number. As the number can be pretty large, output it with modulo 1000000007 (10⁹+7)

Example

Input 1:
2
Output 1:
2
Input 2:
5
Output 2:
6