불확실한 게이트

NAND 게이트는 모든 입력이 참일 때만 거짓을 내보내는 디지털 논리 소자다. 같은 입력에 대해 AND 게이트가 내보내는 값을 반전한 값과 같다. 입력이 두 개인 NAND 게이트의 기호와 진리표는 아래 그림과 같다. 참은 1, 거짓은 0으로 쓴다.

이 문제에서 다루는 회로는 입력이 두 개인 NAND 게이트만으로 이루어지고, 이진 트리 모양이다. 트리의 내부 노드는 NAND 게이트 하나를 나타내며, 두 자식이 내보낸 값을 입력으로 받는다. 트리의 잎은 회로의 외부 입력 하나를 나타내고, 0 또는 1 값을 갖는다. 회로가 내보내는 값은 트리의 루트에 있는 게이트가 내보내는 값이다. 아래 그림은 노드가 아홉 개인 회로다. 그중 넷은 NAND 게이트이고, 다섯은 외부 입력이다.

회로의 게이트는 고장 나 있을 수 있다. 고장 난 게이트는 입력이 무엇이든 항상 0만 내보내거나 항상 1만 내보낸다. 모든 게이트가 제대로 동작하는 같은 모양의 회로를 정상 회로라고 하자. 테스트 패턴은 외부 입력에 값을 하나씩 배정한 것 가운데, 고장 난 게이트 때문에 회로가 내보내는 값이 정상 회로가 내보내는 값과 달라지는 배정이다.

회로의 정보가 주어지면 서로 다른 테스트 패턴의 개수를 구하는 프로그램을 작성하시오.

첫째 줄에 회로에 있는 게이트의 개수 $N$ ($1 \le N \le 10^5$)이 주어진다. 회로는 이진 트리 모양이다. 게이트는 1부터 $N$까지 서로 다른 정수로 구분하며, 1번 게이트가 트리의 루트다. 이어지는 $N$개 줄 가운데 $i$번째 줄에는 $i$번 게이트를 설명하는 세 정수 $X$, $Y$, $F$ ($0 \le X, Y \le N$, $-1 \le F \le 1$)가 주어진다. $X$와 $Y$는 게이트의 두 입력이다. $X$가 0이면 첫째 입력은 외부 입력이고, 0이 아니면 $X$번 게이트가 내보낸 값이다. $Y$도 같은 방식으로 둘째 입력을 나타낸다. 값이 0인 자리는 저마다 서로 다른 외부 입력 하나에 해당한다. $F$는 게이트의 상태다. $-1$은 제대로 동작하는 게이트, 0은 항상 0만 내보내는 게이트, 1은 항상 1만 내보내는 게이트를 뜻한다.

서로 다른 테스트 패턴의 개수를 $10^9 + 7$로 나눈 나머지를 한 줄에 출력한다.