Đếm xâu nhị phân không có ba số 1 liên tiếp

Cho $T$ truy vấn độc lập. Mỗi truy vấn cho một số nguyên $m$. Hãy đếm số xâu nhị phân (chỉ gồm các ký tự $0$ và $1$) độ dài $m$ không chứa ba ký tự $1$ liên tiếp ($\mathtt{\text{111}}$).

Vì kết quả có thể rất lớn, in ra phần dư khi chia cho ${10}^9+7$.

Dữ liệu vào

• Dòng đầu chứa một số nguyên $T$ — số truy vấn.
• $T$ dòng tiếp theo, mỗi dòng chứa một số nguyên $m$.

Dữ liệu ra

In ra $T$ dòng, dòng thứ $i$ là số xâu nhị phân hợp lệ độ dài $m_i$ theo modulo ${10}^9+7$.

Ràng buộc

• $1\le T\le {10}^5$
• $1\le m\le {10}^6$

Ví dụ