Welcome to the Shire… Well at least welcome to Middle Earth, we don’t actually need to travel through the shire in the next HackerRank problem with Connecting Towns. The problem reads

Gandalf is travelling from

RohantoRivendellto meet Frodo but there is no direct route fromRohan(T_{1}) toRivendell(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+1Find 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

## Solving the math of Connecting Towns

There are two things we need to get our heads around. There is the first part which is how many paths there are, and then there is the second part of the modulo.

The former problem of the paths is rather simple as it is a simple combinatorics problem and the total number of paths are just the product of the paths of each leg of the journey

The problem of the modulo operator can be treated in different ways. Since we are using Python as implementation language we can completely ignore it, as it can handle arbitrarily large integers. However, we can also solve it as we have done for Project Euler problem 48.

In general we have the formula

Which means that for every time we multiply with the next set of paths we can also take the modulo, which means we will keep the total size of the integer down significantly. If it actually matters in Python I don’t know.

## Implementing Connecting towns in Python

Let us implement the one with modulo arithmetic. However since we know that both a and b in the previous formula will be smaller than the modulo. Therefore a%c = a and b%c= b, so we only need to take modulo of the result during the iterations. Therefore the function we need to implement is

def connectingTowns(n, routes): paths = 1 for i in routes: paths = (paths * i) % 1234567 return paths

and that should solve the problem.