Background

面对og一次次刁难，你突然发现学学组合数学还是不错的，所以你决定重回天工大的怀抱，但是离开之前og想最后让你帮忙一次，他认为你还是一个可造之才，如果你走了其他人就不能解决他的数学难题，所以长痛不如短痛，对于分组问题，他想让你直接帮忙计算n个人可以分成多少个不同非空组合，这次同样答案对1e9+7取余。

Format

Input

共一行，包含整数 n。 $0\leq n\leq1000$

Output

共一行，包含一个整数，表示答案。

Samples

4

15

Limitation

1s, 1024KiB for each test case.