It has been a prosperous year for King Charles and he is rapidly expanding his empire. In fact, he recently invaded his neighboring country and set up a new kingdom! This kingdom has many cities connected by one-way roads. To ensure higher connectivity, two cities are sometimes directly linked by more than one road.

In the new kingdom, King Charles has made one of the cities his financial capital and another city his warfare capital. He wants a better connectivity between these two capitals. The connectivity of a pair of cities, and , is defined as the number of different paths from city to city . A path may use a road more than once if possible. Two paths are considered different if they do not use the same sequence of roads the same number of times.

There are cities numbered to in the new kingdom and one-way roads. City is the financial capital and city is the warfare capital. Determine the number of different paths between cities and . Since the number may be large, print the result modulo or .

Note: Two roads may connect the same cities, but they are still considered distinct for path connections.

For example, there are cities connected by roads as shown in the following graph:

There are two direct paths and one cyclic path. Direct paths are and and . The cycle can be repeated any number of times, so there are infinite paths. If the connection did not exist, there would be only the two direct paths.

Function Description

Complete the countPaths function in the editor below. It should print your result, modulo if there are limited paths or INFINITE PATHS if they are unlimited. There is no expected return value.

countPaths has the following parameters:
- n: the integer number of cities
- edges: a 2D integer array where is the source city and is the destination city for the directed road