Північно-східний король#3174
У лівому нижньому кутку шахової дошки розміром n \times n знаходиться король. Король може ходити на одну клітинку праворуч, на одну клітинку вгору або по діагоналі вгору-праворуч. Порахуйте кількість способів, якими король може дістатися до верхнього правого кута дошки за модулем .
У першому рядку міститься число тестів (1 \leq t \leq 1000). Кожен з наступних рядків містить одне ціле число (1 \leq n \leq 1000).
Для кожного тесту виведіть кількість можливих шляхів досягти верхнього правого кута дошки розміром n \times n за модулем .
Приклад 1