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

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on 2019/2/
Solved on 2019/2/
@author: shinjisu
"""


# ARC 078 C  Splitting Pile
def getInt(): return int(input())


def getIntList(): return [int(x) for x in input().split()]


def zeros(n): return [0]*n


def getIntLines(n): return [int(input()) for i in range(n)]


def getIntMat(n):
    mat = []
    for i in range(n):
        mat.append(getIntList())
    return mat


def zeros2(n, m): return [zeros(m)]*n


ALPHABET = [chr(i+ord('a')) for i in range(26)]
DIGIT = [chr(i+ord('0')) for i in range(10)]
N1097 = 10**9 + 7


def dmp(x, cmt=''):
    global debug
    if debug:
        if cmt != '':
            print(cmt, ':  ', end='')
        print(x)
    return x


def probC():
    N = getInt()
    A = getIntList()
    dmp((N, A))
    diff = 10**(9+6)
    for i in range(1, N):
        diff = min(diff, abs(sum(A[:i])-sum(A[i:])))
    return diff


debug = False  # True False
ans = probC()
print(ans)
#for row in ans:
#    print(row)


### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on 2019/2/
Solved on 2019/2/
@author: shinjisu
"""


# ARC 078 C  Splitting Pile
def getInt(): return int(input())


def getIntList(): return [int(x) for x in input().split()]


def zeros(n): return [0]*n


def getIntLines(n): return [int(input()) for i in range(n)]


def getIntMat(n):
    mat = []
    for i in range(n):
        mat.append(getIntList())
    return mat


def zeros2(n, m): return [zeros(m)]*n


ALPHABET = [chr(i+ord('a')) for i in range(26)]
DIGIT = [chr(i+ord('0')) for i in range(10)]
N1097 = 10**9 + 7


def dmp(x, cmt=''):
    global debug
    if debug:
        if cmt != '':
            print(cmt, ':  ', end='')
        print(x)
    return x


def probC():
    N = getInt()
    A = getIntList()
    dmp((N, A))
    sumFormer = A[0]
    sumLatter = sum(A[1:])
    diff = abs(sumFormer-sumLatter)
    dmp(diff,'init')
    for i in range(1, N-1):
        sumFormer += A[i]
        sumLatter -= A[i]
        diff = min(diff, abs(sumFormer-sumLatter))
    return diff


def probC_v1():  # 5/16 AC 残りはTLE
    N = getInt()
    A = getIntList()
    dmp((N, A))
    diff = 10**(9+6)
    for i in range(1, N):
        diff = min(diff, abs(sum(A[:i])-sum(A[i:])))
    return diff


debug = False  # True False
ans = probC()
print(ans)
#for row in ans:
#    print(row)
### BUGGY CODE ###

K = int(input())
 
sevens = 7
count = 1
 
while(sevens % K !=0):
  sevens = sevens * 10 + 7
  count += 1
  if count > K:
    count = -1
    break
    
print(count)

### FIXED CODE ###

K = int(input())
 
sevens = 7 % K
count = 1
 
while(sevens % K !=0):
  sevens = sevens * (10 % K) + (7 % K)
  sevens = sevens % K
  count += 1
  if count > K:
    count = -1
    break
    
print(count)
### BUGGY CODE ###

import itertools

nklist = list(map(int,input().split()))
n, k= nklist[0], nklist[1]

lst = [tuple(map(int, input().split())) for i in range(n)]

max_pt = 0
for comb in itertools.combinations(lst, k):
    kinds_set = set()
    umami = 0
    for tpl in comb:
        kinds_set.add(tpl[0])
        umami += tpl[1]
    ttl_pt = len(kinds_set)**2 + umami
    if ttl_pt > max_pt:
        max_pt = ttl_pt
print(max_pt)

### FIXED CODE ###

n, k = map(int, input().split())
a = sorted([tuple(map(int, input().split())) for _ in range(n)], key=lambda x:-x[1])
 
ans = 0
s = set()
q = []
 
for i in range(k):
    ans += a[i][1]
    if a[i][0] in s:
        q.append(a[i][1])
    s.add(a[i][0])
 
ans += len(s)**2
k1 = k
ans1 = ans
 
#はじめ0~k-1までの和がansなので、k~n-1でチェック
while k1 < n and q:
    if a[k1][0] not in s:
        ans1 = ans1+a[k1][1]-q.pop()-len(s)**2+(len(s)+1)**2
        ans = max(ans, ans1)
        s.add(a[k1][0])
    k1 += 1
 
