Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N=int(input())
xs = [None]
for _ in range(N):
    xs.append(list(map(int, input().split()))[::-1])
tops = [None] * (N+1)
for i in range(N):
    i += 1
    tops[i] = xs[i].pop()

cc = 0
rr = 0
while True:
    vs = set()
    nn = False
    for i in range(N):
        i += 1
        j = tops[i]
        if j == None:
            continue
        if i in vs or j in vs:
            continue
        if tops[j] == i:
            nn = True
            if len(xs[i]):
                tops[i] = xs[i].pop()
            else:
                tops[i] = None
                cc += 1
            if len(xs[j]):
                tops[j] = xs[j].pop()
            else:
                tops[j] = None
                cc += 1
            vs.add(i)
            vs.add(j)
    rr += 1
    if cc == N:
        break
    if not nn:
        rr = -1
        break

print(rr)


### FIXED CODE ###

import sys
input = sys.stdin.readline
N=int(input())
xs = [None]
for _ in range(N):
    xs.append(list(map(int, input().split()))[::-1])
tops = [None] * (N+1)
for i in range(N):
    i += 1
    tops[i] = xs[i].pop()

cc = 0
rr = 0
ns = [i+1 for i in range(N)]
while True:
    vs = set()
    nn = False
    nns = []
    for i in ns:
        j = tops[i]
        if j == None:
            continue
        if i in vs or j in vs:
            continue
        if tops[j] == i:
            nn = True
            if len(xs[i]):
                tops[i] = xs[i].pop()
            else:
                tops[i] = None
                cc += 1
            if len(xs[j]):
                tops[j] = xs[j].pop()
            else:
                tops[j] = None
                cc += 1
            vs.add(i)
            vs.add(j)
            nns.append(i)
            nns.append(j)
    ns = nns
    rr += 1
    if cc == N:
        break
    if not nn:
        rr = -1
        break

print(rr)
### BUGGY CODE ###

import heapq

def dijkstra(ad_lst, n, s, t):
    costs = [float('inf') for i in range(n+1)]
    costs[s] = 0
    Q = []
    heapq.heappush(Q, [costs[s], s])

    while(Q != []):
        c, u = heapq.heappop(Q)
        for v, c in ad_lst[u]:
            alt = costs[u] + c
            if alt < costs[v]:
                heapq.heappush(Q, [alt, v])
                costs[v] = alt

    return costs

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

route_y = {i: [] for i in range(n+1)}
route_s = {i: [] for i in range(n+1)}
for i in range(m):
    u, v, a, b = map(int, input().split())
    route_y[u].append([v,a])
    route_y[v].append([u,a])
    route_s[u].append([v,b])
    route_s[v].append([u,b])

cost_y = dijkstra(route_y, n, s, t)
cost_s = dijkstra(route_s, n, t, s)
cost_ys = [[cost_y[i]+cost_s[i], i] for i in range(1,n+1)]

cost_ys.sort()
yen = 10**15
k = 0
for i in range(n):
    while cost_ys[k][1]<=i: k+=1
    print(yen-cost_ys[k][0])
# inf = float('inf')
# result = [inf for _ in range(n+1)]
# min_cost = result[-1]
# for i in range(n, 0, -1):
#     if min_cost > cost_ys[i]:
#         min_cost = cost_ys[i]
#     result[i] = min_cost
# yen = 10**15
# for i in range(1, n+1):
#     print(yen - result[i])


### FIXED CODE ###

import heapq
from itertools import accumulate
inf = float('inf')

def dijkstra(ad_lst, n, s):
    costs = [inf for i in range(n+1)]
    costs[s], Q = 0, []
    heapq.heappush(Q, [costs[s], s])

    while(Q != []):
        c, u = heapq.heappop(Q)
        for v, c in ad_lst[u].items():
            if costs[u] + c < costs[v]:
                heapq.heappush(Q, [costs[u] + c, v])
                costs[v] = costs[u] + c

    return costs

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

route_y = {i: {} for i in range(n+1)}
route_s = {i: {} for i in range(n+1)}
for i in range(m):
    u, v, a, b = map(int, input().split())
    route_y[u][v] = a
    route_y[v][u] = a
    route_s[u][v] = b
    route_s[v][u] = b

