Nick has found a very odd looking tree. It seems to have 3 different coloured nodes, cyan (C), yellow (Y) and red (R), where each node is connected to any number of other nodes. Unfortunately, Nick cannot see all the nodes of the tree, as some of them are hidden from view, so he wants to know the number of ways that the hidden nodes could be coloured and the tree remain "coloured".

The tree is considered coloured if no two connected nodes are the same colour.

Input Specification

The first line contains an integer \(T\), the number of test cases to follow. For each test case, a line with one number \(N\) defines the number of nodes. \(N\) lines follow, with the \(i\)th line denoting the colour of the node (C for cyan, Y for yellow, R for red and ? for unknown). After that follows \(N-1\) lines, each contains one integer, and we call the \(i\)th line's integer \(p_i\). The value of \(p_i\) cooresponds to the parent of node with index \(i+1\). This is because node \(0\) will not have a parent. The node at index \(0\) is guaranteed to be the root of the tree.

The input will not have any cycles, and will be connected. In short, it will be a tree.

Output Specification

For each test case, output the number of different ways the tree can be coloured modulo \(10^9 + 7\).

Bounds

Note this problem includes sub-problems of increasing difficulty worth different numbers of points:

• 20 points: \(1 \leq N \leq 6\)
• 80 points: \(1 \leq N \leq 100\)

For all sub-problems:

\(1 \leq T \leq 10\)

Sample Input

2
5
C
?
?
?
?
0
1
2
3
6
C
?
?
?
?
?
0
0
1
2
3

Sample Output

16
32