print(ans)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 6)

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

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

l=[0]*n
l[0]=1

def dfs(now,last=-1):
    for to in edge[now]:
        if to==last:continue
        ans[to]+=ans[now]
        dfs(to,now)
dfs(0)


for i in ans:
    print(i)

### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, Q = map(int, input().split())
    edges = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(lambda x: int(x) - 1, input().split())
        edges[a].append(b)
        edges[b].append(a)

    counter = [0] * N
    for _ in range(Q):
        p, x = map(int, input().split())
        p -= 1
        counter[p] += x

    def dfs(cur, par):
        for nex in edges[cur]:
            if nex == par:
                continue
            counter[nex] += counter[cur]
            dfs(nex, cur)

    dfs(0, -1)
    print(*counter, sep=" ")


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

N, K, *A = map(int, open(0).read().split())

x = A[:]

for _ in range(K):
    y = [0] * (N + 1)
    for i in range(N):
        y[max(0, i - x[i])] += 1
        y[min(N, i + x[i] + 1)] -= 1
        
    for i in range(N):
        y[i + 1] += y[i]
        
    x = y[:]
        
    
print(*x[:-1])


### FIXED CODE ###

N, K, *A = map(int, open(0).read().split())

x = A[:]

for _ in range(min(50, K)):
    y = [0] * (N + 1)
    for i in range(N):
        y[max(0, i - x[i])] += 1
        y[min(N, i + x[i] + 1)] -= 1
        
    for i in range(N):
        y[i + 1] += y[i]
        
    x = y[:]
        
    
print(*x[:-1])
### BUGGY CODE ###

S=input()
Q=int(input())
query=[list(map(str,input().split())) for _ in range(Q)]

ans=[]
for s in S:
  ans.append(s)
for q in query:
  if len(q)==1:
    ans=ans[::-1]
  else:
    _,f,c=q
    if f=='1':
      ans.insert(0,c)
    else:
      ans.append(c)
print(*ans,sep='')

### FIXED CODE ###

from collections import deque
S=input()
Q=int(input())
query=[list(map(str,input().split())) for _ in range(Q)]

ans=deque(S)
reverse=False
for i,q in enumerate(query):
  if len(q)==1:
    reverse=not reverse
  else:
    _,f,c=q
    if (f=='2') ^ reverse:
      ans.append(c)
    else:
      ans.appendleft(c)
if reverse:
  print(*reversed(ans),sep='')
else:
  print(*ans,sep='')
### BUGGY CODE ###

sx,sy,gx,gy=map(int,input().split())
n=int(input())
g = [[] for i in range(n+2)]
data=[(sx,sy,0)]
for i in range(n):
    data.append(tuple(map(int,input().split())))
data.append((gx,gy,0))
for i in range(n+2):
    for j in range(i,n+2):
        if i==j:
            g[i].append((0,j))
            g[j].append((0,i))
            continue
        tmp=max(0,((data[i][0]-data[j][0])**2+(data[i][1]-data[j][1])**2)**0.5-data[i][2]-data[j][2])
        g[i].append((tmp,j))
        g[j].append((tmp,i))

def dijkstra(g,st,ed):
    from heapq import heappush, heappop, heapify
    inf=10**10+1
    dist=[inf for i in range(len(g))]
    dist[st]=0
    que=[]
    heappush(que,(0,st))
    while que:
        c,v=heappop(que)
        if dist[v]<c:
            continue
        for i in range(len(g[v])):
            if g[v][i][0]+c<dist[g[v][i][1]]:
                dist[g[v][i][1]]=g[v][i][0]+c
                heappush(que,(g[v][i][0]+c,g[v][i][1]))
    return dist[ed]

print(dijkstra(g,0,n+1))

### FIXED CODE ###

from heapq import heappush, heappop
sx,sy,gx,gy=map(int,input().split())
n=int(input())
g = [[] for i in range(n+2)]
data=[(sx+sy*1j,0)]
for i in range(n):
    a,b,c=map(int,input().split())
    data.append((a+b*1j,c))
data.append((gx+gy*1j,0))

for i in range(n+2):
    for j in range(i+1,n+2):
        tmp=abs(data[i][0]-data[j][0])-data[i][1]-data[j][1]
        g[i].append((tmp,j))
        g[j].append((tmp,i))

dist=[2828427127 for i in range(n+2)]
visited=[False for i in range(n+2)]
dist[0]=0
que=[]
heappush(que,(0,0))

