1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
import sys

input = sys.stdin.readline

############ ---- Input Functions ---- ############
def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))

[n, m] = inlt()
zarowki = inlt()
przelaczniki = []
for i in range(m):
	przelaczniki.append(inlt())


debug = True
debug = False

if debug : print(zarowki)
if debug : print(przelaczniki)
przelaczniki_uzywalne = []

przed = 0
nowe_stany = set(["".join([str(x) for x in zarowki])])
po = len(nowe_stany)
stany = nowe_stany
stany_do_rozpatrzenia_teraz = stany

for stan in nowe_stany:
    if debug : print(stan)

def przelacz(a, b, stan):
    if stan[a] == "0":
        ns = "1"
    else:
        ns = "0"
    if debug : print( "=>",  stan[:a] + ns + stan[a+1:b] + ns + stan[b+1:])
    return stan[:a] + ns + stan[a+1:b] + ns + stan[b+1:]
    
kroki = 0

while (stany_do_rozpatrzenia_teraz != set()) :
    if debug : print("=== krok : ", kroki, nowe_stany)
    kroki = kroki + 1
    stany = stany | nowe_stany
    stany_do_rozpatrzenia_teraz = stany
    nowe_stany = set()
    for i in przelaczniki:
        a = min(i[0] - 1, i[1] - 1)
        b = max(i[0] - 1, i[1] - 1)
        if debug : print(a, b)
        for stan in stany_do_rozpatrzenia_teraz:
            if debug : print("stany", stany)
            if stan[a] == stan[b]:
                if debug : print(stan, i, "zadziala")
                przelaczniki_uzywalne.append(i)
                nowe_stany.add(przelacz(a, b, stan))
                if debug : print("nowe : ", nowe_stany)
            else:
                if debug : print(stan, i, "nie zadziala")
    stany_do_rozpatrzenia_teraz = nowe_stany - stany
    if debug : print("stany_do_rozpatrzenia_teraz : " ,stany_do_rozpatrzenia_teraz)

print(len(stany) % 1000000007)