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