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
#!/usr/bin/python3

# === wej ===

N, m = input().split()
N, m = int(N), int(m)

state = [None] + [bool(int(d)) for d in input().split()]

G = [[] for _ in range(N+1)]
for _ in range(m):
    a, b = input().split()
    a, b = int(a), int(b)
    G[a].append(b)
    G[b].append(a)


# === prog ===

M = 10**9 + 7

binom_table = [[1]]

def binom(n, k):
    if n < k:
        return 0

    y = len(binom_table) - 1  # Czy powinienem pozbyć się zmiennej y?
    while y < n:
        y += 1
        last_row = binom_table[-1]

        new_row = [1]
        for x in range(1, len(last_row)):
            new_row.append((last_row[x-1] + last_row[x]) % M)
        new_row.append(1)
        
        binom_table.append(new_row)
        # print(y, n)
        # print(binom_table)
    # print(n, k)
    return binom_table[n][k]

"""
Pewnie trzeba by ztablicować wszystkie silnie...
"""
# print(binom(5, 3))

class Globals:
    pass
g = Globals()

vis = [0] * (N+1)
g.dwudzielna = None
g.count = [None, [0, 0], [0, 0]]
g.wy = 1


def dfs(v, color):
    # print(f"-> {v}")
    vis[v] = color
    # print(f" color: {color}, state[v]: {state[v]}")
    g.count[color][state[v]] += 1

    next_color = 3 - color  # alternates between 1 and 2
    for u in G[v]:
        if not vis[u]:
            dfs(u, next_color)
        elif vis[u] == color:
            g.dwudzielna = False
    
    # print(f"<- {v}")


for v in range(1, N+1):
    if not vis[v]:
        g.dwudzielna = True
        g.count[1] = [0, 0]
        g.count[2] = [0, 0]
        dfs(v, 1)
        if g.dwudzielna:

            n_L = sum(g.count[1])
            n_R = sum(g.count[2])
            r = g.count[2][1] - g.count[1][1]
            if r < 0:  # to zamieniamy strony
                n_L, n_R = n_R, n_L
                r = -r
            
            wyn = 0
            for k in range(r, n_R+1):
                wyn += binom(n_L, k-r) * binom(n_R, k)
                wyn %= M
        else:
            n = sum(g.count[1]) + sum(g.count[2])
            # n = sum(sum(g.count[i]) for i in (1, 2))
            wyn = 1
            for _ in range(n-1):
                wyn = (wyn * 2) % M
        g.wy = (g.wy * wyn) % M




# === wyj ===

print(g.wy % M)  # Modulo na wszelki wypadek, gdybym gdzieś przeoczył.