与非门

难题，先看别的

题面

数字电路中有一种基本逻辑电路叫做与非门，它有两个输入和一个输出。如下图：

现在将n个与非门拼接到一起，形成了一个形如二叉树的电路，如下图：

两个与非门相连表示一个与非门的输出作为另一个与非门的输入。不与与非门相连的部分表示外部输入，可能是0或者1。也就是说所有子节点数不为2的节点都会连一个外部输入，自底向上处理，最后从根节点输出，保证根节点编号为1.

由于外界的干扰，有一些与非门损坏，只能输出1或者只能输出0。

现在给出一个电路，请问有多少输入对应的输出会出错。

输入

第一行一个整数n（$1\le n \le 10^5$）

接下来n行，每行三个整数a,b,c($0\le a,b\le n,-1 \le c\le 1$)。对于第i行，如果a,b不为0，则a表示第i个与非门与第a个与非门相连，b表示第i个与非门与第b个与非门相连；如果a或者b为0，表示第i个与非门对应的输入接外部输入。c如果等于-1，表示第i个与非门正常工作，1表示第i个与非门只输出1，0表示第i个与非门只输出0

从1开始编号，保证根节点为1。

输出

输出一行，一个整数，答案可能很大，请对$10^9+7$取模

输入样例

4
2 3 1
0 0 -1
4 0 0
0 0 -1

输出样例

15

样例说明

这个样例对应的电路如下:

其中1号损坏只能输出1,3号损坏只能输出0

一共有5个外部输入，每个都可能是0,1,所以输入一共有$2^5$种情况

对于输入0 0 0 0 0（上图中，由上到下），理论输出为0，实际输出为1，出错

对于输入1 1 1 1 1（上图中，由上到下），理论输出为1，实际输出为1，正确