EOJ Monthly 2019.7 (based on July Selection)

E. 与非门树

单点时限: 1.0 sec

内存限制: 512 MB

QQ小方以前不会做与非门的实验,现在他会了,所以他急切的想教会你。

同一个与非门可能有多个输入接口,但只会有一个输出接口,由于实验箱的限制,只能将与非门连接成了一个树形结构,即某个与非门的输出,会唯一的连接另一个与非门的一个输入上,各个输入之间互不影响,有唯一的一个与非门(树根)的输出只连接到了一个 LED 上,表示整个电路的输出,“空着”(没有连接到其他输出)的输入接口均连接了一个开关,表示一个输入()。

单单讲给你听肯定是不够的,为了表现自己,QQ小方现在要考考你。

QQ小方正在做数字逻辑实验,QQ小方今天的任务是用一堆与非门实现一个逻辑电路。

对于一个正常运作的与非门,当且仅当所有输入为 时,与非门输出 ,否则与非门输出 。但是很可惜,由于实验室设备陈旧,其中有一些与非门早就被烧坏了,无论他们的输入是什么,他们都会保持某一种输出(即永远输出 的其中一种)。

现在QQ小方想知道电路对于多少种可能的输入(即所有开关的状态)会得到正确的输出。QQ小方当然正确连接了电路。

为了不为难你,QQ小方测试了每个与非门的好坏,并把情况以及整个树的结构告诉了你,希望你能帮他看看现在他对于多少比例有正确的输出,结果模

输入格式

第一行包含一个整数 表示与非门的总数。

接下来的 行中,第 行包含三个整数 表示第 个与非门的输出接在了 的输入端口上, 表示第 个与非门的输入端口数,每个连接都独占某个输入端口,保证不会出现冲突的连接, 表示这个与非门正常工作, 表示其永远输出 0 或 1。

存在唯一的 表示第 个与非门的输出是整个电路的输出,保证联通且呈树形,不存在环。

输出格式

输出一个整数 表示输出正确的比例。

假设正确答案比例的分数是

样例

Input
3
0 2 -1
1 1 1
1 1 -1
Output
249561089

提示

样例解释