cost_y = dijkstra(route_y, n, s)
cost_s = dijkstra(route_s, n, t)
result = list(accumulate([y+s for y,s in zip(cost_y, cost_s)][::-1], min))
yen = 10**15
[print(yen-result[i]) for i in range(n-1, -1, -1)]
### BUGGY CODE ###

"""
最小公倍数LCMを求めて、LCMを各Aで除した商を合計すればよい
と思ったけど、普通に最小公倍数を求めると、値が大きくなりすぎて処理できない。
なので、積は求めずに、素因数の足し引きだけ処理する。
"""
from math import gcd
from collections import Counter
mod = 10**9 +7
N = int(input())
A = list(map(int,input().split()))
factors = []
for i in range(N):
    a = A[i]
    tmp = []
    ceil = int(a**0.5)+1
    for d in range(2,ceil):
        for _ in range(100):
            if a%d==0:
                a//=d
                tmp.append(d)
            else:
                break
    if a != 1:
        tmp.append(a)
    factors.append(Counter(tmp))
    if i == 0:
        l = Counter(tmp)

for i in range(1,N):
    diff = factors[i]-l
    for k,v in diff.items():
        if k not in l:
            l[k] = 0
        l[k] += v

ans = 0
for factor in factors:
    diff = l - factor
    tmp = 1
    for k,v in diff.items():
        tmp *= pow(k,v,mod)
        tmp %= mod
    ans += tmp
    ans %= mod

print(ans)

### FIXED CODE ###

from math import gcd

def lcm(a, b):
    return a*b//gcd(a,b)
