lqp18_31 count rooted unlabeled trees with N nodes one by one.

But the number is so large that he is afraid that he will never stop counting.

So he asks you to tell him the number of rooted unlabeled trees with N nodes modulo 10^9+7.

Input

One line containing one integer N. (1 <= N <= 1000)

Output

One line containing the number of rooted unlabeled trees with N nodes module 10^9+7.

Example

Input:
11

Output:
1842