An toàn mạng

Mạng máy tính của thành phố Metropolis gồm $n$ máy chủ, mỗi máy chủ được gán một khoá mã hoá là một số nguyên trong khoảng $[0,2^k-1]$. Gọi $c_i$ là khoá của máy chủ thứ $i$. Ngoài ra có $m$ cặp máy chủ được nối trực tiếp bằng một kênh truyền dữ liệu. Một kênh truyền được coi là an toàn nếu hai máy chủ ở hai đầu của nó có khoá khác nhau. Đảm bảo rằng tất cả $m$ kênh truyền ban đầu đều an toàn.

Một loại virus mới đang lan rộng. Virus mang một số nguyên $x$ chưa biết, $0\le x\le 2^k-1$. Khi virus lây sang máy chủ $i$, khoá của máy chủ đó bị thay đổi từ $c_i$ thành $c_i\oplus x$, trong đó $\oplus$ là phép XOR theo bit.

Vì không biết virus mang số $x$ nào, cũng không biết virus sẽ lây vào tập máy chủ nào, hãy đếm số cặp $(A,x)$ thoả mãn:

• $A$ là một tập con (có thể rỗng) của tập máy chủ;
• $x$ là một số nguyên trong khoảng $[0,2^k-1]$;
• Sau khi virus mang số $x$ lây vào đúng các máy chủ thuộc $A$ (và không lây vào các máy chủ ngoài $A$), tất cả $m$ kênh truyền vẫn an toàn.

In kết quả theo modulo ${10}^9+7$.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n$, $m$, $k$ ($1\le n\le 5·{10}^5$; $0\le m\le min(n(n-1)/2,5·{10}^5)$; $0\le k\le 60$).
• Dòng thứ hai chứa $n$ số nguyên $c_1,c_2,\dots ,c_n$ ($0\le c_i\le 2^k-1$).
• $m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u_i$, $v_i$ ($1\le u_i,v_i\le n$, $u_i\ne v_i$), mô tả một kênh truyền giữa hai máy chủ $u_i$ và $v_i$. Mỗi cặp máy chủ xuất hiện không quá một lần.

Dữ liệu ra

Một số nguyên duy nhất — số cặp $(A,x)$ thoả mãn, lấy theo modulo ${10}^9+7$.

Ràng buộc

• $1\le n\le 5·{10}^5$
• $0\le m\le min(n(n-1)/2,5·{10}^5)$
• $0\le k\le 60$
• $0\le c_i\le 2^k-1$

Ví dụ