Північно-східний король

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

Вхідні дані

Перший рядок містить кількість тестів $t(1\le t\le 1000)$. Наступні $t$ рядків містять по одному цілому числу $n(1\le n\le 1000)$.

Вихідні дані

Для кожного значення $n$ виведіть шукану кількість способів.

Приклади