def main():
    N = int(input())
    A = list(map(int, input().split()))
    mod = 10**9 + 7
    LCM = 1
    for a in A:
        LCM = lcm(LCM, a)
    ans = 0
    for a in A:
        ans += (LCM//a)
        

    print(ans % mod)
main()
### BUGGY CODE ###

import sys #追加

n=int(input())
sys.setrecursionlimit(10**6*2)

s=input()
X=int(s,2)
ans=[]

ans_memo=[0]*(2**12)
#print(ans_memo)
ans_memo[1]=1
ans_memo[2]=1

def DEF(x,cnt):
    global ans_memo
    #print(x,cnt,ans_memo)
    if x==0:
        return 0
    if x<2**12:    
        if ans_memo[x]!=0:
            return ans_memo[x]
        else:
            if x%(str(bin(x)).count("1"))==0:
                ans_memo[x]=1
                return 1
            else:
                tmp=DEF(x%(str(bin(x)).count("1")),cnt+1)+1
                ans_memo[x]=tmp
                return tmp
    else:
        if x%(str(bin(x)).count("1"))==0:
            return 1
        else:
            tmp=DEF(x%(str(bin(x)).count("1")),cnt+1)+1
            return tmp


ans=[]

for i in range(n):
    tmp=2**(n-i-1)
    tmp_num=X
    #1の時
    if tmp&tmp_num:
        tmp_num-=tmp
        #print(bin(tmp_num),n-i-1)
        ans.append(DEF(tmp_num,0))
        
    else:
        tmp_num+=tmp
        #print(bin(tmp_num),n-i-1)
        ans.append(DEF(tmp_num,0))

#print(ans_memo)

for item in ans:
    print(item)
            









### FIXED CODE ###

def popcount(x):
    return bin(x).count("1")

n=int(input())
s=input()
X=int(s,2)

one_cnt=popcount(X)

modp=X%(one_cnt+1)
modm=X%(one_cnt-1) if one_cnt-1!=0 else 0

for i in range(n):
    if s[i]=="1":
        if one_cnt-1==0:
            print(0)
            continue
        else:
            num=(modm-pow(2,n-i-1,one_cnt-1))%(one_cnt-1)
    else:
        num=(modp+pow(2,n-i-1,one_cnt+1))%(one_cnt+1)

    #print(i,"num",num)
    cnt=1
    while num!=0:
        num=num%popcount(num)
        cnt+=1
    print(cnt)
### BUGGY CODE ###

from itertools import combinations
MOD = 10**9 + 7
n=int(input())
a=list(map(int,input().split()))
sum=0
for x,y in combinations(a,2):
   sum+=x*y%MOD
print(sum%MOD)

### FIXED CODE ###

mod = 10**9 + 7
n=int(input())
s=list(map(int,input().split()))
s2=sum(map(lambda x: x ** 2,s))
ans=(((sum(s))**2)-(s2))//2%mod
print(ans)
### BUGGY CODE ###

S = input()
def ABC(S):
    N = len(S)
    dp = [[0 for j in range(4)] for i in range(N+1)]
    model = 'ABC'
    for i in range(N, -1, -1):
        for j in range(3,-1,-1):
            if i == N and j == 3:
                dp[i][j] = 1
            elif i == N and j < 3:
                dp[i][j] = 0
            elif i < N and j == 3:
                if S[i] == '?':
                    dp[i][j] = 3 * dp[i+1][j]
                else:
                    dp[i][j] = dp[i+1][j]
            else:
                if S[i] == '?':
                    m1 = 3
                else:
                    m1 = 1
                if S[i] == '?' or S[i] == model[j]:
                    m2 = 1
                else:
                    m2 = 0
                dp[i][j] = m1 * dp[i+1][j] + m2 * dp[i+1][j+1]
    return dp[0][0] % (10**9 + 7)
print(ABC(S))

### FIXED CODE ###

S = input()
def ABC(S):
    N = len(S)
    dp = [[0 for j in range(4)] for i in range(N+1)]
    model = 'ABC'
    p = 10**9 + 7
    for i in range(N, -1, -1):
        for j in range(3,-1,-1):
            if i == N and j == 3:
                dp[i][j] = 1
            elif i == N and j < 3:
                dp[i][j] = 0
            elif i < N and j == 3:
                if S[i] == '?':
                    dp[i][j] = 3 * dp[i+1][j] % p
                else:
                    dp[i][j] = dp[i+1][j] % p
            else:
                if S[i] == '?':
                    m1 = 3
                else:
                    m1 = 1
                if S[i] == '?' or S[i] == model[j]:
                    m2 = 1
                else:
                    m2 = 0
                dp[i][j] = (m1 * dp[i+1][j])%p + m2 * (dp[i+1][j+1])%p
    return dp[0][0] % p
print(ABC(S))
### BUGGY CODE ###

from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n = int(input())
ab = []
edges = [[]for _ in range(n)]
for _ in range(n-1):
    a, b = list(map(lambda x: int(x)-1, input().split()))
    edges[a].append(b)
    edges[b].append(a)
    ab.append((a, b))

colors = defaultdict(int)


k = 1
init_v = 0
for v in range(n):
    if k < len(edges[v]):
        k = len(edges[v])
        init_v = v


# v-v2間の色をぬる
def dfs(v, parent):
    # v-parent間で使用済みの色は使えない
    if v < parent:
        palette = [i for i in range(k, 0, -1) if i != colors[(v, parent)]]
    else:
        palette = [i for i in range(k, 0, -1) if i != colors[(parent, v)]]
    for v2 in edges[v]:
        if v2 == parent:
            continue
        color = palette.pop()
        if v2 < v:
            colors[(v2, v)] = color
        else:
            colors[(v, v2)] = color
        dfs(v2, v)


dfs(init_v, -1)

print(k)
for a, b in ab:
    print(colors[(a, b)])


### FIXED CODE ###

from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n = int(input())
ab = []
edges = [[]for _ in range(n)]
for _ in range(n-1):
    a, b = list(map(lambda x: int(x)-1, input().split()))
    edges[a].append(b)
    edges[b].append(a)
    ab.append((a, b))

colors = defaultdict(int)


k = 1
init_v = 0
for v in range(n):
    if k < len(edges[v]):
        k = len(edges[v])
        init_v = v


def dfs(v, parent):
    palette = [i for i in range(len(edges[v])+1, 0, -1)
               if i != colors[(parent, v)]]
    for v2 in edges[v]:
        if v2 == parent:
            continue
        color = palette.pop()
        colors[(v2, v)] = color
        colors[(v, v2)] = color
        dfs(v2, v)


dfs(init_v, -1)

print(k)
for a, b in ab:
    print(colors[(a, b)])
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))

dic = {}
list_town = []
town = 1

for i, v in enumerate(A):
    dic[i+1] = v