while que:
    c,v=heappop(que)
    if visited[v]:
        continue
    visited[v]=True
    for x in g[v]:
        if visited[x[1]]:
            continue
        tmp=x[0]+c if not x[0]<0 else c
        if tmp<dist[x[1]]:
            dist[x[1]]=tmp
            heappush(que,(tmp,x[1]))
print(dist[n+1])
### BUGGY CODE ###

ABM = list(map(int, input().split()))
price_A = list(map(int, input().split()))
price_B = list(map(int, input().split()))

waribiki = []
for i in range(ABM[2]):
    waribiki.append(list(map(int, input().split())))

result = []
for i in waribiki:
    for i_A in price_A:
        for i_B in price_B:
            result.append(i_A + i_B)
    result.append(price_A[i[0] - 1] + price_B[i[1] - 1] - i[2])

print(min(result))


### FIXED CODE ###

ABM = list(map(int, input().split()))
price_A = list(map(int, input().split()))
price_B = list(map(int, input().split()))

waribiki = []
for i in range(ABM[2]):
    waribiki.append(list(map(int, input().split())))

result = []
for i in waribiki:
    result.append(price_A[i[0] - 1] + price_B[i[1] - 1] - i[2])

result.append(min(price_A) + min(price_B))

print(min(result))
### BUGGY CODE ###

s=input()
k=int(input())
n=len(s)
l=[]
for i in range(n):
    curr=''
    for j in range(i,min(i+10,n)):
        curr+=s[j]
        if curr not in l:
            l.append(curr)
l.sort()
#print(l)
print(l[k-1])

### FIXED CODE ###

s=input()
k=int(input())
n=len(s)
l=set()
for i in range(n):
    curr=''
    for j in range(i,min(i+7,n)):
        curr+=s[j]
        l.add(curr)
l=[i for i in l]
l.sort()
#print(l)
print(l[k-1])
### BUGGY CODE ###

import sys
n=int(raw_input())
ans=[]
while n:
    n-=1
    s=sys.stdin.readline().rstrip().split(' ')
    if s[0][0]=='i':
        ans.insert(0,s[1])
    elif s[0][-3]=='r':
#        ans.pop(0)
        del ans[0]
    elif s[0][-3]=='a':
        del ans[-1]
#        ans.pop()
    else:
        for i,j in enumerate(ans):
            if j==s[1]:
                del ans[i]
#                ans.pop(i)
                break
sys.stdout.write(' '.join(ans))
print

### FIXED CODE ###

import sys
import collections
n=int(raw_input())
ans=collections.deque()
while n:
    n-=1
    s=sys.stdin.readline().rstrip().split(' ')
    if s[0][0]=='i':
        ans.appendleft(s[1])
    elif s[0][-3]=='r':
        ans.popleft()
    elif s[0][-3]=='a':
        ans.pop()
    else:
        try:
            ans.remove(s[1])
        except:
            pass
sys.stdout.write(' '.join(ans))
print
### BUGGY CODE ###

X, Y = map(int, input().split())

max_num = 10 ** 18
ans = -1

for i in range(X, max_num+1, X):
  if i % Y != 0:
    ans = i
    break
  
print(ans)

### FIXED CODE ###

X, Y = map(int, input().split())

if X % Y == 0:
  print(-1)
else:
  print(X)
### BUGGY CODE ###

N, Q = map(int, input().split())

trees = {}
for _ in range(N - 1):
    id1, id2 = map(int, input().split())
    if id1 not in trees:
        trees[id1] = []
    trees[id1].append(id2)

values = {}
for _ in range(Q):
    nid, val = map(int, input().split())
    if nid not in values:
        values[nid] = 0
    values[nid] += val

counters = {}
for nid, val in values.items():
    stack = [nid]
    while len(stack) > 0:
        myid = stack.pop()
        if myid not in counters:
            counters[myid] = 0
        counters[myid] += val
        if myid in trees:
            stack.extend(trees[myid])

ret = []
for myid in range(1, N + 1):
    if myid not in counters:
        ret.append(str(0))
    else:
        ret.append(str(counters[myid]))
        
print(' '.join(ret))

### FIXED CODE ###

N, Q = map(int, input().split())

trees = {}
for _ in range(N - 1):
    id1, id2 = map(int, input().split())
    if id1 not in trees:
        trees[id1] = []
    trees[id1].append(id2)

from collections import defaultdict
values = defaultdict(int)
for _ in range(Q):
    nid, val = map(int, input().split())
    values[nid] += val

