Một hoán vị ~P = (p_1, p_2, \dots, p_n)~ của ~n~ số nguyên dương đầu tiên được gọi là thỏa mãn xâu điều kiện ~S = s_1s_2\dots s_{n-1}~ chỉ gồm các ký tự '<', '>' nếu với mọi ~i = 1, 2, \dots, n-1~:

• Nếu ~s_i =~ '<' thì ~p_i < p_{i+1}~;

• Nếu ~s_i =~ '>' thì ~p_i > p_{i+1}~.

Yêu cầu: Cho ~n~ và xâu điều kiện ~S~, đếm số hoán vị thỏa mãn ~S~, vì kết quả có thể rất lớn, chỉ cần đưa ra phần dư trong phép chia cho ~10^9 + 7~.

Input

• Dòng 1: số nguyên ~n~ ~(2 \le n \le 3000)~;

• Dòng 2: xâu ~S~ gồm đúng ~n-1~ ký tự '<' hoặc '>'.

Output

Dòng 1: số nguyên là số hoán vị thỏa mãn xâu điều kiện ~S~, lấy modulo ~10^9 + 7~.

Scoring

Sample Input 1

4
<><

Sample Output 1

5

Sample Input 2

5
<<<<

Sample Output 2

1

Sample Input 3

18
>>>><>>><>><>>><<

Sample Output 3

788654084

Notes

Test 1: Có đúng ~5~ hoán vị thỏa mãn xâu điều kiện <>< là ~[1,3,2,4]~, ~[1,4,2,3]~, ~[2,3,1,4]~, ~[2,4,1,3]~, ~[3,4,1,2]~.

Test 2: Chỉ có đúng ~1~ hoán vị thỏa mãn xâu điều kiện <<<< là ~[1,2,3,4,5]~.

Test 3: Kết quả của ví dụ 3 được lấy modulo ~(10^9 + 7)~.

An muốn thực hiện quá trình xây dựng và tính toán trên một dãy số ~B~ không giảm như sau:

• Bắt đầu từ dãy rỗng, thực hiện ~n~ bước thêm phần tử vào dãy, số được thêm ở bước thứ ~i~ ~(1 \le i \le n)~ là ~a_i~.

• Ở mỗi bước, sau khi thêm phần tử, sắp xếp lại dãy theo thứ tự không giảm và tính tổng các phần tử có chỉ số ~1, k+1, 2k+1, 3k+1, \dots~ (chỉ số các phần tử của dãy bắt đầu từ ~1~, ~k~ là số nguyên dương cho trước).

Hãy giúp An kiểm định công việc của cậu ấy bằng cách viết chương trình tính toán tổng thu được sau mỗi bước.

Input

• Dòng 1: hai số nguyên ~n, k~ ~(1 \le k \le n \le 10^5)~;

• Dòng 2: ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(1 \le a_i \le 10^9)~.

Output

Dòng ~1 \dots n~: dòng ~i~ ghi số nguyên là tổng tính được sau khi thêm phần tử ~a_i~.

Scoring

Sample Input 1

6 3
5 6 1 1 4 7

Sample Output 1

5
5
1
7
6
6

Notes

• Thêm ~5~: dãy là ~[5]~, tổng bằng ~5~;

• Thêm ~6~: dãy là ~[5,6]~, tổng bằng ~5~;

• Thêm ~1~: dãy là ~[1,5,6]~, tổng bằng ~1~;

• Thêm ~1~: dãy là ~[1,1,5,6]~, tổng bằng ~7~;

• Thêm ~4~: dãy là ~[1,1,4,5,6]~, tổng bằng ~6~;

• Thêm ~7~: dãy là ~[1,1,4,5,6,7]~, tổng bằng ~6~.

Cho một cây gồm ~n~ đỉnh (đánh số từ ~1~ đến ~n~). Mỗi cạnh có trọng số ~w~.

Xét một đường đi đơn (không lặp đỉnh) bất kỳ gồm các đỉnh phân biệt ~u_1, u_2, \dots, u_k~ với ~k \ge 2~, trong đó mỗi cặp liên tiếp ~(u_i, u_{i+1})~ được nối bởi một cạnh của cây.

Vẻ đẹp của đường đi được định nghĩa là XOR của các trọng số trên đường đi:

~w_{(u_1,u_2)} \mathbin{\oplus} w_{(u_2,u_3)} \mathbin{\oplus} \dots \mathbin{\oplus} w_{(u_{k-1},u_k)}~.

Bạn được cho ~q~ truy vấn, mỗi truy vấn là một giá trị ~f~. Với mỗi ~f~, hãy đếm số lượng đường đi (tương ứng với các cặp đỉnh không kể thứ tự) có vẻ đẹp đúng bằng ~f~.

Input

• Dòng đầu chứa số nguyên ~n~ ~(2 \le n \le 2 \cdot 10^5)~;

• ~n-1~ dòng tiếp theo, mỗi dòng gồm ba số ~u, v, w~ ~(0 \le w < 2^{20})~ — một cạnh nối ~u~ và ~v~ với trọng số ~w~;

• Dòng tiếp theo chứa số nguyên ~q~ ~(1 \le q \le 2 \cdot 10^5)~;

• ~q~ dòng tiếp theo, mỗi dòng chứa một số nguyên ~f~ ~(0 \le f < 2^{20})~.

Output

In ra ~q~ dòng, dòng thứ ~i~ là số lượng đường đi có vẻ đẹp bằng ~f_i~.

Scoring

Sample Input 1

3
1 2 0
2 3 1
3
0
1
2

Sample Output 1

1
2
0

Sample Input 2

3
1 2 10
2 3 5
3
0
5
15

Sample Output 2

0
1
1

Notes

Trong ví dụ 1:

• Đường đi giữa cặp đỉnh ~(1,2)~ có vẻ đẹp bằng ~0~;

• Đường đi giữa cặp đỉnh ~(1,3)~ có vẻ đẹp bằng ~1~;

• Đường đi giữa cặp đỉnh ~(2,3)~ có vẻ đẹp bằng ~1~.

Trong ví dụ 2:

• Đường đi giữa cặp đỉnh ~(1,2)~ có vẻ đẹp bằng ~10~;

• Đường đi giữa cặp đỉnh ~(1,3)~ có vẻ đẹp bằng ~15~;

• Đường đi giữa cặp đỉnh ~(2,3)~ có vẻ đẹp bằng ~5~.