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
line1 = input()
n, m = list(map(int, line1.split(" ")))

line2 = input()
bulbs_zero = list(map(int, line2.split(" ")))

from collections import defaultdict

switches = defaultdict(lambda: [])

for i in range(m):
    switch = input()
    switch = list(map(int, switch.split(" ")))
    switches[max(switch)-1].append(min(switch)-1)

# print(switches)

states_one = [0] * n
states_zero = [0] * n

no_states = 1

if bulbs_zero[0] == 0:
    states_zero[0] += 1
else:
    states_one[0] += 1

# print(states_zero)
# print(states_one)

for i in range(1, n):

    cur_switches = switches[i]
    val_switch = bulbs_zero[i]

    if val_switch:
        states_one[i] += no_states
    else:
        states_zero[i] += no_states

    if i not in switches:
        # print(i, no_states)
        # print(states_zero)
        # print(states_one)
        continue

    for switch in cur_switches:
        if val_switch:
            no_states += states_one[switch] % (10**9 + 7)
            states_zero[i] += states_one[switch]
            states_zero[switch] += states_one[switch]

        else:
            no_states += states_zero[switch] % (10**9 + 7)
            states_zero[i] += states_zero[switch]
            states_zero[switch] += states_zero[switch]
    # print(i, no_states)
    #
    # print(states_zero)
    # print(states_one)

print(no_states)