Теоретик изучает способы разложить натуральное число n на сумму неотрицательных слагаемых. Два разложения считаются одинаковыми, если отличаются только порядком слагаемых.

Требуется определить, сколькими различными способами можно представить число n в таком виде.

Иными словами, нужно посчитать количество разбиений числа n на неотрицательные слагаемые без учёта порядка.

Ответ выведите по модулю 1000000007.

Входные данные

В единственной строке задано целое число n (1 <= n <= 5000).

Выходные данные

Выведите количество разложений числа n в сумму неотрицательных слагаемых без учёта порядка по модулю 1000000007.

Ограничения

1 <= n <= 5000
Ограничение на модуль ответа: 1000000007

Примеры

Пример 1

Входные данные

4

Выходные данные

5

Пояснение

У числа 4 ровно 5 разбиений.

Пример 2

Входные данные

1

Выходные данные

1

Пример 3

Входные данные

2

Выходные данные

2