Có một chiếc bánh hình tròn. Cậu thực hiện \(k\) lần cắt, tất cả các đường cắt đều không trùng nhau và đi qua tâm của chiếc bánh. Hỏi sau khi cắt chiếc bánh được chia thành bao nhiêu phần.

Input

• Dòng đầu tiên gồm số nguyên dương \(q\) là số truy vấn trong bộ test (\(q \le 10^6\)).
• Dòng tiếp theo gồm \(q\) số tự nhiên, số tự nhiên thứ \(i\) là \(k_i\) (\(k_i \le 10^9\)).

Output

• In ra \(q\) số nguyên cách nhau một dấu cách. Số nguyên thứ \(i\) mô tả kết quả của truy vấn: nếu cắt chiếc bánh \(k_i\) lần thì chiếc bánh được chia thành bao nhiêu phần. Vì kết quả có thể rất lớn nên bạn chỉ cần in ra phần dư của kết quả khi chia cho \(10^9 + 7\).

Example

2
1 2

2 4

Scoring

• Subtask 1 (\(60\%\)): \(k_i \le 1000\), \(q \le 1000\).
• Subtask 2 (\(40\%\)): \(1000 < k_i \le 10^9\), \(q \le 10^6\).