Випадкові прогулянки
"Thorfun Company Limited", також відома як "thorfun.com", є соціальною мережею для блогерів, письменників та читачів, заснованою чотирма випускниками. Один із них захоплюється обчислювальними задачами. Одного дня він натрапив на щось дуже цікаве, адже це рішення різних задач, і "Випадкові прогулянки" є однією з них. Уявіть одномірну лінію, де ви стоїте в початковій точці (позиція 0). На кожному кроці ви можете рухатися або вліво, або вправо на одиницю.
Спочатку розглянемо базову версію задачі. Ви можете рухатися, як забажаєте, протягом 2N кроків, але повинні завершити шлях у початковій точці. Скільки різних шляхів ви можете пройти? Рішення дуже просте. Ви починаєте і закінчуєте в тій самій точці, це означає, що ви повинні зробити однакову кількість кроків вліво і вправо. Вибір N кроків вправо і N кроків вліво з 2N кроків є можливим.
Задача "Випадкові прогулянки" схожа на базову, але з додатковою умовою: під час прогулянки ви не повинні заходити в негативні цілі числа. Наприклад, якщо N = 1, ви можете йти по шляху 0→1→0, але не можете йти по шляху 0→-1→0. Ваше завдання — написати програму для обчислення кількості шляхів, які відповідають цим правилам. Крім того, результат може бути дуже великим, тому виведіть результат за модулем 1000000007 (просте число).
Вхідні дані
Перша строка введення містить кількість тестових випадків T ≤ 1000.
Кожен тестовий випадок — це рядок, що містить ціле число N (1 ≤ N ≤ 1000000).
Вихідні дані
Для кожного тестового випадку виведіть ціле число, що вказує кількість шляхів, які ви можете пройти за модулем 1000000007.