Create Keine's Problem

In Gensokyo, Keine is a teacher in Human Village. Since there are many naughty students in her class, Keine keeps a log of all in/out behaviors of all students, in chronological order.
Following is a part of an example log:
Cirno in
Rumia in
Cirno out
Rumia out
One day, Keine found that the log had been damaged. All the names of students were lost. Keine could remember that some of the records were relevant. Record u and record v are considered relevant if and only if:
Record u and v are of the same student;
Record u is 'I' and record v is 'O';
Record u is before record v;
No other record between record u and record v is of this student.
For example, the first record and the third record in the example log are relevant, since it was a log of Cirno entering and then exiting. However, there are still many possibilities for the whole log. Keine wants to know how many possible versions are there for the damaged log.
Notice that the classroom was empty at both the beginning and the ending of the log.
Input
The first line contains an integer T (1 ≤ T ≤ 1 000) -- the number of test cases.

For each test case:
The first line contains three integers: n, m, k. n (1 ≤ n ≤ 100 000) is the length of the log. m (1 ≤ m ≤ n/2) is the number of relevant pairs that Keine could remember. k (1 ≤ k ≤ 50) is the number of students who may appear in the log.
The second line contains a string, which only consists of 'I' and 'O', indicates the in/out behaviors in the log.
For next m lines, each line contains two integers u and v (u < v), indicate that the u-th and the v-th records are relevant. The u-th record must be 'I' and the v-th record must be 'O'.
Output
For each test case, output only an integer in a single line - the number of possible versions of the log, modulo (1 000 000 000+7).
Sample Input
3
8 2 3
IIOIOIOO
1 3
4 5
8 2 3
IIOOIOIO
2 3
5 6
6 2 3
IOIOIO
1 2
3 4
Sample Output
48
54
27