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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
# n - liczna zarowek
# m - liczba przelacznikow
#
#
# 1 0 1 1 0
#
#
#
# 1 3
#
# 5 3
#
# 4 2
#
# 1 5

n, m = map(int, input().split())
items = list(map(int, input().split()))
Mod = 10 ** 9 + 7
steps = []
for _ in range(m):
    steps.append(tuple(map(int, input().split())))

# print(steps)
results = set()
current = items.copy()

toReturn = 0
visited = set()


def dfs(stepIndex, steps, current, depth, limitDepth):

   # print(current)
    global toReturn

    if depth > limitDepth:
        return

    if tuple(current) + tuple([stepIndex]) in visited:
       return

    #print("cgeck")
    visited.add(tuple(current) + tuple([stepIndex]))

    if (tuple(current)) not in results:
        results.add(tuple(current))
        toReturn = (toReturn + 1) % Mod


    start = steps[stepIndex]
    x = start[0] - 1
    y = start[1] - 1

    # print(x)
    # print(y)


    for i in range(len(steps)):
        if i != stepIndex:
            #print("eeee")
            #print(newResult)
            # with chnage

            dfs(i, steps, current, depth + 1, limitDepth)

            if current[x] == current[y]:
                newResult = current.copy()
                # print("????")
                newResult[x] = 1 - newResult[x]
                newResult[y] = 1 - newResult[y]
                dfs(i, steps, newResult, depth + 1, limitDepth)
            # or without change



#for stepIndex in range(len(steps)):

dfs(0, steps, current, 0, n * 2)


print(toReturn)