문제

태윤이는 \(0\) 또는 \(1\)로 이루어진 길이 \(N\)짜리의 수열 \(A\)를 가지고 있었다. 그러나 태윤이는 수열 \(A\)의 각 원소가 무엇인지 까먹어 버렸다. 다행히도, 태윤이는 수열에 관한 몇 가지 정보를 기억하고 있었다. 각 정보는 \(i,j,x\) 의 순서로 이루어져 있으며, \(A_i\) XOR \(A_{i+1}\) XOR ⋯ XOR \(A_j\) = \(x\)라는 식이 성립한다는 것을 의미한다. 태윤이는 이 정보들로부터 만들어 낼 수 있는 수열의 경우의 수가 몇 개인지 알고 싶어 졌다. 여러분이 태윤이를 도와서 가능한 \(A\)의 경우의 수를 세어주자. 단, 수가 너무 클 수 있으니 \(1,000,000,007\)로 나눈 나머지를 구해야 한다.