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

H,W = map(int, input().split())

S_array = [["#" for _ in range(W+2)]] + [["#"] + list(input()) + ["#"] for i in range(H)] + [["#" for _ in range(W+2)]]

def connection_check(target_list):
    connection = 0
    connection_list = list()
    
    for i in range(len(target_list)):
        if target_list[i]=="#":
            connection_list += [connection for _ in range(connection)]
            connection_list += [0]
            connection = 0
        elif target_list[i]==".":
            connection += 1
    
    return connection_list

W_connection_array = [[0 for _ in range(W+2)]] + [connection_check(S_array[i]) for i in range(1,H+1)] + [[0 for _ in range(W+2)]]
H_connection_array = [[0 for _ in range(H+2)]] + [connection_check([row[i] for row in S_array]) for i in range(1,W+1)] + [[0 for _ in range(H+2)]]

#print(W_connection_array)
#print(H_connection_array)

ans = 0

for i in range(1,H+1):
    for j in range(1,W+1):
        temp_ans = W_connection_array[i][j] + H_connection_array[j][i]
        if ans < temp_ans:
            ans = temp_ans

print(ans - 1) #自分自身の分の重複加算を引く

### FIXED CODE ###

H,W = map(int, input().split())

S_array = [["#" for _ in range(W+2)]] + [["#"] + list(input()) + ["#"] for i in range(H)] + [["#" for _ in range(W+2)]]

def connection_check(target_list):
    connection = 0
    connection_list = list()
    
    for i in range(len(target_list)):
        if target_list[i]=="#":
            connection_list += [connection for _ in range(connection)]
            connection_list += [0]
            connection = 0
        elif target_list[i]==".":
            connection += 1
    
    return connection_list

W_connection_array = [[0 for _ in range(W+2)]] + [connection_check(S_array[i]) for i in range(1,H+1)] + [[0 for _ in range(W+2)]]
H_connection_array = [[0 for _ in range(H+2)]] + [connection_check([row[i] for row in S_array]) for i in range(1,W+1)] + [[0 for _ in range(H+2)]]

#print(W_connection_array)
#print(H_connection_array)

ans = 0

for i in range(1,H+1):
    for j in range(1,W+1):
        temp_ans = W_connection_array[i][j] + H_connection_array[j][i]
        if ans < temp_ans:
            ans = temp_ans

print(ans - 1) #自分自身の分の重複加算を引く
### BUGGY CODE ###

N, K = map(int, input().split())
lis = list(map(int, input().split()))
lis = sorted(lis)
p = 10**9+7
fac_lis = [[0] for i in range(N)]
fac_lis[0] = 1
max_ans = 0
min_ans = 0

for i in range(1,N):
  fac_lis[i] = fac_lis[i-1]*(i+1)

def combi(n,k,num_lis,big_num):
  if n == k:
    return 1
  else:
  	return num_lis[n-1]*pow(num_lis[k-1], big_num-2, big_num)*pow(num_lis[n-k-1], big_num-2, big_num) % big_num

for i in range(K-1,N):
  max_ans += lis[i]*combi(i, K-1, fac_lis, p) % p
  
for i in range(N-K+1):
  min_ans += lis[i]*combi(N-(i+1), K-1, fac_lis, p) % p

ans = (max_ans - min_ans) % p
print(ans)

### FIXED CODE ###

# フェルマーの小定理
N, K = map(int, input().split())
A = list(map(int, input().split()))
 
m = 1000000007
 
fac = [0] * (N + 1)
fac[0] = 1
for i in range(N):
    fac[i + 1] = fac[i] * (i + 1) % m
 
 
def mcomb(n, k):
    if n == 0 and k == 0:
        return 1
    if n < k or k < 0:
        return 0
    return fac[n] * pow(fac[n - k], m - 2, m) * pow(fac[k], m - 2, m) % m
 
 
