Bạn được cho $V$ đỉnh của một đồ thị và phải tạo một đồ thị vô hướng liên thông bằng cách nối các đỉnh với các cạnh đều có trọng số là 1. Các đỉnh của đồ thị được đánh số lần lượt từ $1$ đến $V$. Gọi $E$ là số cạnh của đồ thị, $d_i$ là khoảng cách nhỏ nhất từ đỉnh $1$ đến đỉnh $i$ và $S = d_1 + d_2 + ... + d_V$. Hỏi giá trị $(V+E)*S$ có thể có giá trị lớn nhất là bao nhiêu?

Input

• Dòng đầu tiên chứa số testcase $T$.

• $T$ dòng tiếp theo, mỗi dòng chứa một số nguyên dương $V$.

Output

• Gồm $T$ dòng, mỗi dòng chứa giá trị lớn nhất của $(V+E)*S$ trong mỗi testcase. Vì giá trị này có thể rất lớn nên cần in ra phần dư của giá trị đó sau phép chia lấy dư cho $10^9+7$.

Scoring

• $3\%$ số điểm có $T = 1, V \le 7$.

• $22\%$ số điểm có $T \le 10, V \le 1000$.

• $25\%$ số điểm có $T \le 1000, V \le 10^6$.

• $50\%$ số điểm có $T \le 10^5, V \le 10^9$.

1
2

3

1
5

90

1 2
2 3
3 4
4 5

1 2
2 3
3 4
4 5
3 5