B'The Metropolis computer network consists of n servers, each has an encryption key in the range from 0 to 2^k - 1 assigned to it. Let c_i be the encryption key assigned to the i -th server. Additionally, m pairs of servers are directly connected via a data communication channel. Because of the encryption algorithms specifics, a data communication channel can only be considered safe if the two servers it connects have distinct encryption keys. The initial assignment of encryption keys is guaranteed to keep all data communication channels safe. You have been informed that a new virus is actively spreading across the internet, and it is capable to change the encryption key of any server it infects. More specifically, the virus body contains some unknown number x in the same aforementioned range, and when server i is infected, its encryption key changes from c_i to c_i oplus x , where oplus denotes the bitwise XOR operation. Sadly, you know neither the number x nor which servers of Metropolis are going to be infected by the dangerous virus, so you have decided to count the number of such situations in which all data communication channels remain safe. Formally speaking, you need to find the number of pairs (A, x) , where A is some (possibly empty) subset of the set of servers and x is some number in the range from 0 to 2^k - 1 , such that when all servers from the chosen subset A and none of the others are infected by a virus containing the number x , all data communication channels remain safe. Since this number can be quite big, you are asked to find its remainder modulo 10^9 + 7 . The first line of input contains three integers n , m and k ( 1 <= q n <= q 500 ,000 , 0 <= q m <= q min( frac{n(n - 1)}{2}, 500 ,000) , 0 <= q k <= q 60 ) -- the number of servers, the number of pairs of servers directly connected by'...