counters = defaultdict(int)
stack = [[1, 0]] # id, value from parent
while len(stack) > 0:
    myid, parent_val = stack.pop()
    current_val = parent_val + values[myid]
    counters[myid] = current_val
    if myid in trees:
        for cid in trees[myid]:
            stack.append([cid, current_val])

print(' '.join(map(str, [counters[myid] for myid in range(1, N + 1)])))
### BUGGY CODE ###

import functools
import operator
prod = functools.partial(functools.reduce, operator.mul)

listS = []

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

for i in range(0,N-K+1):
    listS.append(prod(A[i:K+i]))
    
for j in range(len(listS)-1):
    if listS[j] < listS[j+1]:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

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

for i in range(0,N-K):
    if A[i] < A[i+K]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import math

A,B = map(int,input().split())
ans = 1
mid = int(max(A,B)/2)
for i in range(2,mid+2):
    if A % i== 0 and B % i == 0:
        if i % 2 == 0 and i != 2:
            continue
        for j in range(3,int(math.sqrt(i)+1),2):
            if i % j == 0 and i != j:
                break
        else:
            ans += 1
print(ans)

### FIXED CODE ###

import math

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

A,B = map(int,input().split())
a = prime_factorize(A)
b = prime_factorize(B)
ans = 1

while a != []:
    x = a[0]
    if x in b:
        ans+=1
    a = [i for i in a if i != x]

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

import math

x,y = map(int, input().split())
# (i,j)->(i+1,j+2) continues a times.
# (i,j)->(i+2,j+1) continues b times.
temp = 2*x-y

a = -1
b = -1
if temp%3==0 and temp>=0:
  b = temp//3
  if x-2*b>=0:
    a = x-2*b

if a==-1 or b==-1:
  print(0)
else:
  ans = math.factorial(a+b)/(math.factorial(a)*math.factorial(b))
  print(int(ans%(10**9+7)))

### FIXED CODE ###

import math

x,y = map(int, input().split())
# (i,j)->(i+1,j+2) continues a times.
# (i,j)->(i+2,j+1) continues b times.
temp = 2*x-y

a = -1
b = -1
if temp%3==0 and temp>=0:
  b = temp//3
  if x-2*b>=0:
    a = x-2*b

if a==-1 or b==-1:
  print(0)
else:
  #このままではansは非常に大きい数になりメモリ使用量が大きくなる。
  #よって、メモリ使用量削減のために"逆元とフェルマーの小定理"を活用する。
  A = 1
  B = 1
  mod = 10**9+7
  for i in range(min(a,b)):
    A *= a+b-i
    A %= mod
    B *= i+1
    B %= mod
  print(A*pow(B,mod-2,mod)%mod)
### BUGGY CODE ###

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())

N,K = inpl()
xys = []
xx = set()
yy = set()
for i in range(N):
    x,y = inpl()
    xys.append([x,y])
    xx.add(x)
    yy.add(y)

ans = INF
xx = sorted(list(xx))
yy = sorted(list(yy))
Lx = len(xx)
Ly = len(yy)
for i1 in range(Lx):
    x1 = xx[i1]
    for i2 in range(i1,Lx):
        x2 = xx[i2]
        for j1 in range(Ly):
            y1 = yy[j1]
            for j2 in range(j1,Ly):
                y2 = yy[j2]
                tmp = 0
                for x,y in xys:
                    if x1 <= x <= x2 and y1 <= y <= y2:
                        tmp += 1
                if K <= tmp:
                    ans = min(ans,(x2-x1)*(y2-y1))

print(ans)


### FIXED CODE ###

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())

N,K = inpl()
xys = []
xx = set()
for i in range(N):
    x,y = inpl()
    xys.append([x,y])
    xx.add(x)

ans = INF
xx = sorted(list(xx))
Lx = len(xx)
xys.sort(key = lambda x: x[1])
for i1 in range(Lx):
    x1 = xx[i1]
    for i2 in range(i1,Lx):
        x2 = xx[i2]
        yy = []
        for x,y in xys:
            if x1 <= x <= x2:
                yy.append(y)
        Ly = len(yy)
        if Ly < K:
            continue
        else:
            for l in range(Ly-K+1):
                r = l+K-1
                ans = min((yy[r]-yy[l])*(x2-x1),ans)

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

# -*- coding: utf-8 -*-
# モジュールのインポート
import itertools

# 標準入力を取得
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

# 求解処理


