Задачи
Северо-восточный король
Северо-восточный король
В левом нижнем углу квадратной шахматной доски $n \times n$ находится король. Он может ходить только на одну клетку вправо, вверх, или по диагонали вправо вверх. Посчитайте количество способов, которыми король может дойти до правой верхней клетки доски по модулю $1000003$.
\InputFile
Первая строка содержит количество тестов $t~(1 \le t \le 1000)$. Следующие $t$ строк содержат по одному целому числу $n~(1 \le n \le 1000)$.
\OutputFile
Для каждого значения $n$ выведите в отдельной строке искомое количество способов.
Входные данные #1
2 2 3
Выходные данные #1
3 13