Mr. LL is a special teacher. He has magical power. He can use magic to make infinite candy.

       There are  students(Number  to ) in his class. They all like to eat sweets. Different students want different amounts of candy. We use  represent the number of sweets needed by the student  ().

       Because the students are so many, Mr. LL divides them into groups. The number of sweets needed by one group equals the sum of all students in the group needed.

       Now Mr. LL starts giving sweets to every group. But every time he chose one group and gives the group only one Candy(We don't need to care about which student in the group the candy belong to). Every group is different. After many times every group is satisfied.

       Now We need to calculate how many ways to satisfy all groups.

The first line of the input is the number of the cases .(T<=100)

       For each case, first line input two integers (the number of students,1<=n<=100), (the number of relationships, 0<=m<=100),Then input  integers(a[i]<=10^5) means the number of sweets needed by a student.

       The last  line ,each line input two integers (means the student  and the student  in the same group) ( 1<=u,v<=n,u!=v)

For each case, first line output “Case #t:”, t is the number of cases.

Second line output the number of ways modulo 

1
3 1
1 1 1
1 2

Case #1:
3

The first case:

three students,  and  in the group ,  in the group .

First  way:     give group  one candy -> give group  one candy -> give group  one candy.

Second way: give group  one candy -> give group  one candy -> give group  one candy.

Third  way:    give group  one candy -> give group  one candy -> give group  one candy.