There is a total of young programmers which are preparing for the second part of competitive season
during a winter camp in ~~Krapina~~ Zagreb. Mr. Malnar, a big promoter of order, discipline and hard work,
told the programmers to form a line and gave each of them a certain number (possibly zero) tasks. He
gave away a total of **different** tasks and he knows that the -th programmer in line will be happy if
they got exactly tasks.

In how many different ways could Mr. Malnar give out the tasks in such a way that **at least one**
programmer was happy? Two ways of giving out the tasks are considered different if there exists a
programmer and a task such that in one way that programmer received that task while in the other one
they didn't.

#### Input

The first line contains an integer from task description.

#### Output

Output the sought number of ways modulo .

#### Scoring

Subtask | Score | Constraints |
---|---|---|

No additional constraints. |

#### Sample Input 1

`1`

#### Sample Output 1

`1`

#### Sample Input 2

`2`

#### Sample Output 2

`3`

#### Explanation for Sample Output 2

Ways of giving out the tasks in which at least one programmer is happy are:

- First task to first programmer, second task to the second one.
- Second task to the first programmer, first task to the second one.
- Both tasks to the second programmer.

#### Sample Input 3

`314`

#### Sample Output 3

`192940893`

## Comments