NPC2015D - Eefun is not so Fun

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 (109+7)

Example

Input 1:
2
Output 1:
2

Input 2:
5
Output 2:
6

Constraints:

  • 1 ≤ N ≤ 1018

Added by:Louis Arianto
Date:2015-10-10
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:NPC Schematics 2015

hide comments
2015-11-15 17:46:02 Akhilesh Anandh
Same as this problem:
http://www.spoj.com/problems/LOCKER/
2015-11-14 09:31:18 Alex Anderson
Problem missing constraint: The numbers used to sum must be positive. Else, 2 = -6 + -6 + 14 ==> unbounded answer.
2015-11-12 20:00:02 :.Mohib.:
350th AC with nice one ;)
2015-10-22 07:37:38 Daksh
AC :)

Last edit: 2015-10-31 20:11:19
2015-10-18 18:23:08
Explain input 1, how is the product 2 ? It should be 1 * 1 = 1 since 2 * 0 = 0 ?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.