# Hackerrank - Connecting Towns Solution

Gandalf is travelling from ** Rohan** to

**to meet Frodo but there is no direct route from**

**Rivendell****(T**

**Rohan**_{1}) to

**(T**

**Rivendell**_{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.

### Solution in Python

```
#!/bin/python3
import os
import sys
def connectingTowns(n, routes):
p = 1
for route in routes:
p*=route
return p%1234567
t = int(input())
for t_itr in range(t):
n = int(input())
routes = list(map(int, input().rstrip().split()))
result = connectingTowns(n, routes)
print(result)
```