Permutations solution: Facebook hacker cup 2013 Round 2

From 2011 facebook is organizing a Facebook hacker cup every year around feb, visit Facebook hacker cup homepage for more details

This question is the third question(Carried 45 marks out of 100) for the Round 2 of 2013 hacker cup. only top 100 contestants will be moved to Round 3.

Problem Statement

In this problem you need to count number of possible permutations p of the first N integers, given N-1 constraints of the form p_i < p_j.

Input

The first line contains an integer T, T ≤ 20, followed by T test cases. Each test case begins with an integer N, N ≤ 1000, which is the number of integers in the permutation. The next N – 1 lines each contain a single constraint in the following format: “i sign j“, where 0 ≤ i, j ≤ N – 1 and sign is either “<” or “>“, which denotes whether the i-th element of the permutation should be less than or greater than the j-th element.

It is guaranteed that it is not possible to partition indices into two disjoint sets A and B such that there is no constraint involving elements from both A and B.

Output

For each test case, output one single line with the number of permutations that satisfy all the constraints, following the output format shown in the example. The answer may be very large, so you should give the result modulo 1000000007.

Example Input

5
2
0 < 1
3
0 < 1 2 > 1
5
0 < 2
1 < 2
2 < 3
2 < 4
4
0 < 1
0 < 2
0 < 3 6 0 > 1
1 > 2
2 > 3
3 > 4
4 > 5

Example Output

Case #1: 1
Case #2: 1
Case #3: 4
Case #4: 6
Case #5: 1

Solution

I will just give the hint as of now, think of using graph and dfs.
There is a neat solution by Niyaj(ranked 45 in round 2).

Facebook Comments