Случайные блуждания
Компания "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.