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
from collections import defaultdict
# 1. Wczytaj dane
n, m = map(int, input().split())
c = list(map(int, input().split()))
prze = [list(map(int, input().split())) for _ in range(m)]

# szybkie podnoszenie do potęgi w ciele modulo n:
def potega(a, b, n):
    wyn = 1
    while b > 0:
        if b % 2 == 1:
            wyn *= a
            wyn %= n
        a *= a
        a %= n
        b //= 2
    return wyn

# 2. Zdefiniuj funkcję liczba_konfiguracji(n, m, c, prze), która zwróci resztę z dzielenia przez 10^9 + 7
# liczby osiągalnych konfiguracji zapalonych i zgaszonych żarówek
def liczba_konfiguracji(n, m, c, prze):
    res = 0
    pom = []
    for prz in prze:
        pom.append([prz[1], prz[0]])
    prze += pom
    prze = sorted(prze) #, key=lambda x: (x[0], x[1]) if x[0] < x[1] else (x[1], x[0]))
    #print(*prze)
    sp_skl = defaultdict(set) # numer spójnej składowej -> zbiór żarówek
    id_skld = -1
    for prz in prze:
        #print("testing: ", prz, c[prz[0]-1], c[prz[1]-1])
        if (c[prz[0]-1] == c[prz[1]-1] and c[prz[0]-1] >= 0):
            c[prz[0]-1] = id_skld
            c[prz[1]-1] = id_skld
            sp_skl[id_skld].add(prz[0])
            sp_skl[id_skld].add(prz[1])
            id_skld -= 1
            #print(prz)
        elif (c[prz[0]-1] < 0 and c[prz[1]-1] >= 0):
            skld = c[prz[0]-1]
            c[prz[1]-1] = skld
            sp_skl[skld].add(prz[1])
        elif (c[prz[1]-1] < 0 and c[prz[0]-1] >= 0):
            skld = c[prz[1]-1]
            c[prz[0]-1] = skld
            sp_skl[skld].add(prz[0])
        elif (c[prz[0]-1] < 0 and c[prz[1]-1] < 0):
            skld = c[prz[0]-1]
            skld2 = c[prz[1]-1]
            if skld != skld2:
                sp_skl[skld] = sp_skl[skld].union(sp_skl[skld2])
                for x in sp_skl[skld2]:
                    c[x-1] = skld
                #sp_skl[skld2] = set()
                del sp_skl[skld2]
                c[prz[0]-1] = skld
                c[prz[1]-1] = skld
    
    r = 0 # len(sp_skl) - 1
    for skl in sp_skl.items():
        #print(len(skl[1]) - 1, skl)
        r += len(skl[1]) - 1

    return potega(2, r, 10**9 + 7)

# 3. Wypisz wynik
print(liczba_konfiguracji(n, m, c, prze), end='')