第四回日本最強プログラマー学生選手権-予選-（AtCoder Beginner Contest 313）E,F問題メモ

from itertools import groupby


def naive(s):
    print(s)
    cnt = 0
    while len(s) > 1 and len(s) < 1000:
        n = len(s)
        res = []
        for i in range(n - 1):
            c = s[i]
            k = int(s[i + 1])
            res.append(c * k)
        s = ''.join(res)
        print(s)
        cnt += 1
    return cnt


def solve(s):
    MOD = 998244353
    s = s[::-1]
    ans = 0
    prev_not_1 = False
    cum_1 = 0
    for c, itr in groupby(s):
        c = int(c)
        k = len(list(itr))
        # print(c, k)
        if c == 1:
            ans += k + cum_1
            prev_not_1 = False
            cum_1 = 0
        else:
            if k > 1 or prev_not_1:
                return -1
            prev_not_1 = True
            ans += 1
            cum_1 += (c - 1) * ans
        # print(ans)
        ans %= MOD
    return (ans - 1) % MOD


n = int(input())
s = input()

# print(naive(s))

print(solve(s))

n, m = map(int, input().split())
cards = [list(map(int, input().split())) for _ in range(n)]
machines = set()
sure = set()
for _ in range(m):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    if x == y:
        sure.add(x)
    else:
        if x > y:
            x, y = y, x
        machines.add((x, y))

# 確実に高い方が選べるカード
high = [0] * n
# 裏返せるマシンが1つも無いカード
no_chance = [1] * n
for i in range(n):
    if i in sure:
        high[i] = 1
        no_chance[i] = 0
        cards[i].sort(reverse=True)
    elif cards[i][0] >= cards[i][1]:
        high[i] = 1

# 確実には低い方しか選べないが、そういうの同士で潰しあえるカード
low_both = [0] * n
for x, y in machines:
    if high[x] == 0 and high[y] == 0:
        low_both[x] = low_both[y] = 1
    no_chance[x] = no_chance[y] = 0

# 確実には低い方しか選べず、確実に高い方を選べるカードを犠牲にするとひっくり返せるかもしれない
l_set = {i for i in range(n) if high[i] == 0 and low_both[i] == 0 and no_chance[i] == 0}
h_set = {i for i in range(n) if high[i] == 1 and no_chance[i] == 0}
l_list = sorted(l_set)
h_list = sorted(h_set)
l_reindex = {l: i for i, l in enumerate(l_list)}
h_reindex = {h: i for i, h in enumerate(h_list)}
l_len = len(l_set)
h_len = len(h_set)

# 各highがひっくり返せるlowをbitflagで保持
reversible = [0] * h_len
for x, y in machines:
    if high[x] == 1 and y in l_set:
        i = h_reindex[x]
        j = l_reindex[y]
        reversible[i] |= 1 << j
    elif high[y] == 1 and x in l_set:
        i = h_reindex[y]
        j = l_reindex[x]
        reversible[i] |= 1 << j

# print(l_list)
# print(h_list)
# print(reversible)

# 小さい方で処理を分ける
res = 0
if h_len < l_len:
    for bitset in range(1 << h_len):
        tmp = 0
        tmpset = 0
        for i in range(h_len):
            x = h_list[i]
            if bitset & (1 << i):
                tmpset |= reversible[i]
                tmp += sum(cards[x])
            else:
                tmp += cards[x][0] * 2
        for j in range(l_len):
            y = l_list[j]
            if tmpset & (1 << j):
                tmp += sum(cards[y])
            else:
                tmp += cards[y][0] * 2
        res = max(res, tmp)
else:
    INF = 1 << 60
    dp = [-INF] * (1 << l_len)
    dp[0] = 0
    for i in range(h_len):
        x = h_list[i]
        use = sum(cards[x])
        nouse = cards[x][0] * 2
        rev = reversible[i]

        for bitset in range((1 << l_len) - 1, -1, -1):
            if bitset & rev != rev:
                dp[bitset | rev] = max(dp[bitset | rev], dp[bitset] + use)
            dp[bitset] += nouse

    for bitset in range(1 << l_len):
        tmp = dp[bitset]
        for j in range(l_len):
            y = l_list[j]
            if bitset & (1 << j):
                tmp += sum(cards[y])
            else:
                tmp += cards[y][0] * 2
        res = max(res, tmp)

for x in range(n):
    if low_both[x] == 1:
        res += sum(cards[x])
    elif no_chance[x] == 1:
        res += cards[x][0] * 2

print(res / 2)