for _ in range(K):
    list_town.append(town)
    town = dic[town]
    if town in list_town:
        stop_twon = town
        break

if N <= K:
    list_first_split = list_town[:list_town.index(stop_twon)]
    list_second_split = list_town[list_town.index(stop_twon):]
    print(list_second_split[(K - (len(list_first_split))) % len(list_second_split)])
else:
    print(town)

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))

dic = {}
for i, v in enumerate(A):
    dic[i+1] = v

town = 1
s = set()
l = []
for _ in range(K):
    l.append(town)
    s.add(town)
    town = dic[town]
    if town in s:
        stop_twon = town
        break
if N <= K:
    list_first_split = l[:l.index(stop_twon)]
    list_second_split = l[l.index(stop_twon):]
    print(list_second_split[(K - (len(list_first_split))) % len(list_second_split)])
else:
    print(town)
### BUGGY CODE ###

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

n = int(input())
edge = []
for i in range(n-1):
    edge.append(list(map(int,input().split())))

c_arr = sorted(list(map(int,input().split())))

m = sum(c_arr) - max(c_arr)
ans = [0]*(n + 1)
a,b = edge.pop()
ans[a] = c_arr.pop()
ans[b] = c_arr.pop()
uf = UnionFind(n)
uf.union(a,b)
while edge:
    for i in range(len(edge)):
        if uf.same_check(a,edge[i][0]):
            if not uf.same_check(a,edge[i][1]):
                ans[edge[i][1]] = c_arr.pop()
                uf.union(edge[i][0],edge[i][1])
                edge.pop(i)
                break
        elif uf.same_check(a,edge[i][1]):
            ans[edge[i][0]] = c_arr.pop()
            uf.union(edge[i][0],edge[i][1])
            edge.pop(i)
            break
print(m)
print(*ans[1:])        


### FIXED CODE ###

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

n = int(input())
edge = []
for i in range(n-1):
    edge.append(list(map(int,input().split())))

c_arr = sorted(list(map(int,input().split())))

m = sum(c_arr) - max(c_arr)
ans = [0]*(n + 1)
a,b = edge.pop()
ans[a] = c_arr.pop()
ans[b] = c_arr.pop()
uf = UnionFind(n)
uf.union(a,b)
while edge:
    for i in range(len(edge)):
        if uf.same_check(a,edge[i][0]):
            if not uf.same_check(a,edge[i][1]):
                ans[edge[i][1]] = c_arr.pop()
                uf.union(edge[i][0],edge[i][1])
                edge.pop(i)
                break
        elif uf.same_check(a,edge[i][1]):
            ans[edge[i][0]] = c_arr.pop()
            uf.union(edge[i][0],edge[i][1])
            edge.pop(i)
            break
print(m)
print(*ans[1:])
### BUGGY CODE ###

N=int(input())
c=0
for i in range(1,N+1):
  i=str(i)
  for j in range(1,N+1):
    j=str(j)
    if i[0]==j[-1] and i[-1]==j[0]:
      c+=1
print(c)

### FIXED CODE ###

N=int(input())
d=dict()
ans=0
for i in range(1,N+1):
  if not (str(i)[0],str(i)[-1]) in d:    
    d[(str(i)[0],str(i)[-1])]=1
  else:
    d[(str(i)[0],str(i)[-1])]+=1
for j in d:
  if (j[-1],j[0]) in d:
    ans+=d[j]*d[(j[-1],j[0])]
print(ans)
### BUGGY CODE ###

# ABC141d
import sys
import heapq
import math
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

a, b = map(int, input().split())
cd = []
for i in range(1, min(a, b) + 1):
    if (a % i != 0 or b % i != 0):
        continue
    flag = True
    for j in cd:
        if (j == 1):
            continue
        if (i % j == 0):
            flag = False
            break
    if (flag):
        cd.append(i)
print(len(cd))

### FIXED CODE ###

# ABC141d
import sys
import heapq
import math
import fractions
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

a, b = map(int, input().split())
cd = []


def prime_decomposition(n):
    i = 2
    table = set()
    while i * i <= n:
        while n % i == 0:
            n /= i
            table.add(i)
        i += 1
    if n > 1:
        table.add(n)
    return table


