在本题中,神经网络由一棵带权有向树表示。神经网络通过从叶子节点开始的信号级联来处理信息:树中的每个节点根据其上游邻居计算输出值,并将该值传递给其下游邻居。一个节点计算出的输出值是其每个上游邻居的输出值乘以从该上游邻居到该节点本身的边权之和。没有上游邻居的节点(叶子节点)的输出值始终为 1。本题中的所有神经网络都有且仅有一个最终输出节点(根节点)。
There was a spider, I panicked. But I think it's gone now.
有时,神经网络会发生故障,变成通常所说的“神经质网络”(neurotic network)。假设你有机会开启精神病学领域的第二职业。现在的情况是,有人脑子里装了一个神经质网络。这意味着,如果他们的神经网络输出的是一个偶数,此人就会抓狂并点火烧小猫。因此,预先判断某个人是否安全至关重要。如果安全,请输出他们的神经网络输出值对 $1,000,000,007$ 取模的结果。如果你认为该人周围的小猫没有穿防火服而不安全,请输出字符串 “FREAK OUT”(不含引号)。
输入格式
输入的第一行包含 $T$,表示测试用例的数量。对于每个测试用例,第一行包含整数 $N$,表示树中的节点数。下一行包含 $N - 1$ 个整数 $a_1, a_2, \dots, a_{N-1}$,其中 $a_i$ 是 ID 为 $i$ 的节点的下游邻居。接下来一行包含 $N - 1$ 个整数 $w_1, w_2, \dots, w_{N-1}$,其中 $w_i$ 是从 ID 为 $i$ 的节点发出的神经连接的权重。注意,ID 为 0 的节点始终是输出节点。
输出格式
如果神经网络最终输出节点的计算结果为偶数,则输出 “FREAK OUT”(不含引号)。否则,输出最终输出节点的值对 $1,000,000,007$ 取模的结果。
数据范围
- $0 < T \le 50$
- $0 < N \le 10000$
- $0 < w_i \le 10$
- $0 \le a_i < N$
- 保证图是一棵树。
- 这是一个 I/O 密集型问题。对于 Java 程序员,这意味着你应该使用
BufferedReader进行输入读取(而不是Scanner)。
样例
输入格式 1
4 1 4 0 0 2 7 7 1 4 0 0 2 6 7 2 11 0 1 2 3 4 5 6 7 8 9 9 9 9 9 9 9 9 9 9 3
输出格式 1
1 FREAK OUT FREAK OUT 162261460