def get_ub(l: list, x: int) -> int:
    l = sorted(l)
    low = -1
    high = len(l)
    while 1 < high - low:
        mid = (high + low) // 2
        guess = l[mid]
        if guess > x:
            high = mid
        else:
            low = mid
    return high


ans = 0
for A_i, B_i in itertools.product(A, B):
    if A_i >= B_i:
        continue
    ans += N - get_ub(C, B_i)

# 結果出力
print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-

def get_input() -> tuple:
    """
    標準入力を取得する.

    Returns:\n
        tuple: 標準入力
    """
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))

    return N, A, B, C


def get_lb(l: list, key: int) -> int:
    """
    l[index] > keyとなる最小のindexを求める.

    Args:\n
        l (list): リスト
        key (int): 整数

    Returns:\n
        int: l[index] > keyとなる最小のindex
    """
    low = -1
    high = len(l)
    while 1 < high - low:
        mid = (low + high) // 2
        guess = l[mid]
        if guess > key:
            high = mid
        else:
            low = mid
    return high


def get_ub(l: list, key: int) -> int:
    """
    l[index] < keyとなる最大のindexを求める.

    Args:\n
        l (list): リスト
        key (int): 整数

    Returns:\n
        int: l[index] < keyとなる最大のindex
    """
    low = -1
    high = len(l)
    while 1 < high - low:
        mid = (low + high) // 2
        guess = l[mid]
        if guess < key:
            low = mid
        else:
            high = mid
    return low


def main(N: int, A: list, B: list, C: list) -> None:
    """
    メイン処理.

    Args:\n
        N (int): パーツの数
        A (list): 上部のパーツのサイズ
        B (list): 中部のパーツのサイズ
        C (list): 下部のパーツのサイズ
    """
    # 事前にリストをソートしておく
    A = sorted(A)
    B = sorted(B)
    C = sorted(C)

    # 求解処理
    ans = 0
    for i in range(N):
        B_i = B[i]
        ans += (get_ub(A, B_i) + 1) * (N - get_lb(C, B_i))

    # 結果出力
    print(ans)


if __name__ == "__main__":
    # 標準入力を取得
    N, A, B, C = get_input()

    # メイン処理
    main(N, A, B, C)
### BUGGY CODE ###

import bisect

n = int(input())
xx = list(map(int, input().split()))
pp = [(xx[i], i + 1) for i in range(n)]
pp.sort(reverse = True)

larger = [0, 0, pp[0][1], n + 1, n + 1]
ans = 0

for i in range(1, n):
	idx = bisect.bisect_left(larger, pp[i][1])

	ans += (larger[idx - 1] - larger[idx - 2]) * (larger[idx] - pp[i][1]) * pp[i][0]
	ans += (pp[i][1] - larger[idx - 1]	) * (larger[idx + 1] - larger[idx]) * pp[i][0]
	larger.insert(idx, pp[i][1])

print(ans)

### FIXED CODE ###


def main():
	n = int(input())
	xx = list(map(int, input().split()))

	pp = [(xx[i], i + 1) for i in range(n)]
	pp.sort(key=lambda x: x[0])
	# print(xx)
	# print(pp)

	left = [0, 0] + [i + 1 for i in range(n)]
	right = [i + 1 for i in range(n)] + [n + 1, n + 1]
	ans = 0
	for i in range(n):

		ori_num, ori_ind = pp[i]
		l1 = left[ori_ind]
		l2 = left[l1]
		r1 = right[ori_ind]
		r2 = right[r1]

		# print("ori_num, ori_ind, l1, l2, r1, r2")
		# print(ori_num, ori_ind, l1, l2, r1, r2)
		# print(left)
		# print(right)

		ans += ((l1 - l2) * (r1 - ori_ind) + (ori_ind - l1) * (r2 - r1)) * ori_num

		right[l1] = r1
		left[r1] = l1

	print(ans)

main()
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
B = list()
ans = 0
for i in range(n - 1):
    for j in range(n - i - 1):
        b = A[i] ^ A[j + i + 1]
        B.append(b)
        len_B = len(B)
        if ans + B[len_B - 1] < 1000000007:
            ans += b
        else:
            ans = (ans + b) % 1000000007
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
p = [pow(2, i, mod) for i in range(60)]
ans = 0
for i in range(60):
    c = 0
    for j in a:
        if (j >> i) & 1:
            c += 1
    ans += (c * (n - c) * p[i]) % mod
    ans %= mod
print(ans)
### BUGGY CODE ###

import sys,math,collections,itertools
input = sys.stdin.readline

