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

from collections import defaultdict, deque
N,M=map(int, input().split())
G = {i: [] for i in range(1, N+1)}
for _ in range(M):
    x,y=map(int,input().split())
    G[x].append(y)

dp = [-1]*(N+1)
for s in range(1, N+1):
    if dp[s] != -1:
        continue
    que = deque([s])
    dp[s] = 0
# for node in range(1, N+1):
#     for nx in G[node]:
#         dp[nx] = max(dp[nx], dp[node]+1)
    while que:
        node = que.popleft()
        for nx in G[node]:
            dp[nx] = max(dp[nx], dp[node]+1)
            que.append(nx)
        
print(max(dp))

### FIXED CODE ###

from collections import defaultdict, deque
N,M=map(int, input().split())
G = {i: [] for i in range(1, N+1)}
deg = [0]*(N+1)
for _ in range(M):
    x,y=map(int,input().split())
    G[x].append(y)
    deg[y] += 1

from collections import deque, defaultdict
S = [i for i in range(1, N+1) if deg[i]==0]
dp = [0]*(N+1)

def topological_sort(adj, indeg):
    """
    幅優先探索によるトポロジカルソート
    O(|V|+|E|)

    adj: 隣接リスト
    indeg: 各ノード入次数を管理するリスト

    ret: トポロジカルソートされたリスト
    """
    is_visited = [0]*(N+1)
    ret = []
    def bfs():
        """
        sからBFSする
        """
        queue = deque(S)
        while queue:
            u = queue.popleft()
            # queueには入次数0のノードが入っているのでretに追加
            # ret.append(u)

            for v in adj[u]: # uの子ノードを探索
                indeg[v] -= 1 #探索したら子の次数を減らす
                if (indeg[v] == 0):
                    # 入次数0かつ未訪問なら
                    queue.append(v)
                    dp[v] = max(dp[v], dp[u]+1)
                    is_visited[v] = 1
    
    bfs()
    
    # return ret

topological_sort(G, deg)
print(max(dp))
### BUGGY CODE ###

