Cho một số nguyên dương \(n\), có bao nhiêu cách chọn \(2\) số nguyên không âm bé hơn hoặc bằng \(n\) có tổng bằng \(n\)? \((1\leq n\leq10^{1000})\). Ví dụ \(n=20\), chúng ta có 21 cách: \(0+20,1+19,2+18,3+17,...,20+0.\) Trong bài toán này, số \(n\) sẽ có một vài vị trí không xác định, được thay thế bằng kí hiệu '*'. Chú ý, chữ số bắt đầu của \(n\) chắc chắn khác '*' và '0'.

INPUT

Dòng đầu chứa một số nguyên \(T\) là số test của bài toán.

\(T\) dòng sau, mỗi dòng chứa một số nguyên dương \(n\)

OUTPUT

In ra kết quả module \(10^9+7\)