Có ~ n ~ thành phố, các thành phố được đánh số từ ~ 0 ~ đến ~ n-1 ~, giữa thành phố thứ ~ i-1 ~ đến thành phố thứ ~ i ~ có ~ a_i ~ ~ ( i = 1…n-1) ~ con đường khác nhau. Hãy cho biết có bao nhiêu cách đi từ thành phố 0 đến thành phố ~ n-1 ~. Số lượng cách đi có thể rất lớn nên kết quả sẽ được lấy dư cho ~ 1234567 ~.

Dữ liệu vào

Dòng đầu tiên ghi số nguyên ~ t ~ ~ ( t ≤ 1000 ) ~ cho biết số lượng bộ dữ liệu, mỗi bộ dữ liệu có cấu trúc:

• Dòng đầu là số nguyên dương ~ n ~ ~ ( 2 ≤ n ≤ 100) ~ cho biết số lượng thành phố
• Dòng tiếp theo ghi ~ n-1 ~ số nguyên dương, trong đó số thứ ~ i ~ ~ ( i = 1…n-1) ~ ghi giá trị ~ a_i ~ ~ (a_i≤1000) ~.

Kết quả

Mỗi bộ dữ liệu trong Input ghi một số nguyên trên một dòng.

Ví dụ:

Input 1

2
3
1 3
4
2 2 2 

Output 1

3
8