print(len(prime_decomposition(a).intersection(prime_decomposition(b)))+1)
exit()

for i in range(1, fractions.gcd(a, b) + 1):
    if (a % i != 0 or b % i != 0):
        continue
    flag = True
    for j in cd:
        if (j == 1):
            continue
        if (i % j == 0):
            flag = False
            break
    if (flag):
        cd.append(i)
print(len(cd))
### BUGGY CODE ###

N,K = map(int,input().split())
temp = []
c,t = K,-1
for i in range(N):
    temp.append(list(map(int,input().split())))
    temp.sort()
while c>0:
    t += 1
    c -= temp[t][1]
print(temp[t][0])

### FIXED CODE ###

N,K = map(int,input().split())
temp = []
c,t = K,-1
for i in range(N):
    temp.append(list(map(int,input().split())))
temp.sort()
while c>0:
    t += 1
    c -= temp[t][1]
print(temp[t][0])
### BUGGY CODE ###

import sys

import numba as nb
import numpy as np

input = sys.stdin.readline


@nb.njit("void(i8,i8,i8,i8[:,:],i8,i8[:,:],i8[:])", cache=True)
def dfs(H, W, D, A, Q, LR, ans):
    position = [(-1, -1)] * (H * W + 1)
    for h in range(H):
        for w in range(W):
            position[A[h][w]] = (h, w)

    mp = np.zeros(shape=(H * W + 1), dtype=np.int64)

    for i in range(1, H * W + 1 - D):
        h, w = position[i]
        y, x = position[i + D]
        mp[i] = abs(x - w) + abs(y - h)

    for i in range(Q):
        l, r = LR[i]
        q = (r - l) // D
        for k in range(q):
            ans[i] += mp[l + D * k]


def main():
    H, W, D = map(int, input().split())
    A = np.zeros(shape=(H, W), dtype=np.int64)
    for i in range(H):
        A[i] = tuple(map(int, input().split()))
    Q = int(input())
    LR = np.zeros(shape=(Q, 2), dtype=np.int64)
    for i in range(Q):
        LR[i] = tuple(map(int, input().split()))

    ans = np.zeros(shape=Q, dtype=np.int64)
    dfs(H, W, D, A, Q, LR, ans)

    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

import numba as nb
import numpy as np

input = sys.stdin.readline


@nb.njit("void(i8,i8,i8,i8[:,:],i8,i8[:,:],i8[:])", cache=True)
def dfs(H, W, D, A, Q, LR, ans):
    position = [(-1, -1)] * (H * W + 1)
    for h in range(H):
        for w in range(W):
            position[A[h][w]] = (h, w)

    mp = np.zeros(shape=(H * W + 1), dtype=np.int64)

    for i in range(1, H * W + 1 - D):
        h, w = position[i]
        y, x = position[i + D]
        mp[i + D] = abs(x - w) + abs(y - h)

    for d in range(1, D + 1):
        mp[d::D] = np.cumsum(mp[d::D])

    for i in range(Q):
        l, r = LR[i]
        ans[i] = mp[r] - mp[l]


def main():
    H, W, D = map(int, input().split())
    A = np.zeros(shape=(H, W), dtype=np.int64)
    for i in range(H):
        A[i] = tuple(map(int, input().split()))
    Q = int(input())
    LR = np.zeros(shape=(Q, 2), dtype=np.int64)
    for i in range(Q):
        LR[i] = tuple(map(int, input().split()))

    ans = np.zeros(shape=Q, dtype=np.int64)
    dfs(H, W, D, A, Q, LR, ans)

    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()
### BUGGY CODE ###

nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N, M = nl()

from collections import defaultdict
edges = defaultdict(set)
for i in range(M):
    u, v = nl()
    edges[u].add(v+N)
    edges[u+N].add(v+2*N)
    edges[u+2*N].add(v)

S, T = nl()

import queue
q = queue.Queue()
q.put((S, 0))

done = defaultdict(bool)
done[S] = True