H,W=list(map(int,input().split()))
s = [ input().rstrip() for _ in range(H)]

def isOK(start,goal):
    q =  collections.deque([start])
    dp = [[0]*W for _ in range(H)]
    while q:
        nowh,noww = q.popleft()
        dp[nowh][noww] = 1
        if s[nowh][noww] == '.':
            target_mark = '#'
        else:
            target_mark = '.'
            
        if nowh >0 and s[nowh-1][noww] == target_mark and dp[nowh-1][noww]==0:
            q.append((nowh-1,noww))
            if (nowh-1,noww)==goal:
                return True

        if nowh <H-1 and s[nowh+1][noww] == target_mark and dp[nowh+1][noww]==0:
            q.append((nowh+1,noww))
            if (nowh+1,noww)==goal:
                return True
            
        if noww > 0 and s[nowh][noww-1] == target_mark and dp[nowh][noww-1]==0:
            q.append((nowh,noww-1))
            if (nowh,noww-1)==goal:
                return True

        if noww < W-1 and s[nowh][noww+1] == target_mark and dp[nowh][noww+1]==0:
            q.append((nowh,noww+1))
            if (nowh,noww+1)==goal:
                return True
    return False

cnt = 0

start_candi = []
end_candi = []
for ih in range(H):
    for iw in range(W):
        if s[ih][iw] == '#':
            start_candi.append((ih,iw))
        else:
            end_candi.append((ih,iw))

for start in start_candi:
    for end in end_candi:
        flag = abs(start[0]-end[0])+abs(start[1]-end[1])
        if flag%2==1:
            cnt += isOK(start,end)
        else:
            continue

print(cnt)







        


### FIXED CODE ###

import sys,math,collections,itertools
input = sys.stdin.readline

H,W=list(map(int,input().split()))
s = [ input().rstrip() for _ in range(H)]
dp = [[0]*W for _ in range(H)]

def isOK(start):
    q =  collections.deque([start])
    dp[start[0]][start[1]] = 1
    black,white=0,0
    while q:
        nowh,noww = q.popleft()
        if s[nowh][noww] == '.':
            target_mark = '#'
            white +=1
        else:
            target_mark = '.'
            black +=1
        if nowh >0 and s[nowh-1][noww] == target_mark and dp[nowh-1][noww]==0:
            q.append((nowh-1,noww))
            dp[nowh-1][noww]=1
        if nowh <H-1 and s[nowh+1][noww] == target_mark and dp[nowh+1][noww]==0:
            q.append((nowh+1,noww))
            dp[nowh+1][noww]=1
        if noww > 0 and s[nowh][noww-1] == target_mark and dp[nowh][noww-1]==0:
            q.append((nowh,noww-1))
            dp[nowh][noww-1]=1
        if noww < W-1 and s[nowh][noww+1] == target_mark and dp[nowh][noww+1]==0:
            q.append((nowh,noww+1))
            dp[nowh][noww+1]=1
            
    return black*white

cnt = 0

start_candi = []
end_candi = []
for ih in range(H):
    for iw in range(W):
        if s[ih][iw] == '#':
            start_candi.append((ih,iw))
        else:
            end_candi.append((ih,iw))

for ih in range(H):
    for iw in range(W):
        if dp[ih][iw] == 0:
            start = (ih,iw)
            cnt += isOK(start)
        else:
            continue

print(cnt)
### BUGGY CODE ###

N, M = map(int, input().split())
A = []
for i in range(M):
	curr = int(input())
	A.append(curr)

mod = 1000000007

ans = [0] * (N + 1)

ans[0] = 1

for i in range(len(ans)):
	if i in A:
		continue
	if(i+1 < len(ans)):
		ans[i+1] += ans[i]
		ans[i+1] %= mod
	if(i+2 < len(ans)):
		ans[i+2] += ans[i]
		ans[i+2] %=mod

print(ans[N])

### FIXED CODE ###

N, M = map(int, input().split())
A = []
for i in range(M):
	curr = int(input())
	A.append(curr)

mod = 1000000007

ans = [0] * (N + 1)

ans[0] = 1

for a in A:
	ans[a] = -1

for i in range(len(ans)):
	if ans[i] == -1:
		continue
	if(i+1 < len(ans) and ans[i+1] != -1):
		ans[i+1] += ans[i]
		ans[i+1] %= mod
	if(i+2 < len(ans) and ans[i+2] != -1):
		ans[i+2] += ans[i]
		ans[i+2] %=mod

print(ans[N])