All Submissions


Russia after taking over Cremia wants to have rapid development of Cremia.To make this happen Russia wants a city of Cremia to become the economic capital of new Russia with Cremia included.They also want good connectivity between Moscow,capital of Russia, and the economic capital from Cremia.

Russia along with Cremia has cities connected by only one way roads.To ensure high connectivity, two cities are sometimes directly connected by even more than one road.

Connectivity of a pair of cities is defined as the number of paths between the two cities.A road can be used in a path more than once if possible.Two paths are considered different if they do not use exactly the same sequence of roads.

There are N cities in Russia,Cremia included, and M one way roads.City 1 is Moscow and city N is the economic capital from Cremia.your task is to find the connectivity between Moscow and the economic capital,i.e how many different paths are there from city 1 to city N?

INPUT
The first line of input contains the number of test cases T.
Each test case begins with two intergers N and M, deonting number of cities and number of one way roads.Next M lines of each test case contains two integers X and Y denoting a one way raod from city X to city Y.

OUTPUT
For each test case print the number of different paths from city 1 to city N modulo 1,000,000,000(10^9), if there are infinitely many different paths print “INFINITE PATHS”(quotes are for clarity).Answer of each test case must be in separate line.

CONSTRAINT

0 < T <= 20
1 < N <=10000
0 < M <= 10^5
0 < X <= N
0 < Y <= N



SAMPLE INPUT

2
5 4
1 2
2 3
1 4
4 5
7 7
1 2
2 3
1 4
4 6
4 7
6 5
5 7


SAMPLE OUTPUT

1
2


Problem Setter : Akshay Kumar

Languages: AWK,Bash,Brain,C,C++,Java,C#,JavaScript,Pascal,Perl,PHP,Python,Python3,Ruby,Text

Time Limit: 1 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Submit

Login to post clarification.

No Clarifications.

Contest

Mode Judge

Passive

Online

Overall Rankings

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0