while not q.empty():
    src, cost = q.get()
    for dst in edges[src]:
        if dst == T:
            print((cost+1) // 3)
            import sys
            sys.exit()

        if not done[dst]:
            done[dst] = True
            q.put((dst, cost+1))

print(-1)




### FIXED CODE ###

nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N, M = nl()

from collections import defaultdict
edges = defaultdict(set)
for i in range(M):
    u, v = nl()
    edges[u].add(v+N)
    edges[u+N].add(v+2*N)
    edges[u+2*N].add(v)

S, T = nl()

import queue
q = queue.Queue()
q.put((S, 0))

done = defaultdict(bool)
done[S] = True

while not q.empty():
    src, cost = q.get()
    for dst in edges[src]:
        if dst == T:
            print((cost+1) // 3)
            import sys
            sys.exit()

        if not done[dst]:
            done[dst] = True
            q.put((dst, cost+1))

print(-1)
### BUGGY CODE ###

s = list(input())

ans = 0
f = 1

while f:
    tmp = s
    f = 0
    for i in range(len(s)-2):
        if tmp[i:i+3] == ["A", "B", "C"]:
            s[i:i+3] = ["B", "C", "A"]
            ans += 1
            f = 1

print(ans)

### FIXED CODE ###

s = input().replace("BC", "D")

ans = 0
cnt = 0
for i in s[::-1]:
    if i == "D":
        cnt += 1
    elif i == "A":
        ans += cnt
    else:
        cnt = 0



print(ans)
### BUGGY CODE ###

N,M=map(int,input().split())
mod = 10**9+7
def framod(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod

def comb(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod

def cnt(n):
  s = sum([comb(n-i,i,mod)%mod for i in range(n//2+1)])
  s = s%mod
  return s

A0 = 0
ans = 1
for i in range(M):
  A1 = int(input()) - 1
  ans = (ans * cnt(A1-A0))%mod
  A0 = A1+2
ans = (ans * cnt(N-A0))%mod
print(ans)


### FIXED CODE ###

N,M=map(int,input().split())
mod = 10**9+7
fram = [1]
for i in range(1,N+1):
  fram.append(fram[-1]*i%mod)

#def framod(n, mod, a=1):
#    for i in range(1,n+1):
#        a = a * i % mod
#    return a

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod

def comb(n, k, mod):
    a=fram[n]
    b=fram[k]
    c=fram[n-k]
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod

def cnt(n):
  s = sum([comb(n-i,i,mod)%mod for i in range(n//2+1)])
  s = s%mod
  return s

A0 = 0
ans = 1
for i in range(M):
  A1 = int(input()) - 1
  ans = (ans * cnt(A1-A0))%mod
  A0 = A1+2
ans = (ans * cnt(N-A0))%mod
print(ans)
### BUGGY CODE ###

S = input()
N = len(S)
A = [0]*N
for i in range(N):
    n = i
    b = S[n]
    cnt = 0
    while True:
        if b=="R" and S[n+1]=="L":
            if cnt%2==0:
                A[n]+=1
            else:
                A[n+1]+=1
            break
        if b=="L" and S[n-1]=="R":
            if cnt%2==0:
                A[n]+=1
            else:
                A[n-1]+=1
            break
        if b=="R":
            n+=1
        else:
            n-=1
        cnt+=1
print(*A)

### FIXED CODE ###

S = input()
N = len(S)
A = [0]*N
b = "R"
R = 0
cnt = 0
for i in range(N):
    cnt+=1
    if S[i]=="R":
        if b=="R":
            continue
        else:
            cnt=1
            b = "R"
    elif S[i]=="L":
        if b=="L":
            if cnt%2==1:
                A[R]+=1
            else:
                A[R+1]+=1
        else:
            R = i-1
            b="L"
            n = cnt//2
            A[i-1]+=n
            A[i]+=(cnt-n)
            cnt=0
print(*A)
### BUGGY CODE ###

import sys
import itertools
from collections import deque
from operator import itemgetter

input = sys.stdin.readline
S = input()
counter = 0

for i in range(len(S)//2):
    if '01' in S:
        S = S.replace('01', '', 1)
        counter += 1
    if '10' in S:
        S = S.replace('10','', 1)
        counter += 1
print(2*counter)

### FIXED CODE ###

import sys
import itertools
from collections import deque
from operator import itemgetter

input = sys.stdin.readline
S = input()
counter = 0

A = S.count('1')
B = S.count('0')
print(2*min(A,B))