Кролик Крис с детства увлекается массивами. Сейчас он занят исследованием массивов длиной n, которые содержат только целые числа от 1 до n. Он не силен в математике — поэтому некоторые простые вещи выводят его из себя. Вот, к примеру, вчера он задался целью вычислить, сколько всего есть разных красивых массивов? Крис считает, что массив красив, если выполняется одно из двух:
- каждый элемент, начиная со второго, не больше предыдущего
- каждый элемент, начиная со второго, не меньше предыдущего
Крис, изрядно разозлившись на себя и на математику, пришел просить помощи у Стьюи и Брайана. Но те просто посмеялись и сказали, что ответ слишком прост и неинтересен. Помогите кролику Крису все же найти ответ.
Выходные данные
В единственной строке требуется вывести ответ. Так как он может быть достаточно большим — нужно вывести его по модулю 1000000007.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
|
4
|
|
2
|
3
|
17
|