B. Carlitos and the end of the world!
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Carlitos "Curious" Nunes is visiting the Luxor Museum with his parents. He is fond of games, and has read about ancient Egyptian games like Senet. Unfortunately, Carlitos did not found this game on Luxor. However, he found a papyrus that tells a myth about the end of the world. For him, this myth seemed like a funny game.

When the pyramid of Giza was finished, the main priest collected $$$100$$$ precious stones of different colors. In each of the following years, during the Wepet-Renpet Festival, the priest carried out the following ritual:

  1. First, he arranged the stones in a single pile.
  2. While there was a pile with at least two stones: he picked one such pile, and divided it into two, by choosing any nonempty subset of stones to form a new pile.
Furthermore, the priest did not repeat the exact same ritual of a previous year. We make the following two remarks. First, two piles of stones are considered the same if they contain the same set of stones. Second, we consider two rituals equal if in step 2 we make the same sequence of choices and divide the piles in the same way. Finally, the myth says that, when the priest can not make the ritual without repeating one of a previous year, the world will end!

As a curious kid, Carlitos was thinking about how many years the world will last, if this ritual started today. Moreover, he wanted to calculate this for different numbers of stones. Since you are an experience programmer, Carlitos asked you to write a program that calculates this number. He wants to check whether his calculations are correct.

Input

A single line containing an integer $$$N$$$ ($$$1 \leq N \leq 5 \cdot 10^5$$$), indicating the number of stones.

Output

An integer, the number of years the world will last. Since this number can be huge, print it mod $$$10^9 + 7$$$.

Example
Input
10
Output
571911986