Числа Каталана

1000 мс · 256 МБ · всё или ничего

Выведите $n$ -е число Каталана по модулю $10^9 + 7$ :

C_n = \frac{1}{n+1} \binom{2n}{n}.

В первой строке $q$ ( $1 \le q \le 10^5$ ). В каждой из следующих $q$ строк — число $n$ ( $0 \le n \le 10^6$ ).

Для каждого запроса выведите $C_n$ по модулю $10^9 + 7$ .

ввод

1
0

вывод

Разбор идеи от автора задачи. Сначала попробуйте сами.

Войдите, чтобы отправлять решения.