F. Classroom
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

- Imagine you have $$$n$$$ students lined up, each with an integer value. Your challenge is to split this line into one or more consecutive groups (the number of groups $$$m$$$ is not fixed) such that each group meets a special "hull" condition:

  • The first group starts with student $$$1$$$ and the last group ends with student $$$n$$$.
  • The groups are consecutive; if group $$$j$$$ covers students from index $$$l_j$$$ to $$$r_j$$$, then for every $$$1 \le j \lt m$$$, we have $$$r_j + 1= l_{j+1}$$$.
  • For each group $$$j$$$ (where $$$1 \le j \le m$$$), if the group includes students with index $$$l_j, l_j+1, \dots, r_j$$$, then the sum $$$l_j + l_j+1 + \dots + r_j$$$ must be divisible by $$$j$$$.

- Your task: Compute the number of ways to form such a segmentation of the students, and output your answer modulo $$$10^9 + 7$$$.

Input

The first line contains an integer $$$n$$$ ($$$1 \le n \le 5*10^3$$$) — the number of students.

Output

Print a single integer: the number of valid segmentations, modulo $$$10^9 + 7$$$.

Examples
Input
7
Output
5
Input
5
Output
5