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.
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.
For each test case, output the number of different ways the tree can be coloured modulo \(10^9 + 7\).
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\)
2 5 C ? ? ? ? 0 1 2 3 6 C ? ? ? ? ? 0 0 1 2 3