Північно-східний король Hard#3175
У нижньому лівому куті шахівниці розміром n \times n знаходиться король. Король може рухатися лише на одну клітинку вправо, на одну клітинку вгору або на одну клітинку по діагоналі вгору-вправо. Обчисліть кількість різних способів, якими король може дістатися до верхнього правого кута дошки по модулю .
Перший рядок містить одне ціле число (1 \leq T \leq 10000) — кількість тестів. Кожен з наступних рядків містить одне ціле число (1 \leq n \leq 10^6).
Для кожного тесту виведіть одне число — відповідь на задачу.
Приклад 1