Cities on a map are connected by a number of roads. The number of roads between each city is in an array and city \(0\) is the starting location. The number of roads from city \(0\) to city \(1\) is the first value in the array, from city \(1\) to city \(2\) is the second, and so on.

How many paths are there from city \(0\) to the last city in the list, modulo \(1234567\)?

**Example**

\(n=4\)

\(routes=[3,4,5]\)

There are \(3\) roads to city \(1\), \(4\) roads to city \(2\) and \(5\) roads to city \(3\). The total number of roads is \(3\times 4\times 5\mod 1234567 = 60\).

**Note**

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

**Function Description**

Complete the *connectingTowns* function in the editor below.

*connectingTowns* has the following parameters:

*int n:*the number of towns*int routes[n-1]:*the number of routes between towns

**Returns**

*int:*the total number of routes, modulo 1234567.

**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}

**Constraints**

1 <= T<=1000

2< N <=100

1 <= routes[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, hence 2 * 2 * 2 = 8.

## Solution

The solution was given already by the problem statement. We have to multiply all number of routes and since the number can get quite large, we are required to get the result modulo 1234567. To not rely on bigint, we make use of multiplicative rules of modulo and can solve the problem with

```
function connectingTowns(n, routes) {
var p = 1;
for (var r of routes) {
p = (r * p) % 1234567;
}
return p % 1234567;
}
```