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
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
from collections import deque, defaultdict, Counter


def binary_array_to_string(binary_array):
    # Convert binary array to string
    binary_string = ''.join(str(bit) for bit in binary_array)

    return binary_string


def swap_characters_at_indices(input_string, index_1, index_2):
    # Create a new string with the swapped bits

    if 0 <= index_1 < len(input_string) and 0 <= index_2 < len(input_string):
        if input_string[index_1] == '0':
            new_string = input_string[:index_1] + \
                '1' + input_string[index_1 + 1:]
        else:
            new_string = input_string[:index_1] + \
                '0' + input_string[index_1 + 1:]

        if new_string[index_2] == '0':
            new_string = new_string[:index_2] + '1' + new_string[index_2 + 1:]
        else:
            new_string = new_string[:index_2] + '0' + new_string[index_2 + 1:]

        return new_string
    else:
        print("Index out of range")
        return input_string


class DisjSet:
    def __init__(self, n):
        # Constructor to create and
        # initialize sets of n items
        self.rank = [1] * n
        self.parent = [i for i in range(n)]

    # Finds set of given item x

    def find(self, x):

        # Finds the representative of the set
        # that x is an element of
        if (self.parent[x] != x):

            # if x is not the parent of itself
            # Then x is not the representative of
            # its set,
            self.parent[x] = self.find(self.parent[x])

            # so we recursively call Find on its parent
            # and move i's node directly under the
            # representative of this set

        return self.parent[x]

    # Do union of two sets represented
    # by x and y.

    def Union(self, x, y):

        # Find current sets of x and y
        xset = self.find(x)
        yset = self.find(y)

        # If they are already in same set
        if xset == yset:
            return

        # Put smaller ranked item under
        # bigger ranked item if ranks are
        # different
        if self.rank[xset] < self.rank[yset]:
            self.parent[xset] = yset

        elif self.rank[xset] > self.rank[yset]:
            self.parent[yset] = xset

        # If ranks are same, then move y under
        # x (doesn't matter which one goes where)
        # and increment rank of x's tree
        else:
            self.parent[yset] = xset
            self.rank[xset] = self.rank[xset] + 1

    def get_parents(self):
        counts = Counter(self.parent)

        return list(counts.keys())


class HashGraph:
    '''
    This graph stores bulb states as vertices
    '''

    def __init__(self):
        self.edges = []

    def addEdge(self, u, v):
        self.edges.append((u, v))

    def BFS(self, s):
        # Mark all the vertices as not visited
        visited = defaultdict(bool)

        # Create a queue for BFS
        queue = deque()

        # Mark the source node as
        # visited and enqueue it
        queue.append(s)
        visited[s] = True

        while queue:
            # Dequeue a vertex from and increase counter
            s = queue.popleft()

            for edge in self.edges:
                if s[edge[0]] == s[edge[1]]:
                    s = swap_characters_at_indices(s, edge[0], edge[1])

                    if visited[s] == False:
                        queue.append(s)
                        visited[s] = True

        return len(visited) % (10**9+7)


n, m = map(int, input().split())

bulb_states = [int(x) for x in input().split()]

disj_set = DisjSet(n)
switches = []


for i in range(m):
    a, b = map(int, input().split())

    disj_set.Union(a-1, b-1)
    switches.append((a-1, b-1))

connected_components = defaultdict(list)

for switch in switches:
    connected_components[disj_set.find(switch[0])].append(switch)

result = 1

for edges in connected_components.values():
    hash_graph = HashGraph()

    for edge in edges:
        hash_graph.addEdge(edge[0], edge[1])

    result *= hash_graph.BFS(binary_array_to_string(bulb_states))
    result %= 10**9+7

print(result)