- Practice
- Mathematics
- Fundamentals
- Connecting Towns

# Connecting Towns

# Connecting Towns

Gandalf is travelling from **Rohan** to **Rivendell** to meet Frodo but there is no direct route from **Rohan** (T_{1}) to **Rivendell** (T_{n}).

But there are towns T_{2},T_{3},T_{4}...T_{n-1} such that there are N_{1} routes from Town T_{1} to T_{2}, and in general, N_{i} routes from T_{i} to T_{i+1} for i=1 to n-1 and 0 routes for any other T_{i} to T_{j} for j ≠ i+1

Find the total number of routes Gandalf can take to reach Rivendell from Rohan.

**Note**

Gandalf has to pass all the towns T_{i} for i=1 to n-1 in numerical order to reach T_{n}.

For each T_{i} , T_{i+1} there are only N_{i} distinct routes Gandalf can take.

**Input Format**

The first line contains an integer T, T test-cases follow.

Each test-case has 2 lines. The first line contains an integer N (the number of towns).

The second line contains N - 1 space separated integers where the i^{th} integer denotes the number of routes, N_{i}, from the town T_{i} to T_{i+1}

**Output Format**

Total number of routes from T_{1} to T_{n} modulo 1234567

http://en.wikipedia.org/wiki/Modular_arithmetic

**Constraints**

1 <= T<=1000

2< N <=100

1 <= N_{i} <=1000

**Sample Input**

```
2
3
1 3
4
2 2 2
```

**Sample Output**

```
3
8
```

**Explanation**

Case 1: 1 route from T_{1} to T_{2}, 3 routes from T_{2} to T_{3}, hence only 3 routes.

Case 2: There are 2 routes from each city to the next, at each city, Gandalf has 2 choices to make, hence 2 * 2 * 2 = 8.