Counting Bicycle Race Routes

There are N villages numbered from 1 through N and M one-way roads between them. A bicycle race is going to be held in this country. The race must start at village 1 and end at village 2.

Compute the number of possible race routes. Multiple roads may connect the same ordered pair of villages, and choosing different roads counts as different routes. Some directed cycles may make the number of routes from village 1 to village 2 infinite.

The first line contains the number of villages N and the number of roads M. (2 <= N <= 10,000, 1 <= M <= 100,000)

Each of the next M lines contains two integers A and B describing a road. This road goes from village A to village B.

There may be more than one road between the same two villages.

Print the number of possible bicycle race routes on the first line. If the number has more than 9 digits, print only its last 9 digits. If leading zeroes are needed to make those last 9 digits visible, include them.

If the number of routes is infinite, print inf.