Ваше завдання — побудувати вежу, ширина якої дорівнює 2, а висота — n.

У вас є необмежений запас блоків, ширина та висота яких є цілими числами.

Наприклад, ось деякі можливі рішення для n=6:

Дано ~n~. Скільки різних веж можна побудувати? Дзеркальні та повернуті вежі враховуються окремо, якщо вони виглядають по-різному.

Обмеження

• ~1 \le t \le 100~
• ~1 \le n \le 10^6~

Формат вхідних даних

Перший рядок містить ціле число ~t~: кількість тестів.

Після цього йде ~t~ рядків, і кожен рядок містить ціле число ~n~: висоту вежі.

Формат вихідних даних

Для кожного тесту виведіть кількість веж за модулем ~10^9+7~.

Приклад вхідних даних

3
2
6
1337

Приклад вихідних даних

8
2864
640403945