Северо-восточный король

В левом нижнем углу квадратной шахматной доски $n\times n$ находится король. Он может ходить только на одну клетку вправо, вверх, или по диагонали вправо вверх. Посчитайте количество способов, которыми король может дойти до правой верхней клетки доски по модулю $1000003$.

Входные данные

Первая строка содержит количество тестов $t(1\le t\le 1000)$. Следующие $t$ строк содержат по одному целому числу $n(1\le n\le 1000)$.

Выходные данные

Для каждого значения $n$ выведите в отдельной строке искомое количество способов.

Примеры