• Kí hiệu u(n) là số nguyên nhỏ nhất có tổng các chữ số bằng n.

• Kí hiệu g(k)=u(1)+u(2)+...+u(k).

Gọi f(i) là số thứ i trong dãy fibo với f(0)=0, f(1)=1 và f(i)=f(i-1)+f(i-2).

Yêu cầu: Tính z(q)=g(f(2))+g(f(3))+...+g(f(q)) với số q nguyên dương cho trước. Vì đáp án có thể lớn, nên ta cần mod 10⁹+7 trước khi in ra.

Input:

• Dòng thứ nhất chứa số t (1<=t<=50) - Thể hiện số lượng testcase của bài toán.

• t dòng tiếp theo, mỗi dòng chứa số nguyên dương q (2<=q<=100).

Output:

• Ứng với mỗi testcase, in ra đáp án cần tìm.