L. Many recursions
time limit per test
0.25 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

It was a long time since Informikas has had something to do with recursions and this had to be fixed. For that reason he decided to come up with some recursion and later solve it all by himself.

The first recursion Informikas managed to come up was

"Nah, too easy", he told to himself, crumpled the paper and threw it to a trash can.

"Squaring is overrated. Still too easy", he thought while the paper was flying towards a trash can.

"Oh no, what have I done! This recursion has no terminating condition! It's too hard even for me!", Informikas shouted out loud.

Could you be so kind and, given the value of a, help out Informikas by finding the value of h(0).

Input

Single integer a (0 ≤ a ≤ 1018).

Output

Calculate the integer part of h(0). As the answer can be quite a large number, output it modulo 109 + 7 (1000000007). In cases when the recursion goes infinitely long, output "Nobody got time for that" (without quotation marks).

Examples
Input
0
Output
1
Input
1
Output
2