Khôi đang đi du lịch vòng quanh vũ trụ và muốn đi tham quan lần lượt từ hành tinh thứ \(1\) đến hành tinh thứ \(n\).

Biết rằng từ hành tinh thứ \(i\) đến hành tinh thứ \(i+1\) có \(A_i\) cổng dịch chuyển không gian khác nhau.

Hỏi có bao nhiêu cách để Khôi đi du hành không gian lần lượt từ thành tinh thứ \(1\) đến hành tinh thứ \(n\).

Input

• Số test \(q ( q \le 1000)\)
• Mỗi test gồm 1 số nguyên dương \(n ( n \le 1000)\) và \(n-1\) số nguyên dương \(A_1, A_2, ... , A_{n-1} ( A_i \le 1000)\)

Output

• Mỗi test trên \(1\) dòng, phần dư của số cách du hành không gian khi chia cho 1234567.

Example

2
3
1 3
4
2 2 2

3
8