N,Y=map(int,input().split())
A=[]
for i in range(Y//10000+1):
    for j in range((Y-i*10000)//5000+1):
        c1=(Y-10000*i-5000*j)/1000
        c2=N-i-j
        if c1==c2:
            A=[i,j,c1]
            break
        if c1!=c2:
            continue
if len(A)==0:
    print("-1 -1 -1")
else:
    A[2]=int(A[2])
    print(str(A[0])+" "+str(A[1])+" "+str(A[2]))

### FIXED CODE ###

n,y=map(int,input().split())
for i in range(n+1):
	for j in range(n+1):
		if (y-(10000*i+5000*j))/1000\
		==n-i-j and n-i-j>=0:
			print(i,j,n-i-j)
			exit()
print(-1,-1,-1)
### BUGGY CODE ###

def solve(string):
    n = len(string)
    q_pos = [i for i in range(n) if string[n - i - 1] == "?"]
    table = [[0] * 13 for _ in range(2)]
    table[0][int(string.replace("?", "0")) % 13] = 1
    for i in range(len(q_pos)):
        base = pow(10, q_pos[i], 13)
        for j in range(13):
            for k in range(10):
                table[1][(j + k * base) % 13] += table[0][j]
        table[0] = table[1]
        table[1] = [0] * 13
    return str(table[0][5] % (10**9 + 7))


if __name__ == '__main__':
    print(solve(input()))


### FIXED CODE ###

def solve(string):
    n = len(string)
    q_pos = [i for i in range(n) if string[n - i - 1] == "?"]
    table = [[0] * 13 for _ in range(2)]
    table[0][int(string.replace("?", "0")) % 13] = 1
    for i in range(len(q_pos)):
        base = pow(10, q_pos[i], 13)
        for j in range(13):
            for k in range(10):
                table[1][(j + k * base) % 13] += table[0][j]
        for j in range(13):
            table[1][j] %= (10**9 + 7)
        table[0] = table[1]
        table[1] = [0] * 13
    return str(table[0][5])


if __name__ == '__main__':
    print(solve(input()))
### BUGGY CODE ###

import copy

def com(n,r,m):
    #a = math.factorial(n)%m
    a = 1
    for i in range(1,n+1):
        a *= i
        a %= m
    A = pow(a,m-2,m)
    
    
    b= copy.copy(A)   
    for i in range(n,r,-1):
        b = (b*i)%m
    
    c = copy.copy(A)
    for i in range(n,n-r,-1):
        c = (c*i)%m
       
    return (a*b*c)%m

def main():
    k = int(input())
    s = input()
    mod = 10**9+7
    z = [1]
    for i in range(1,k+1):
        y = z[-1]*26
        z.append(y%mod)
    l = len(s)

    N = k+2
    inv_t = [0]+[1]
    for i in range(2,N):
        inv_t.append(inv_t[mod % i] * (mod - int(mod / i)) % mod)
    #print(inv_t)
    
    ans = 0
    p = 1   #pow(25,i-len(s),mod)
    q = z[k]
    bai = 1
    for i in range(l,l+k+1):
        #base = p*q   #pow(26,len(s)+k-i,mod)
        #base = pow(25,i-len(s),mod) * pow(26,len(s)+k-i,mod)
        #bai = r
        #bai = com(i-1,len(s)-1,mod)
        #print(i,len(s),base,bai)
        ans += p*q*bai
        ans %= mod
        p *= 25
        q = z[l+k-i-1]
        bai = bai*i*inv_t[i+1-l]
        bai %= mod
    print(ans)
    
if __name__=="__main__":
    main()

### FIXED CODE ###

import copy

def com(n,r,m):
    #a = math.factorial(n)%m
    a = 1
    for i in range(1,n+1):
        a *= i
        a %= m
    A = pow(a,m-2,m)
    
    
    b= copy.copy(A)   
    for i in range(n,r,-1):
        b = (b*i)%m
    
    c = copy.copy(A)
    for i in range(n,n-r,-1):
        c = (c*i)%m
       
    return (a*b*c)%m

def main():
    k = int(input())
    s = input()
    mod = 10**9+7
    z = [1]
    for i in range(1,k+1):
        y = z[-1]*26
        z.append(y%mod)
    l = len(s)

    N = k+2
    inv_t = [0]+[1]
    for i in range(2,N):
        inv_t.append(inv_t[mod % i] * (mod - int(mod / i)) % mod)
    #print(inv_t)
    
    ans = 0
    p = 1   #pow(25,i-len(s),mod)
    #q = z[k]
    bai = 1
    for i in range(l,l+k+1):
        #base = p*q   #pow(26,len(s)+k-i,mod)
        #base = pow(25,i-len(s),mod) * pow(26,len(s)+k-i,mod)
        #bai = r
        #bai = com(i-1,len(s)-1,mod)
        #print(i,len(s),base,bai)
        ans += p*z[l+k-i]*bai
        ans %= mod
        p *= 25
        p %= mod
        #q = z[l+k-i-1]
        bai = bai*i*inv_t[i+1-l]
        bai %= mod
    print(ans)
    
if __name__=="__main__":
    main()
### BUGGY CODE ###

# -*- coding: utf-8 -*-
n = int(input())
numlist = list(map(int, input().split()))
dic = {}
for num in numlist:
  if num not in dic:
    dic[num] = 1
  else:
    dic[num] += 1
    
ansdic = {}
for key in dic.keys():
  n = dic[key]
  ansdic[key] = [int(n*(n-1)/2),int((n-1)*(n-2)/2)]
      
ansdic2 = {}
for key in ansdic.keys():
  sum = 0
  for key2 in ansdic.keys():
    if key == key2:
      sum += ansdic[key2][1]
    else:
      sum += ansdic[key2][0]
  ansdic2[key] = sum  
    
for num in numlist:
  print(ansdic2[num])

### FIXED CODE ###

# -*- coding: utf-8 -*-
n = int(input())
numlist = list(map(int, input().split()))
dic = {}
for num in numlist:
  if num not in dic:
    dic[num] = 1
  else:
    dic[num] += 1
    
tmpsum = 0
for value in dic.values():
  tmpsum += int(value*(value-1)/2)
ansdic = {}
for key in dic.keys():
  n = dic[key]
  ansdic[key] = tmpsum - n + 1      
    
for num in numlist:
  print(ansdic[num])
### BUGGY CODE ###

N = int(input())
A = [int(x) for x in input().split()]
ans = 0
for i in range(60):
    tmp = [x >> i & 1 for x in A]
    ans += (tmp.count(True) * tmp.count(False)) * 2 ** i
    ans = ans % (10 ** 9 + 7)
print(ans)


### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]
B = []
for x in A:
    tmp_lst = []
    for _ in range(60):
        tmp = x // 2
        tmp_lst.append(x - tmp * 2)
        x = tmp
    B.append(tmp_lst)

ans = 0
for i in range(60):
    tr, fl = 0, 0
    for x in B:
        if x[i]:
            tr += 1
        else:
            fl += 1
    ans += (tr * fl) * 2 ** i
    ans = ans % (10 ** 9 + 7)
print(ans)
### BUGGY CODE ###

from functools import reduce

def gcd_base(x, y):
    if x >= y:
        while y != 0:
            x, y = y, x % y
        return x
    else:
        while x != 0:
            y, x = x, y % x
        return y

def gcd(numbers):
    return reduce(gcd_base, numbers)

N = int(input())
A = list(map(int, input().split()))
GCD = []

for i in range(N):
    a = A.pop(0)
    GCD.append(gcd(A))
    A.append(a)

print(max(GCD))

### FIXED CODE ###

def gcd(x, y):
    if x >= y:
        while y != 0:
            x, y = y, x % y
        return x
    else:
        while x != 0:
            y, x = x, y % x
        return y

N = int(input())
A = list(map(int, input().split()))
L = [0, 0]
for ai in A:
    L.append(gcd(L[-1], ai))
 
R = [0, 0]
for ai in A[::-1]:
    R.append(gcd(R[-1], ai))
 
print(max(gcd(l, r) for l, r in zip(L, reversed(R))))
### BUGGY CODE ###

def calc(N, M, a, c):
    inf = 10 ** 7 + 1
    L = 2 ** N
    dp = [inf for _ in range(L)]
    dp[0] = 0
    C = [sum([_c[i] * 2 ** i for i in range(N)]) for _c in c]
    for _ in range(M):
        dp_x = list(dp)
        for i in range(M):
            for j in range(L):
                if dp[j] == inf:
                    continue
                dp_x[j | C[i]] = min(dp_x[j | C[i]], dp[j] + a[i])
            dp = dp_x
        if dp[L - 1] < inf:
            return dp[L - 1]
    return -1


(N, M) = tuple([int(s) for s in input().split(' ')])
a = [0 for _ in range(M)]
c = [[0 for _ in range(N)] for _ in range(M)]
for i in range(M):
    (_a, _b) = tuple([int(s) for s in input().split(' ')])
    a[i] = _a
    for _c in [int(s) for s in input().split(' ')]:
        c[i][_c - 1] = 1
print(calc(N, M, a, c))

### FIXED CODE ###

def calc(N, M, a, c):
    for j in range(N):
        u = sum([c[i][j] for i in range(M)])
        if u == 0:
            return -1
    inf = 10 ** 7 + 1
    L = 2 ** N
    dp = [inf for _ in range(L)]
    dp[0] = 0
    C = [sum([_c[i] * 2 ** i for i in range(N)]) for _c in c]
    for _ in range(M):
        dp_x = list(dp)
        for i in range(M):
            for j in range(L):
                if dp[j] == inf:
                    continue
                dp_x[j | C[i]] = min(dp_x[j | C[i]], dp[j] + a[i])
            dp = dp_x
        if dp[L - 1] < inf:
            return dp[L - 1]
    return -1


(N, M) = tuple([int(s) for s in input().split(' ')])
a = [0 for _ in range(M)]
c = [[0 for _ in range(N)] for _ in range(M)]
for i in range(M):
    (_a, _b) = tuple([int(s) for s in input().split(' ')])
    a[i] = _a
    for _c in [int(s) for s in input().split(' ')]:
        c[i][_c - 1] = 1
print(calc(N, M, a, c))
### BUGGY CODE ###

import numpy as np
from math import gcd
from functools import reduce

PC = True
SC = True

N = int(input())
A = list(map(int, input().split()))
A.sort(reverse = True)


for i in range(N):
  for j in range(N-1, i, -1):
    if A[i] < np.sqrt(A[j]):
      break
    if gcd(A[i],A[j]) != 1:
      PC = False
      break
        
p = reduce(gcd, A)
if p != 1:
  SC = False
      
if PC == True:
  print('pairwise coprime')
else:
  if SC == True:
    print('setwise coprime')
  else:
    print('not coprime')

### FIXED CODE ###

from math import gcd
from functools import reduce
import numpy as np

PC = True

N = int(input())
A = list(map(int, input().split()))
A.sort(reverse = True)

MAX = A[0]+1
mp = [0]*MAX

for i in A:
  mp[i] += 1

for i in range(2,MAX):
  if sum(mp[i::i])>1:
    PC = False
    break

if PC:
  print('pairwise coprime')
else:
  if reduce(gcd, A) == 1:
    print('setwise coprime')
  else:
    print('not coprime')
### BUGGY CODE ###

from collections import deque

h,w=map(int,input().split())
a = [input() for _ in range(h)]
move=((1,0),(0,1),(-1,0),(0,-1))

que=deque([])
visited=[[0]*w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j]=="#":
            que.append((i,j,0))
            visited[i][j]=1


while len(que)>0:       
    ci,cj,d=que.popleft()
    for mi,mj in move:
        ni,nj=mi+ci,mj+cj
        if 0<=ni<h and 0<=nj<w and visited[ni][nj]==0:
            if a[ni][nj]==".":
                visited[ni][nj]=1
                que.append((ni,nj,d+1))

print(d)

### FIXED CODE ###

from collections import deque

h,w=map(int,input().split())
a = [input() for _ in range(h)]
move=((1,0),(0,1),(-1,0),(0,-1))

que=deque([])
visited=[[0]*w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j]=="#":
            que.append((i,j,0))
            visited[i][j]=1


while len(que)>0:       
    ci,cj,d=que.popleft()
    for mi,mj in move:
        ni,nj=mi+ci,mj+cj
        if 0<=ni<h and 0<=nj<w and visited[ni][nj]==0:
            if a[ni][nj]==".":
                visited[ni][nj]=1
                que.append((ni,nj,d+1))

print(d)
### BUGGY CODE ###

from collections import Counter
n = int(input())
li = [input() for _ in range(n)]
a = Counter(li)
keys = [k for k, v in a.items() if v == max(a.values())]
keys = sorted(keys)
for i in keys:
    print(i)

### FIXED CODE ###

from collections import Counter
n = int(input())
li = [input() for _ in range(n)]
a = Counter(li)
mx = max(a.values())
keys = [k for k, v in a.items() if v == mx]
keys = sorted(keys)
for i in keys:
    print(i)
### BUGGY CODE ###

n, k, q = list(map(int, input().split()))

b = [k]*n

for i in range(q):
    a = int(input())
    b[a-1] += 1
    b = list(map(lambda x: x-1, b))

for i in range(len(b)):
    if b[i] > 0:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

n, k, q = list(map(int, input().split()))

b = [k]*n

for i in range(q):
    a = int(input())
    b[a-1] += 1

b = list(map(lambda x: x-q, b))

for i in range(len(b)):
    if b[i] > 0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

N = int(input())
A = [int(s) for s in input().split()]

mod_number = 10**9 + 7

total = 0
for i in range(0, N - 1):
    j_total = sum(A[i+1:N])
    total += A[i] * j_total

ans = total % mod_number

print(ans)

### FIXED CODE ###

N = int(input())
A = [int(s) for s in input().split()]

mod_number = 10**9 + 7
sum_A = sum(A)
total = 0
for i in range(0, N - 1):
    sum_A = sum_A - A[i]
    total += A[i] * sum_A

ans = total % mod_number

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

import sys
sys.setrecursionlimit(10**8)

n,q=map(int,input().split())
Graph=[[] for _ in range(n+1)]
score=[0 for _ in range(n+1)]
for _ in range(n-1):
    a,b=map(int,input().split())
    Graph[a].append(b)
    Graph[b].append(a)

for _ in range(q):
    p,x=map(int,input().split())
    score[p]+=x

seen=[False for _ in range(n+1)]
ans=[0 for _ in range(n+1)]
ans[1]=score[1]
def dfs(v):
    seen[v]=True
    for nv in Graph[v]:
        if seen[nv]:
            continue
        else:
            ans[nv]=ans[v]+score[nv]
            dfs(nv)

dfs(1)
print(*ans[1:])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
#普通にinputするよりstdin.readlineのほうがはやい
input = sys.stdin.readline 
n,q=map(int,input().split())
Graph=[[] for _ in range(n+1)]
ans=[0 for _ in range(n+1)]


for _ in range(n-1):
    a,b=map(int,input().split())
    Graph[a].append(b)
    Graph[b].append(a)

for _ in range(q):
    p,x=map(int,input().split())
    ans[p]+=x

def dfs(v,par):
    for nv in Graph[v]:
        if nv==par:
            continue
        else:
            ans[nv]+=ans[v]
            dfs(nv,v)

dfs(1,-1)
print(*ans[1:])
### BUGGY CODE ###

n, k, q = map(int, input().split())
points=[k]*(n+1)
win=[]
for i in range(q):
  win.append(int(input()))
for j in range(1,n+1):
  if points[j]-(q-win.count(j))>0:
    print('Yes')
  else:
    print('No')

### FIXED CODE ###

n, k, q = map(int, input().split())
points=[k]*(n+1)
cnt=[0]*(n+1)
for i in range(q):
  cnt[int(input())]+=1
for j in range(1,n+1):
  if k-(q-cnt[j])>0:
    print('Yes')
  else:
    print('No')
### BUGGY CODE ###

import numpy as np

n, m = map(int, input().split())
price = np.zeros(m, dtype=int)
treasure = np.zeros(m, dtype=int)
for i in range(m):
  price[i], _ = map(int, input().split())
  for c in map(int, input().split()):
    treasure[i] += 1 << (c - 1)
dp = np.ones(1 << n, dtype=int) * (10 ** 8 + 1)
dp[0] = 0
for bit in range(1 << n):
  next_bit = treasure | bit
  next_cost = price + dp[bit]
  for i in range(m):
    dp[next_bit[i]] = min(dp[next_bit[i]], next_cost[i])
if dp[-1] > 10 ** 8:
  print(-1)
else:
  print(dp[-1])

### FIXED CODE ###

n, m = map(int, input().split())
price = [0] * m
treasure = [0] * m
for i in range(m):
  price[i], _ = map(int, input().split())
  for c in map(int, input().split()):
    treasure[i] += 1 << c-1
dp = [10 ** 8 + 1] * (1 << n)
dp[0] = 0
for bit in range((1 << n) - 1):
  cost = dp[bit]
  for i in range(m):
    next_bit = treasure[i] | bit
    next_cost = price[i] + cost
    dp[next_bit] = min(dp[next_bit], next_cost)
if dp[-1] > 10 ** 8:
  print(-1)
else:
  print(dp[-1])
### BUGGY CODE ###

from collections import defaultdict
N = int(input())
S = input()
ans = 0
for i in range(1, N+1):
    d = defaultdict(list)
    for j in range(N - i + 1):
        d[S[j:j+i]].append(j)
    # print(d)
    for l in d.values():
        for j in range(len(l) - 1):
            if l[j] + i <= l[j + 1]:
                ans = max(ans, i)
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
dp = [[0] * 5005 for _ in range(5005)]
for i in range(N - 1, -1, -1):
    for j in range(N - 1, -1, -1):
        if S[i] != S[j]:
            dp[i][j] = 0
        else:
            dp[i][j] = dp[i + 1][j + 1] + 1
ans = 0
for i in range(N):
    for j in range(i + 1, N):
        now = min(dp[i][j], j - i)
        ans = max(ans, now)
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
dp = [float("inf") for i in range(2 ** n)]
dp[0] = 0

for i in range(m):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    for j in range(2 ** b):
        num = 0
        temp = bin(j + 2 ** b)[3:]
        for k in range(b):
            if temp[k] == "1":
                num += 2 ** (c[k] - 1)
        for k in range(2 ** n):
            dp[k | num] = min(dp[k | num], dp[k] + a)
if dp[2 ** n - 1] == float("inf"):
    print(-1)
else:
    print(dp[2 ** n - 1])

### FIXED CODE ###

n, m = map(int, input().split())
dp = [float("inf") for i in range(2 ** n)]
dp[0] = 0

for i in range(m):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    num = 0
    for j in range(b):
        num += 2 ** (c[j] - 1)
    for k in range(2 ** n):
        dp[k | num] = min(dp[k | num], dp[k] + a)
if dp[2 ** n - 1] == float("inf"):
    print(-1)
else:
    print(dp[2 ** n - 1])
### BUGGY CODE ###

from collections import deque

H, W = list(map(int, input().split()))
grid = []
for _ in range(H):
    grid.append(list(input()))

dq = deque([(0, 0, 1)])
while dq:
    h, w, cnt = dq.popleft()
    grid[h][w] = cnt
    nexts = [(h+1, w, cnt+1), (h-1, w, cnt+1), (h, w+1, cnt+1), (h, w-1, cnt+1)]
    for y, x, c in nexts:
        if 0 <= y and y < H and 0 <= x and x < W:
            if grid[y][x] == '.':
                dq.append((y, x, c))
            if type(grid[y][x]) == int and c < grid[y][x]:
                dq.append((y, x, c))

if grid[-1][-1] == '.' or grid[-1][-1] == '#':
    print(-1)
    exit() 

sharp_num = 0
max_num = 0
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            sharp_num += 1
print(H * W - grid[-1][-1] - sharp_num)





### FIXED CODE ###

import sys
from collections import deque
 
h,w = map(int, sys.stdin.readline().split())
maze = [list(sys.stdin.readline()) for _ in range(h)]
dis = [[-1 for _ in range(w)] for _ in range(h)]
 
que = deque()
que.append((0,0))
dis[0][0] = 1
 
while que:
    y,x = que.popleft()
    for dx, dy in ((1,0), (0,1), (-1, 0), (0, -1)):
        nx = x + dx
        ny = y + dy
        if (nx < 0) or (nx > w-1) or (ny < 0) or (ny > h-1): continue
        if (maze[ny][nx] == '.') and (dis[ny][nx] == -1):
            dis[ny][nx] = dis[y][x] + 1
            que.append((ny, nx))
 
ans = 0
black_num = 0
for m in maze:
    black_num += m.count('#')
 
if dis[h-1][w-1] == -1:
    ans = -1
else:
    ans = w*h - black_num - dis[h-1][w-1]
 
print(ans)
### BUGGY CODE ###

N = int(input())

divisor = 2
modsum = 0
for i in range(N-1):
    # print(i + 1)
    # print(divisor)
    modsum += (i + 1) % divisor
    divisor += 1
    
print(modsum)

### FIXED CODE ###


N = int(input())

calc_N =  N-1

if calc_N % 2 == 1:
    O = calc_N // 2
    output = (1+calc_N) * O + O + 1
else :
    O = calc_N // 2
    output = (1+calc_N) * O
    
print(output)
### BUGGY CODE ###

n,m=(int(i) for i in input().split())
#print(n,m)

mod=10**9+7
ans=1

if abs(n-m) > 1:
  print(0)
elif n==m:
  while n > 0:
    ans*=n%mod
    n-=1
  ans=ans*ans*2%mod
  print(ans)
else:
  if n < m:
    n,m=m,n
  while n > 0:
    ans*=n%mod
    n-=1
  ans=ans*ans//(m+1)%mod
  print(ans)
    

### FIXED CODE ###

n,m=(int(i) for i in input().split())
#print(n,m)

mod=10**9+7
ans=1

if abs(n-m) > 1:
  print(0)
elif n==m:
  for i in range(n,0,-1):
    ans=ans%mod
    ans*=i
  ans=ans*ans*2%mod
  print(ans)
else:
  for i in range(n,0,-1):
    ans=ans%mod
    ans*=i
  for i in range(m,0,-1):
    ans=ans%mod
    ans*=i
  print(ans%mod)
### BUGGY CODE ###

s = input()
n = len(s)
for i in range(n):
  s=s.replace('01','')
  s=s.replace('10','')
print(n-len(s))

### FIXED CODE ###

s = input()
c1,c2=s.count('0'),s.count('1'),
print(min(c1,c2)*2)
### BUGGY CODE ###

from collections import deque
 
H, W = map(int, input().split())
A = [list(input()) for i in range(H)]
 
INF = float('inf')
dx = [1, 0, -1, 0]
dy = [0, 1, 0 , -1]
 
def bfs(i, j):
    D = [[INF] * W for i in range(H)]
    que = deque()
    que.append([i, j])
    D[i][j] = 0
    
    while que != []:
        p = que.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx < H and 0 <= ny < W and A[nx][ny] != '#' and D[nx][ny] == INF:
                que.append([nx, ny])
                D[nx][ny] = D[p[0]][p[1]] + 1
            elif 0 <= nx < H and 0 <= ny < W and A[nx][ny] == '#':
                D[nx][ny] = D[p[0]][p[1]] + 1
                return D[nx][ny]
 
ans = 0
for i in range(H):
    for j in range(W):
        if A[i][j] == '.':
            tmp = bfs(i, j)
            ans = max(ans, tmp)
            
print(ans)

### FIXED CODE ###

from collections import deque
 
H, W = map(int, input().split())
A = [list(input()) for i in range(H)]
 
que = deque()
INF = float('inf')
dx = [1, 0, -1, 0]
dy = [0, 1, 0 , -1]            
D = [[INF] * W for i in range(H)]

for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            que.append([i, j])
            D[i][j] = 0
                       
def bfs():
    while len(que) != 0:
        p = que.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx < H and 0 <= ny < W and A[nx][ny] != '#' and D[nx][ny] == INF:
                que.append([nx, ny])
                D[nx][ny] = D[p[0]][p[1]] + 1
    
bfs()

ans = 0
for i in range(H):
    for j in range(W):
        tmp = D[i][j]
        ans = max(ans, tmp)
        
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n = int(input())
alist = list(map(int,input().split()))
binlist = [0]*60
mod_number = 10**9+7
for a in alist:
    a_bin = bin(a)
    for i in range(len(a_bin)-2):
        if int(a_bin[-(i+1)])==1:
            binlist[-(i+1)] += 1
            #print(a,a_bin,i,binlist)
ans = 0
for i in range(60):
    ans = (ans + binlist[-(i+1)]*(n-binlist[-(i+1)])*pow(2,i))%mod_number
    
print(ans)

### FIXED CODE ###

n = int(input())
alist = list(map(int,input().split()))
binlist = [0]*60
mod_number = 10**9+7

def dec2bin(target):
    amari = []
    while target != 0:
        amari.append(target%2)
        target = target//2
    amari.reverse()
    return amari

for a in alist:
    a_bin = dec2bin(int(a))
    for i in range(len(a_bin)):
        if int(a_bin[-(i+1)])==1:
            binlist[-(i+1)] += 1
            #print(a,a_bin,i,binlist)
ans = 0
for i in range(60):
    ans = (ans + binlist[-(i+1)]*(n-binlist[-(i+1)])*pow(2,i))%mod_number
    
print(ans)
### BUGGY CODE ###

n,x,y=map(int,input().split())
ans=[0]*n
for i in range(1,n+1):
    for j in range(i+1,n+1):
        a1=abs(i-j)
        a2=abs(x-i)+1+abs(y-j)
        a3=abs(y-i)+1+abs(x-j)
        d=min(a1,a2,a3)
        ans[d]+=1

for i in range(1,n):
    print(ans[i])
   

### FIXED CODE ###

n,x,y=map(int,input().split())
ans=[0]*n #個数を数えるのにバケットを用意する
for i in range(1,n+1): #i<jなるすべての頂点の組について最短距離を求める
 for j in range(i+1,n+1):
   dist1=j-i
   dist2=abs(x-i)+abs(y-j)+1
   dist3=abs(y-i)+abs(x-j)+1
   d=min(dist1,dist2,dist3) #最短距離は上式により求められる
   ans[d]+=1 #最短距離がdとなる組の個数を1増やす
for i in range(1,n):
 print(ans[i])