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