lqp18_31 count unrooted 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 unrooted 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 unrooted unlabeled trees with N nodes modulo 10^9+7

Example

Input:
10

Output:
106