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

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

Вхідні дані

Перший рядок входу містить число T (1 ≤ T ≤ 10000) — кількість тестів. Наступні T рядків містять по одному цілому числу n (1 ≤ n ≤ 10^6).

Для кожного n виведіть одне ціле число — відповідь до задачі.

Приклади