A.sort(reverse=True)
maxX = 0
for i in range(N - K + 1):
    maxX += A[i] * mcomb(N - (i + 1), K - 1)
    maxX %= m

A.sort()
minX = 0
for i in range(N - K + 1):
    minX += A[i] * mcomb(N - (i + 1), K - 1)
    minX %= m

print((maxX - minX) % m)
### BUGGY CODE ###


def resolve():
    INF = 10 ** 18
    N, K = map(int, input().split())
    P = list(map(lambda x: int(x) - 1, input().split()))
    C = list(map(int, input().split()))

    visited = [0] * N
    cycles = []

    for i in range(N):
        if visited[i]:
            continue
        score = []
        v = i
        visited[v] = True
        score.append(C[v])
        while not visited[P[v]]:
            v = P[v]
            visited[v] = True
            score.append(C[v])
        cycles.append(score)

    ans = -INF
    for cy in cycles:
        length = len(cy)
        c_num = max(0, (K - 1) // length - 1)
        total = max(0, sum(cy) * c_num)
        rest = K - (c_num * length)
        l_cy = cy + cy + cy
        for l in range(length):
            total_rest = 0
            for diff in range(rest):
                total_rest += l_cy[l + diff]
                ans = max(ans, total + total_rest)

    print(ans)


if __name__ == "__main__":
    resolve()

### FIXED CODE ###


def resolve():
    INF = 10 ** 18
    N, K = map(int, input().split())
    P = list(map(lambda x: int(x) - 1, input().split()))
    C = list(map(int, input().split()))

    visited = [0] * N
    cycles = []

    for i in range(N):
        if visited[i]:
            continue
        score = []
        v = i
        visited[v] = True
        score.append(C[v])
        while not visited[P[v]]:
            v = P[v]
            visited[v] = True
            score.append(C[v])
        cycles.append(score)

    ans = -INF
    for cy in cycles:
        length = len(cy)
        c_num = max(0, (K - 1) // length - 1)
        total = max(0, sum(cy) * c_num)
        rest = K - (c_num * length)
        l_cy = cy + cy + cy
        for l in range(length):
            total_rest = 0
            for diff in range(rest):
                total_rest += l_cy[l + diff]
                ans = max(ans, total + total_rest)

    print(ans)


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

import sys
read = sys.stdin.read
def main():
    def find(x):
        if par[x] < 0:
            return x
        else:
            par[x] = find(par[x])
            return par[x]
    def unite(x, y):
        x = find(x)
        y = find(y)
        if x == y:
            return False
        else:
            if par[x] > par[y]:
                x, y = y, x
            par[x] += par[y]
            par[y] = x
            return True
    def same(x, y):
        return find(x) == find(y)
    def members(x):
        root = find(x)
        return [i for i in range(n) if find(i) == root]

    n, m, k = map(int, input().split())
    par = [-1] * n
    friend = {e: set() for e in range(n)}
    foe = {e: set() for e in range(n)}
    for _ in range(m):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        unite(a, b)
        friend[a].add(b)
        friend[b].add(a)
    m = map(int, read().split())
    cd = zip(m, m)
    for c, d in cd:
        c -= 1
        d -= 1
        foe[c].add(d)
        foe[d].add(c)
    for i1 in range(n):
        r = len(set(members(i1)) - friend[i1] - foe[i1]) - 1
        print(r, end=' ')

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
from collections import defaultdict
def main():
    def find(x):
        if par[x] < 0:
            return x
        else:
            par[x] = find(par[x])
            return par[x]
    def unite(x, y):
        x = find(x)
        y = find(y)
        if x == y:
            return False
        else:
            if par[x] > par[y]:
                x, y = y, x
            par[x] += par[y]
            par[y] = x
            return True
    def members(x):
        root = find(x)
        return [i for i in range(n) if find(i) == root]

    n, m, k = map(int, input().split())
    num_of_friends = [-1] * n
    par = [-1] * n
    for _ in range(m):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        unite(a, b)
        num_of_friends[a] += -1
        num_of_friends[b] += -1
    roots = defaultdict(int)
    #roots = {e: set() for e in range(n)}
    for i2 in range(n):
        roots[find(i2)] += 1
    for i3 in range(n):
        #num_of_friends[i3] += len(roots[find(i3)])
        num_of_friends[i3] += roots[find(i3)]
    for _ in range(k):
        c, d = map(int, input().split())
        c -= 1
        d -= 1
        if find(c) == find(d):
            num_of_friends[c] -= 1
            num_of_friends[d] -= 1

    for i in range(n):
        print(num_of_friends[i], end=' ')

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

n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[1000000000]*n
dp[0]=0
for i in range (1,n):
    for j in range(max(i-k,0),i):
        dp[i]=min(dp[i],dp[j]+abs(h[i]-h[j]))
print(dp[n-1])

### FIXED CODE ###

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

dp=[1000000000]*n
dp[0]=0
for i in range (1,n):
    for j in range(max(i-k,0),i):
        dp[i]=min(dp[i],dp[j]+abs(h[i]-h[j]))
print(dp[n-1])
### BUGGY CODE ###

N, K = [int(s) for s in input().split()]
rans = []
for _ in range(K):
    l, r= [int(s) for s in input().split()]
    rans.append((l, r))
rans.sort()

prev = -1
newrans = []
for ran in rans:
    l, r = ran
    if l <= prev:
        newrans[-1] = max(r, newrans[-1])
    else:
        newrans.append([l,r])
    prev = max(prev, r)

rans = newrans
sums = [0, 1]
s = 1
# print(rans)
for i in range(2, N+1):
    # print(sums, i)
    for ran in rans:
        l = i - ran[0]
        r = max(i - ran[1] - 1, 0)
        # print(l, r, s)
        if l >= 0:
            s += sums[l] - sums[r]
    sums.append(s)
# print(sums)
if N == 1:
    print(1)
else:
    print((sums[-1] - sums[-2]) % 998244353)


### FIXED CODE ###

N, K = [int(s) for s in input().split()]
rans = []
for _ in range(K):
    l, r= [int(s) for s in input().split()]
    rans.append((l, r))
rans.sort()

prev = -1
newrans = []
for ran in rans:
    l, r = ran
    if l <= prev:
        newrans[-1] = max(r, newrans[-1])
    else:
        newrans.append([l,r])
    prev = max(prev, r)

MOD = 998244353

rans = newrans
sums = [0, 1]
s = 1
# print(rans)
for i in range(2, N+1):
    # print(sums, i)
    for ran in rans:
        l = i - ran[0]
        r = max(i - ran[1] - 1, 0)
        # print(l, r, s)
        if l >= 0:
            s = (s + sums[l] - sums[r]) % 998244353
    sums.append(s)
# print(sums)
if N == 1:
    print(1)
else:
    print((sums[-1] - sums[-2]) % 998244353)
### BUGGY CODE ###

def resolve():
    n, k, q = map(int, input().split())
    score = [k for _ in range(n)]
    for _ in range(q):
        a = int(input())
        stay = score[a-1]
        score = list(map(lambda x:x-1, score))
        score[a-1] = stay
    for i in range(n):
        if score[i] > 0:
            print("Yes")
        else:
            print("No")
resolve()

### FIXED CODE ###

def resolve():
    n, k, q = map(int, input().split())
    score = [0] * n
    for _ in range(q):
        a = int(input())
        score[a-1] += 1
    for i in range(n):
        s = k + score[i] - q
        if s > 0:
            print("Yes")
        else:
            print("No")
resolve()
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
 
def main():
    n=int(input())
    A=list(map(int, input().split()))
    ans = 0
    mod = 10**9 + 7
    for i in range(60):
        q = sum(map(lambda x:((x >> i) & 0b1),A))
        ans += q*(n-q)*pow(2, i, mod)
        ans = ans % mod
    print(ans)
 
if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
 
def main():
    n=int(input())
    A=list(map(int, input().split()))
    ans = 0
    mod = 10**9 + 7
    for i in range(60):
        q = sum(map(lambda x:((x >> i) & 0b1),A))
        ans += q*(n-q)*pow(2, i, mod)
        ans = ans % mod
    print(ans)
 
if __name__=='__main__':
    main()
### BUGGY CODE ###

import bisect

N = int(input())
A = sorted(map(int, input().split()))
B = sorted(map(int, input().split()))
C = sorted(map(int, input().split()))
D = len(C)

ans = 0
for i in A:
    for k in B:
        if k <= i:
            continue
        ans += D - bisect.bisect_right(C,k)
print(ans)

### FIXED CODE ###

import bisect

N = int(input())
A = sorted(map(int, input().split()))
B = sorted(map(int, input().split()))
C = sorted(map(int, input().split()))

ans = 0
for i in B:
    ans += bisect.bisect_left(A,i)*(N - bisect.bisect_right(C,i))
print(ans)
### BUGGY CODE ###

def solve():
    
    ans=0
    for i in range(n-1):
        for j in range(i+1,n):
            ans+=a[i]^a[j]
    
    print(ans%(10**9+7))
    
n=int(input())
a=list(map(int,input().split()))
solve()

### FIXED CODE ###

import sys
input=sys.stdin.readline
n=int(input())
a=tuple(map(int,input().split()))
mod=10**9+7
cnt=[0]*60

for temp in a:
    if temp==0:continue
    digit=len(bin(temp))-2
    for j in range(digit):
        if (temp>>j)&1:
            cnt[j]=cnt[j]+1

#print(cnt)
ans=0
for i in range(60):
    if cnt[i]==0:continue
    ans=(ans+pow(2,i)*cnt[i]*(n-cnt[i]))%mod
print(ans%mod)
### BUGGY CODE ###

import sys
from collections import defaultdict


def main():
    n = int(sys.stdin.readline().strip())
    a = [int(s) for s in sys.stdin.readline().strip().split(' ')]

    def do_it(num):
        if num == 1:
            return {}
        cur = num
        dic = defaultdict(int)
        for i in range(2, num+1):
            if cur == 1:
                break
            while cur % i == 0:
                dic[i] += 1
                cur //= i
        return dic

    d = defaultdict(int)
    d_list = []
    for ai in a:
        di = do_it(ai)
        d_list.append(di)
        keys = di.keys()
        for key in keys:
            d[key] = max(d[key], di[key])

    ans = 0
    for i in range(n):
        cur = 1
        keys = d.keys()
        d_i = d_list[i]
        for key in keys:
            diff = d[key] - d_i[key]
            for j in range(diff):
                cur *= key
                cur %= 10 ** 9 + 7
        ans += cur
        ans %= 10 ** 9 + 7
    print(ans)


main()


### FIXED CODE ###

def gcd(a,b):
  if b == 0:
    return a
  return gcd(b, a % b)
 
def lcm(a,b):
  return a * b // gcd(a,b)
 
n = int(input())
av = list(map(int, input().split(' ')))
alcm = 1
for i in av:
  alcm = lcm(alcm, i)
 
tot = 0
for i in range(n):
  tot += alcm // av[i]
 
print(tot % 1000000007)
### BUGGY CODE ###

N = int(input())
C = input()

for i in range(N):
    if C[i] == "1":
        X = C[:i] + "0" + C[i+1:]
    else:
        X = C[:i] + "1" + C[i+1:]

    N = int(X,2)
    ans = 0
    while N > 0:
        cnt = 0
        for c in format(N,"b"):
            if c == "1":
                cnt += 1
        N %= cnt
        ans += 1
    print(ans)

### FIXED CODE ###

n = int(input())
x = input()

def count(n):
    cnt = 0
    while n:
        cnt += n % 2
        n //= 2
    return cnt

LIMIT = 5*10**5
dp = [0] * LIMIT
for i in range(1, LIMIT):
    dp[i] = dp[i % count(i)]+1

c = x.count("1")
a = int(x,2) % (c+1)

if c == 1:
    for i in range(n):
        if x[i] == "0":
            print(dp[(a + pow(2, n-i-1, c+1)) % (c+1)] + 1)
        else:
            print(0)
    exit()

b = int(x,2) % (c-1)
for i in range(n):
    if x[i] == "0":
        print(dp[(a + pow(2, n-i-1, c + 1)) % (c + 1)] + 1)
    else:
        print(dp[(b - pow(2, n-i-1, c - 1)) % (c - 1)] + 1)
### BUGGY CODE ###

# import sys 
# input = sys.stdin.readline
 
 
n = int(input())
 
a= list(map(int,input().split())) 
 
def main(a):
    if 0 in a:
        print(0)
        quit()
     
    ans = 1
    for i in a:
        ans *= i 
        
        if ans > 10**18:
            ans = -1
    
    print(ans) 
    
main(a)


### FIXED CODE ###

# import sys 
# input = sys.stdin.readline
 
 
n = int(input())
 
a= list(map(int,input().split())) 
 
def main(a):
    if 0 in a:
        print(0)
        return
     
    ans = 1
    for i in a:
        ans *= i 
        
        if ans > 1000000000000000000:
            print(-1)
            return
    
    print(ans)
    
main(a)
### BUGGY CODE ###

N,M = map(int, input().split())
a = [int(input()) for _ in range(M)]
dp = [0 for _ in range(N+1)]
dp[0] = 1
for i in range(N+1):
    if i in a:
        continue
    else:
        if i+1 not in a and i+1 <= N:
            dp[i+1] += dp[i]
        if i+2 not in a and i+2 <= N:
            dp[i+2] += dp[i]
print(dp[-1]%1000000007)

### FIXED CODE ###

N,M = map(int, input().split())
a = [int(input()) for _ in range(M)]
dp = [0 for _ in range(N+1)]
dp[0] = 1
no_step = 0
for i in range(N+1):
    if no_step >= M:
        if i+1 <= N:
            dp[i+1] += dp[i]
        if i+2 <= N:
            dp[i+2] += dp[i]
    else:
        if i == a[no_step]:
            no_step += 1
            continue
        else:
            if i+1 != a[no_step] and i+1 <= N:
                dp[i+1] += dp[i]
            if i+2 != a[no_step] and i+2 <= N:
                dp[i+2] += dp[i]
print(dp[-1]%1000000007)
### BUGGY CODE ###

a,b=map(int,input().split())
x=0
while True:
  if x*(a-1)+1>=b: break
  else: x=+1
print(x)

### FIXED CODE ###

a,b=map(int,input().split())
x=0
while True:
  if x*(a-1)+1>=b: break
  else: x+=1
print(x)
### BUGGY CODE ###

def main():
    n, m = map(int, input().split())
    a=list(map(int, input().split()))
    s=[0]*(n+1)
    for i in range(1, n+1):
        s[i]=s[i-1]+a[i-1]
    dic={}
    for i in range(n+1):
        tmp=s[i]%m
        if tmp in dic.keys():
            dic[tmp]+=1
        else:
            dic[tmp]=1
    ans=0
    for i in dic.values():
        ans+=i*(i-1)//2
    print(ans)
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n, m = map(int, input().split())
    a=list(map(int, input().split()))
    s=[0]*(n+1)
    for i in range(1, n+1):
        s[i]=s[i-1]+a[i-1]
    dic={}
    for i in range(n+1):
        tmp=s[i]%m
        if tmp in dic.keys():
            dic[tmp]+=1
        else:
            dic[tmp]=1
    ans=0
    for i in dic.values():
        ans+=i*(i-1)//2
    print(ans)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

N = int(input())
A = tuple(map(int, input().split()))
B = tuple(map(int, input().split()))

def calc(fr, to):
    ret = N
    for g in range(N // fr[0] + 1):
        for s in range(N // fr[1] + 1):
            D = N - g * fr[0] - s * fr[1]

            if D < 0:
                break

            q, r = divmod(D, fr[2])

            D += g * to[0]
            D += s * to[1]

            r += g * to[0]
            r += s * to[1]
            r += q * to[2]

            ret = max(ret, D, r)
    return ret

N = calc(A, B)
print(calc(B, A))


### FIXED CODE ###

N = int(input())
A = tuple(map(int, input().split()))
B = tuple(map(int, input().split()))

def calc(A, B, N):
    M = N
    if len([i for i, (a, b) in enumerate(zip(A, B)) if a < b]) == 1:
        i = [i for i, (a, b) in enumerate(zip(A, B)) if a < b][0]

        for k in range(N // A[i] + 1):
            D = N - k * A[i]
            if D < 0:
                continue

            D += k * B[i]
            M = max(M, D)
    elif len([i for i, (a, b) in enumerate(zip(A, B)) if a < b]) == 2:
        i, j = [i for i, (a, b) in enumerate(zip(A, B)) if a < b]

        for k in range(N // A[i] + 1):
            D = N - k * A[i]
            l, D = divmod(D, A[j])

            D += k * B[i]
            D += l * B[j]

            M = max(M, D)
    elif len([i for i, (a, b) in enumerate(zip(A, B)) if a < b]) == 3:
        for g in range(N // A[0] + 1):
            for s in range(N // A[1] + 1):
                D = N - g * A[0] - s * A[1]

                if D < 0:
                    break

                q, r = divmod(D, A[2])

                D += g * B[0]
                D += s * B[1]

                r += g * B[0]
                r += s * B[1]
                r += q * B[2]

                M = max(M, D, r)
    return M

print(calc(B, A, calc(A, B, N)))
### BUGGY CODE ###

from collections import defaultdict
dd = defaultdict(lambda:[])
N, M = map(int, input().split())
temp = list(map(int, input().split()))
li_h = [0]
li_h.extend(temp)
for i in range(M):
    a, b= map(int, input().split())
    dd[a].append(b)
    dd[b].append(a)
#print(dd)
ans = 0
d = defaultdict(lambda:True)
for i in range(1, N+1):
    d[i] = True
li_dd = []
for i in dd:
    li_dd.append(i)
#print(li_dd)
for i in range(1, N+1):
    if i not in li_dd:
        ans += 1
    else:
        if not d:
            continue
        else:
            for k in dd[i]:
                if li_h[k] < li_h[i]:
                    d[k] = False
                elif li_h[k] == li_h[i]:
                    d[k] = False
                    d[i] = False
                    break
                else:
                    d[i] = False
                    break
            if d[i]:
                ans += 1
                #print(i)
            else:
                continue
print(ans)


### FIXED CODE ###

N, M = map(int, input().split())
dd = {}
for i in range(1, N+1):
    dd[i] = []
temp = list(map(int, input().split()))
li_h = [0]
li_h.extend(temp)
for i in range(M):
    a, b= map(int, input().split())
    dd[a].append(b)
    dd[b].append(a)
#print(dd)
ans = 0
d = {}
for i in range(1, N+1):
    d[i] = True
for i in range(1, N+1):
        if not d:
            continue
        else:
            for k in dd[i]:
                if li_h[k] < li_h[i]:
                    d[k] = False
                elif li_h[k] == li_h[i]:
                    d[k] = False
                    d[i] = False
                    break
                else:
                    d[i] = False
                    break
            if d[i]:
                ans += 1
                #print(i)
            else:
                continue
print(ans)
### BUGGY CODE ###

N=int(input())
X=input()

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

cnt=[0]*N

for i in range(1,N):
    p = popcount(i)
    cnt[i]=cnt[i%p]+1


P=X.count("1")
for i in range(N):
    if X[i]=="0":
        ret=int(X,2)+pow(2,N-i-1)
        p=P+1
    else:
        ret=int(X,2)-pow(2,N-i-1)
        p=P-1
    if ret==0:
        print(0)
    else:
        print(cnt[ret%p]+1)


### FIXED CODE ###

N=int(input())
X=input()

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

cnt=[0]*N
for i in range(1,N):
    p = popcount(i)
    cnt[i]=cnt[i%p]+1


P=X.count("1")

#MODSPP[i]=2**i%(P+1)
MODSPP=[0]*N
MODSPM=[0]*N

PP=P+1
if P-1<=0:
    PM=1
else:
    PM=P-1

MODSPP[0]=1%PP
MODSPM[0]=1%PM

for i in range(1,N):
    MODSPP[i]=(MODSPP[i-1]*2)%PP
    MODSPM[i]=(MODSPM[i-1]*2)%PM



MODSX_PP=0
MODSX_PM=0
for i in range(N):
    if X[i]=="1":
        MODSX_PP+=MODSPP[N-i-1]
        MODSX_PM+=MODSPM[N-i-1]
    MODSX_PP%=PP
    MODSX_PM%=PM


for i in range(N):
    if X[i]=="0":
        ret=MODSX_PP+MODSPP[N-i-1]
        ret%=PP
        print(cnt[ret]+1)
    else:
        if P-1<=0:
            print(0)
        else:
            ret=(MODSX_PM-MODSPM[N-i-1]+PM)%PM
            print(cnt[ret]+1)
### BUGGY CODE ###

N=int(input())
S=input()
a=[S[:i].count("#")+S[i+1:].count(".") for i in range(N)]
print(min(a))

### FIXED CODE ###

N=int(input())
S=input()
b=0
w=S.count(".")
ans=b+w
for s in S:
  if s=="#":
    b+=1
  else:
    w-=1
  ans=min(ans, b+w)
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0

for i in range(n-1):
  for j in range(i+1, n):
    ans += a[i] * a[j]

print(ans % (10**9 + 7))


### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
a = [0]
ans = 0

for i in range(n-1):
    a.append(a[i] + A[i])
for i in range(n):
    ans += A[i]*a[i]
print(ans % (10**9 + 7))
### BUGGY CODE ###

n = int(input())
li = [sorted(list(input())) for i in range(n)]

li2 = []
for i in range(len(li)):
    li2.append(li.count(li[i]))

li3 = list(set(li2))

from fractions import Fraction

def comb(n, k):
    
    if n < 0 or k < 0:
        pdt = 0
    
    else:
        pdt = 1
        for s in range(1, k + 1):
            pdt *= Fraction(n - s + 1, s)
    
    return pdt.numerator
num = 0   
for i in range(len(li3)):
    num += comb(li3[i],2)

print(num)

### FIXED CODE ###

n = int(input())
from collections import Counter
li = []
for i in range (n):
    li.append(sorted(input()))
li.sort()
for i in range(n):
    li[i]="".join(li[i])

d = Counter(li)
L = list(d.values())

cnt = 0
for i in range(len(L)):
    cnt += L[i]*(L[i]-1)//2
print(cnt)
### BUGGY CODE ###

from itertools import combinations

N,K=map(int,input().split())
H=[int(input()) for _ in range(N)]

ans=10**9
for i in combinations(H, K):
    ans=min(ans,max(i)-min(i))
print(ans)

### FIXED CODE ###

N,K=map(int,input().split())
H=[int(input()) for _ in range(N)]

H=sorted(H)
ans=10**9
for i in range(N-K+1):
    ans=min(ans,H[i+K-1]-H[i])
print(ans)
### BUGGY CODE ###

a = int(input())
 
ans = 0

  
print(sum(range(1,a)))

### FIXED CODE ###

n = int(input())

print(n*(n-1)//2)