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

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

r = s.count('R')
g = s.count('G')
b = s.count('B')

# 1つ目の条件を満たす
first_conditions = r*g*b
# 一つ目の条件は満たすが、2つ目の条件は満たさない
second_condition = 0
sum_ = 0
for i in range(n):
    for j in range(i,n):
        for k in range(j,n):
            if j-i == k-j and s[i] != s[j] and s[j] != s[k] and s[i] != s[k]:
                second_condition += 1
print(first_conditions-second_condition)

### FIXED CODE ###

n = int(input())
s = input()
r_ary = []
g_ary = []
b_ary = []
for i in (s):
    if i == 'R':
        r_ary.append(i)
    elif i == 'G':
        g_ary.append(i)
    elif i == 'B':
        b_ary.append(i)
r = len(r_ary)
g = len(g_ary)
b = len(b_ary)
first_conditions = r*g*b
for i in range(n-2):
    for j in range(i+1,n-1):
        if 2*j-i<n and s[i]!=s[2*j-i] and s[j]!=s[2*j-i] and s[i]!=s[j]:
            first_conditions -= 1
print(first_conditions)
### BUGGY CODE ###

from collections import deque
N = int(input())
a = [[0] * (N) for i in range(N)]
for n in range(N-1):
    u,v,w = map(int, input().split())
    a[u-1][v-1] += w
    a[v-1][u-1] += w

dist = [0]*N
st = deque()
push, pop = st.appendleft, st.pop
push(0)
while st:
    i = pop()
    for j in range(N):
        if a[i][j] > 0:
            dist[j] = dist[i] + a[i][j]
            a[i][j], a[j][i] = 0,0
            push(j)


for d in dist:
    if d%2 == 0:
        print(0)
    else:
        print(1)

### FIXED CODE ###

from collections import deque
N = int(input())
G = [[] for i in range(N)]
for i in range(N-1):
    u,v,w = map(int, input().split())
    G[u-1].append((v-1, w))
    G[v-1].append((u-1, w))

st = deque()
push, pop = st.appendleft, st.pop
push(0)
dist = [0]*N
cnt = [0]*N
cnt[0] = 1

while st:
    u = pop()
    for v,w in G[u]:
        if cnt[v] == 1:
            continue
        dist[v] = dist[u] + w
        push(v)
        cnt[v] = 1

for d in dist:
    if d%2 == 0:
        print(0)
    else:
        print(1)
### BUGGY CODE ###

from collections import deque

h, w = (int(x) for x in input().split())
ch, cw = (int(x) - 1 for x in input().split())
dh, dw = (int(x) - 1 for x in input().split())
S = [list(input()) for _ in range(h)]
grid = [[-1] * w for _ in range(h)]
grid[ch][cw] = 0
N = [[0, 1], [0, -1], [1, 0], [-1, 0]]
P = [[2, 2], [2, 1], [2, 0], [2, -1], [2, -2], [1, 2], [1, 1], [1, -1], [1, -2], [0, 2], [0, -2], [-1, 2], [-1, 1],
     [-1, -1], [-1, -2], [-2, 2], [-2, 1], [-2, 0], [-2, -1], [-2, -2]]

que = deque([(0, ch, cw)])
while que:
    count, y, x = que.popleft()
    if grid[y][x] < count:
        continue
    for NX, NY in N:
        nx = x + NX
        ny = y + NY
        if 0 <= nx < w and 0 <= ny < h and S[ny][nx] != "#":
            if grid[ny][nx] == -1 or grid[ny][nx] > count:
                grid[ny][nx] = count
                que.appendleft((count, ny, nx))
    for PX, PY in P:
        px = x + PX
        py = y + PY
        if 0 <= px < w and 0 <= py < h and S[py][px] != "#":
            if grid[py][px] == -1 or grid[py][px] > count + 1:
                grid[py][px] = count + 1
            que.append((count + 1, py, px))

print(grid[dh][dw])


### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
s = [list(input()) for _ in range(h)]

Ch, Cw = Ch - 1, Cw - 1
Dh, Dw = Dh - 1, Dw - 1
d = [[-1] * w for _ in range(h)]
d[Ch][Cw] = 0
walk = [[0, 1], [0, -1], [1, 0], [-1, 0]]
warp = [[2, 2], [2, 1], [2, 0], [2, -1], [2, -2], [1, 2], [1, 1], [1, -1], [1, -2], [0, 2], [0, -2], [-1, 2], [-1, 1],
        [-1, -1], [-1, -2], [-2, 2], [-2, 1], [-2, 0], [-2, -1], [-2, -2]]

que = deque([[0, Ch, Cw]])
while que:
    count, y, x = que.popleft()
    if d[y][x] < count:
        continue
    for NY, NX in walk:
        if 0 <= y + NY < h and 0 <= x + NX < w and s[y + NY][x + NX] != '#':
            if d[y + NY][x + NX] == -1 or d[y + NY][x + NX] > count:
                d[y + NY][x + NX] = count
                que.appendleft([count, y + NY, x + NX])
    for NY, NX in warp:
        if 0 <= y + NY < h and 0 <= x + NX < w and s[y + NY][x + NX] != '#':
            if d[y + NY][x + NX] == -1 or d[y + NY][x + NX] > count + 1:
                d[y + NY][x + NX] = count + 1
                que.append([count + 1, y + NY, x + NX])

print(d[Dh][Dw])
### BUGGY CODE ###

m = 1000000
NIL = 1e9

def h1(key):
    return key % m

def h2(key):
    return 1 + (key % (m - 1))

def h(key, i):
    return (h1(key) + i * h2(key)) % m

def insert(t, key):
    i = 0
    while True:
        j = h(key, i)
        if t[j] == NIL:
            t[j] = key
            return j
        else:
            i += 1

def find(t, key):
    i = 0
    while True:
        j = h(key, i)
        if t[j] == key:
            return j
        elif t[j] == NIL or i >= m:
            return NIL
        else:
            i += 1

def convert(word):
    result = ""
    for i in word:
        if i == "A":
            result += "1"
        elif i == "T":
            result += "2"
        elif i == "G":
            result += "3"
        else:
            result += "4"
    return int(result)


t = [NIL]*m
n = int(input())
for i in range(n):
    com = input().split()
    key = convert(com[1])
    if com[0] == "insert":
        insert(t, key)
    else:
        if find(t, key) != NIL:
            print("yes")
        else:
            print("no")


### FIXED CODE ###

n = int(input())
d = set()

for i in range(n):
    com = input().split()
    if com[0] == "insert":
        d.add(com[1])
    else:
        print("yes" if com[1] in d else "no")
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int


def solve(S: str):
    """
    >>> solve("05")
    1
    >>> solve("18")
    1
    >>> solve("13")
    0
    """
    pre, cur = None, None
    base = 10
    if S[-1] == "?":
        cur = [1] * 10 + [0] * 3
    else:
        cur = [0] * 13
        cur[int(S[-1])] = 1
    for n in reversed(S[:-1]):
        pre, cur = cur, [0] * 13
        g = range(10) if n == "?" else [int(n)]
        for i in g:
            t = base * i % 13
            for j in range(13):
                cur[(j+t)%13] = (cur[(j+t)%13] + pre[j]) % MOD
        base = (base * 10) % 13        
        # print(n, pre, cur, base)
    return cur[5]

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    print(solve(S))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    test()
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
 
MOD = 1000000007  # type: int
 
 
def solve(S: str):
    """
    >>> solve("05")
    1
    >>> solve("18")
    1
    >>> solve("13")
    0
    """
    pre, cur = [0] * 13, None
    base = 10
    if S[-1] == "?":
        cur = [1] * 10 + [0] * 3
    else:
        cur = [0] * 13
        cur[int(S[-1])] = 1
    for n in reversed(S[:-1]):
        pre, cur = cur, pre
        for i in range(13): # 再生成を避ける
            cur[i] = 0
        g = range(10) if n == "?" else [int(n)]
        for i in g:
            t = base * i % 13
            for j in range(13):
                cur[(j+t)%13] = (cur[(j+t)%13] + pre[j]) % MOD
        base = (base * 10) % 13        
        # print(n, pre, cur, base)
    return cur[5]
 
# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    print(solve(S))
 
def test():
    import doctest
    doctest.testmod()
 
if __name__ == '__main__':
    #test()
    main()
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
l = [1]
lnew = [1]
for i in range(n):
  lnew.append(a[l[i]-1])
  if lnew[-1] in l == True:
    break
  else:
    l.append(lnew[-1])

del l[-1]
lindex = l.index(l[-1])
del l[-1]
r = len(l) - lindex
rlist = l[lindex:]

if k >= lindex:
  kmod = (k - lindex) % r
  ans = rlist[kmod]
else:
  ans = l[k]
  
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
l = [1]
b = [1] + [0] * (n-1)
for i in range(n):
  b[a[l[i]-1]-1] += 1
  if b[a[l[i]-1]-1] == 2:
    break
  else:
    l.append(a[l[i]-1])

lindex = l.index(a[l[i]-1])
r = len(l) - lindex
rlist = l[lindex:]

if k >= lindex:
  kmod = (k - lindex) % r
  ans = rlist[kmod]
else:
  ans = l[k]
  
print(ans)
### BUGGY CODE ###

n = int(input())
s = str(input())
count = 0

for k in range(n):
    for j in range(n):
        for i in range(n):
            if i < j < k:
                a = (s[i], s[j], s[k])
                #print(a)
                a_set = set(a)
                #print(a_set)
                if len(a_set) == 3 and (j - i) != (k - j):
                    count += 1

print(count)

### FIXED CODE ###

n = int(input())
s = str(input())
count = 0
sum_RGB = s.count("R") * s.count("G") * s.count("B")
for i in range(n):
    for j in range(i, n):  # rangeをiからにすることでループ減らせる
        # for k in range(n): # sum_RGBから減らしていくのでｋがi,jで決まる
        k = 2*j - i
        if k < n:
            a = (s[i], s[j], s[k])
            # print(a)
            a_set = set(a)
            # print(a_set)
            if len(a_set) == 3:
                count += 1

print(sum_RGB - count)
### BUGGY CODE ###

n = int(input())
li = [list(map(int,input().split())) for i in range(n-1)] #csf

for i in range(n-1):
    t = li[i][1] + li[i][0]
    for j in range(i+1,n-1):
        while True:
            if t >= li[j][1] and t%li[j][2] == 0:
                break
            else:
                t += 1
        t += li[j][0]
    print(t)
print(0)

### FIXED CODE ###

n = int(input())
li = [list(map(int,input().split())) for i in range(n-1)] #csf

for i in range(n-1):
    t = li[i][1] + li[i][0]
    for j in range(i+1,n-1):
        while True:
            if t >= li[j][1] and t%li[j][2] == 0:
                break
            else:
                t += 1
        t += li[j][0]
    print(t)
print(0)
### BUGGY CODE ###

s = input()
n = int(input())
query = []
for i in range(n):
    query.append(input().split())
cond = 1

for i in range(n):
    if query[i] == ['1']:
        cond *= -1
    else:
        if cond == 1:
            if query[i][1] == '1':
                s = query[i][2] + s
            else:
                s = s + query[i][2]
        else:
            if query[i][1] == '2':
                s = query[i][2] + s
            else:
                s = s + query[i][2]
if cond == -1:
    s = s[::-1]
print(s)


### FIXED CODE ###

from collections import deque
s = input()
n = int(input())
query = []
for i in range(n):
    query.append(input().split())
cond = 1
word = deque(s)
for i in range(n):
    if query[i] == ['1']:
        cond *= -1
    else:
        if cond == 1:
            if query[i][1] == '1':
                word.appendleft(query[i][2])
            else:
                word.append(query[i][2])
        else:
            if query[i][1] == '2':
                word.appendleft(query[i][2])
            else:
                word.append(query[i][2])

result = ''.join(word)
if cond == -1:
    result = result[::-1]
print(result)
### BUGGY CODE ###

# coding: utf-8
import array, bisect, collections, heapq, itertools, math, random, re, string, sys, time
sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7
 
 
def II(): return int(input())
def ILI(): return list(map(int, input().split()))
def IAI(LINE): return [ILI() for __ in range(LINE)]
def IDI(): return {key: value for key, value in ILI()}
 
 
def solve(N, W, w, v):
    dp = [[-1] * (N + 1) for __ in range(W + 1)]
    def throw(weight=W, num=0):
        if dp[weight][num] != -1:
            return dp[weight][num]
        
        if num == N:
            return 0
        elif weight < w[num]:
            res = throw(weight, num + 1)
        else:
            res = max(throw(weight, num + 1), throw(weight - w[num], num + 1) + v[num])
        
        dp[weight][num] = res
        return res
    
    ans = throw()
    return ans
    
 
def main():
    N, W = ILI()
    w, v = [], []
    for __ in range(N):
        x, y = ILI()
        w.append(x)
        v.append(y)
    print(solve(N, W, w, v))
 
 
if __name__ == "__main__":
    main()


### FIXED CODE ###

# coding: utf-8
import array, bisect, collections, heapq, itertools, math, random, re, string, sys, time

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7


def II(): return int(input())
def ILI(): return list(map(int, input().split()))
def IAI(LINE): return [ILI() for __ in range(LINE)]
def IDI(): return {key: value for key, value in ILI()}


def solve(N, W, w_v):
    memo = collections.defaultdict(int)
    memo[0] = 0
    for w, v in w_v:
        for w_memo, v_memo in sorted(list(memo.items()), key=lambda x: -x[0]):
            if w + w_memo > W:
                continue
            if memo[w + w_memo] < v_memo + v:
                memo[w + w_memo] = v_memo + v

    return max(memo.values())


def main():
    N, W = ILI()
    w_v = IAI(N)
    print(solve(N, W, w_v))


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

N, X, M = map(int,input().split())
visited = [(-1,-1)]*M
ans = 0
for i in range(N):
    if visited[X][0] > 0:
        d = ans - visited[X][0]
        left = N-i
        length = i-visited[X][1]
        ans += (left//length)*d
        left %= length
        for j in range(left):
            ans += X
            X = X*X % M
        break
    visited[X] = (ans, i)
    ans += X
    X = X*X % M
print(ans)

### FIXED CODE ###

N, X, M = map(int,input().split())
visited = [(-1,-1)]*M
ans = 0
for i in range(N):
    if visited[X][0] >= 0:
        d = ans - visited[X][0]
        left = N-i
        length = i-visited[X][1]
        ans += (left//length)*d
        left %= length
        for j in range(left):
            ans += X
            X = X*X % M
        break
    visited[X] = (ans, i)
    ans += X
    X = X*X % M
print(ans)
### BUGGY CODE ###

#coding:utf-8



def main():
    
    def dbg(*something):
        if DEBUG:
            print(*something)


    #正の宝石を戻すことはない
    #負の宝石を戻すのは後半
    from sys import stdin
    from math import ceil,floor
    DEBUG = False
    N,K = list(map(int,stdin.readline().split()))
    V = list(map(int,stdin.readline().split()))


    #残りk回のとき深さk以下の場所に正の宝石がない→終了
    #i回の操作で取れる石>それまでにとるi-1個の石の和
    #深さiにある石vの価値：v - (それまでにとるi-1個の石の和　except (k-i)個の負の石)
    '''
    '''




    def tansaku(left,right,rK,N,score):
        dbg(V[left:right+1],rK,N,score)

        N.sort()
        # max_v = score + sum(N[rK:])
        max_v = score
        for n in N[rK:]:
            max_v += n


        # n = []
        for i in range(left,min(rK+left, ceil((right - left +1)/2)+left)):
            
            if V[i] <= 0:
                #n.append(V[i])
                continue


            next_rK = rK - 1 - (i - left)
            next_tmp_v = tansaku(i+1,right,  next_rK, N+V[left:i], score+V[i])
            #next_tmp_v = tansaku(i+1,right,  next_rK, newN, score+V[i])
            max_v = max(next_tmp_v , max_v)


            break

        # n = []
        for i in range(right ,max(right - ceil((right-left+1)/2)  ,right-rK)  ,-1 ):
            
            if V[i] <= 0:
                #n.append(V[i])
                continue

            #next_V = V[:i]
            next_rK = rK - 1 - (right - i)
            #next_tmp_v = tansaku(   left,   i- left -1  ,next_rK,N+n,score+V[i])
            next_tmp_v = tansaku(   left,   i-1  ,next_rK,N+V[i+1:right+1],score+V[i])
            max_v = max(next_tmp_v , max_v)
            break


        return max_v

    print(tansaku(0,len(V)-1,K,[],0))





if __name__ == '__main__':
    main()


### FIXED CODE ###

#coding:utf-8



def main():
    
    def dbg(*something):
        if DEBUG:
            print(*something)


    #正の宝石を戻すことはない
    #負の宝石を戻すのは後半
    from sys import stdin
    from math import ceil,floor
    DEBUG = False
    N,K = list(map(int,stdin.readline().split()))
    V = list(map(int,stdin.readline().split()))
    
    max_value = 0
    dbg([i for i in range(3,-1,-1)])
    for getnum in range(1,min(N+1,K+1)):  #取る宝石の総数
        for a in range(getnum + 1):  #左から石を取る回数
            J = [0] * getnum #石
            b = getnum - a #右から石を取る回数
            for i in range(a):
                J[i] = V[i]
            for i in range(b):
                J[a+i] = V[-i-1]
            J.sort()
            #dbg(J,a,b)
            t = min(K-getnum,getnum) #捨てる石
           
            for i in range(t): 
                if J[i] >= 0:
                    t = i
                    break
            #dbg(J,i,t,a,b,J[t:])
            tmp_max = sum(J[t:])

            max_value = max(max_value,tmp_max)
    print(max_value)



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

class UnionFind:
    def __init__(self, size: int):
        self.__root = [-1 for _ in range(size)]

    def find(self, v: int) -> int:
        if self.__root[v] < 0:
            return v
        self.__root[v] = self.find(self.__root[v])
        return self.__root[v]

    def size(self, v: int) -> int:
        r = self.find(v)
        return -self.__root[r]

    def unite(self, u: int, v: int):
        ur, vr = self.find(u), self.find(v)
        if ur == vr:
            return

        if self.size(ur) < self.size(vr):
            ur, vr = vr, ur

        self.__root[ur] += self.__root[vr]
        self.__root[vr] = ur

    def connected(self, u: int, v: int):
        return self.find(u) == self.find(v)


def decayed_bridges(N: int, M: int, edges: list) -> list:
    ret = [N*(N-1)//2]
    uf = UnionFind(N+1)

    for u, v in reversed(edges):
        ret = [ret[0]] + ret[:]

        if not uf.connected(u, v):
            n1, n2 = uf.size(u), uf.size(v)
            ret[0] -= n1 * n2
            uf.unite(u, v)

    return ret[1:]


if __name__ == "__main__":
    N, M = [int(s) for s in input().split()]
    edges = []
    for _ in range(M):
        a, b = [int(s) for s in input().split()]
        edges.append((a, b))

    answers = decayed_bridges(N, M, edges)

    for a in answers:
        print(a)


### FIXED CODE ###

class UnionFind:
    def __init__(self, size: int):
        self.__root = [-1 for _ in range(size)]

    def find(self, v: int) -> int:
        if self.__root[v] < 0:
            return v
        self.__root[v] = self.find(self.__root[v])
        return self.__root[v]

    def size(self, v: int) -> int:
        r = self.find(v)
        return -self.__root[r]

    def unite(self, u: int, v: int):
        ur, vr = self.find(u), self.find(v)
        if ur == vr:
            return

        if self.size(ur) < self.size(vr):
            ur, vr = vr, ur

        self.__root[ur] += self.__root[vr]
        self.__root[vr] = ur

    def connected(self, u: int, v: int):
        return self.find(u) == self.find(v)


def decayed_bridges(N: int, M: int, edges: list) -> list:
    ret = [0 for _ in range(M)]
    uf = UnionFind(N)

    current = N*(N-1)//2
    for m in range(M-1, -1, -1):
        ret[m] = current

        u, v = edges[m]
        u, v = u-1, v-1

        if not uf.connected(u, v):
            n1, n2 = uf.size(u), uf.size(v)
            current -= n1 * n2
            uf.unite(u, v)

    return ret


if __name__ == "__main__":
    N, M = [int(s) for s in input().split()]
    edges = []
    for _ in range(M):
        a, b = [int(s) for s in input().split()]
        edges.append((a, b))

    answers = decayed_bridges(N, M, edges)

    for a in answers:
        print(a)
### BUGGY CODE ###

from fractions import gcd
a,b = map(int,input().split())
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors
y = sorted(make_divisors(gcd(a,b)))
r = []
for i in y[1:]:
    y_y = make_divisors(i)
    f = True
    for j in y_y:
        if j in r:
            f = False
            break
    if f:
        r.append(i)
print(len(r)+1)

### FIXED CODE ###

from fractions import gcd
a,b = map(int,input().split())
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors
y = sorted(make_divisors(gcd(a,b)))
r = []
for i in y[1:]:
    y_y = make_divisors(i)
    f = True
    for j in y_y:
        if j in r:
            f = False
            break
    if f:
        r.append(i)
print(len(r)+1)
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-

import numpy

def main():
  n, k = map(int, input().strip().split())
  Hs = list(map(int, input().strip().split()))
  dp = numpy.zeros(n, dtype=numpy.int)
  for i in range(1, n):
    dp[i] = numpy.min([dp[i-(k+1)] + abs(Hs[i] - Hs[i-(k+1)]) for k in range(k) if i-(k+1) >= 0])
  print(dp[-1])


if __name__=='__main__':
  main()

### FIXED CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-

import numpy

def main():
  n, k = map(int, input().strip().split())
  Hs = numpy.array([int(line) for line in input().strip().split()], dtype=numpy.int)
  dp = numpy.zeros(n, dtype=numpy.int)
  for i in range(1, n):
    if i - k < 0:
      dp[i] = numpy.min(dp[:i] + numpy.abs(Hs[i] - Hs[:i]))
    else:
      dp[i] = numpy.min(dp[(i-k):i] + numpy.abs(Hs[i] - Hs[(i-k):i]))
  print(dp[-1])


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

from collections import deque

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

moves = [(-1, 0), (1, 0), (0, -1), (0, 1)] 

def bfs():
    dist = [[0 for _ in range(W)] for _ in range(H)]
    routes = deque()
    routes.append((0, 0)) 

    while len(routes) > 0:
        x, y = routes.popleft()
        for move in moves:
            cx, cy = x + move[0], y + move[1]
            if cx < 0 or cy < 0 or cx >= W or cy >= H or c[cy][cx] == '#':
                continue
            if cx == W-1 and cy == H-1: 
                return sum([line.count('.')for line in c]) - dist[y][x] - 2 
            routes.append((cx, cy))
            dist[cy][cx] = dist[y][x] + 1 
    return -1

print(bfs())

### FIXED CODE ###

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

moves = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def bfs():
    visited = [[False for _ in range(W)] for _ in range(H)]
    dist = [[[] for _ in range(W)] for _ in range(H)]
    routes = [(0, 0)]
    visited[0][0] = True

    hop_count = 0
    while len(routes) > 0:
        x, y = routes.pop(0)
        for move in moves:
            cx, cy = x + move[0], y + move[1]
            if cx < 0 or cy < 0 or cx >= W or cy >= H or c[cy][cx] == '#' or visited[cy][cx]:
                continue
            if cx == W-1 and cy == H-1:
                return sum([line.count('.')for line in c]) - len(dist[y][x]) - 2
            visited[cy][cx] = True
            routes.append((cx, cy))
            dist[cy][cx] += dist[y][x] + [(x, y)]
    return -1

print(bfs())
### BUGGY CODE ###

def gcd(x,y):
  return (y if x%y==0 else gcd(y,x%y))
def lcd(x,y):
  return x*y//gcd(x,y)
N=int(input())
A=sorted(list(map(int,input().split())),reverse=True)
l=1
for a in A:
  l=lcd(a,l)
ans=0
for a in A:
  ans=(ans+l//a)
print(ans%1000000007)

### FIXED CODE ###

P=1000000007
def power(x,p):
  if(p==0):
    return 1;
  if(p%2):
    return power(x,p-1)*x%P;
  a=power(x,p//2);
  return a*a%P;
def inv(x):
  return power(x,P-2);
N=int(input());A=list(map(int,input().split()));
#N=10000;A=[1000000 for i in range(N)];
L=[0 for i in range(max(A)+1)]
for a in A:
  t=a;i=2;
  while(i**2<=a):
    c=0;
    while(t%i==0):
      t//=i;c+=1;
    L[i]=max(L[i],c)
    i+=1;
  if(t!=1):
    L[t]=max(L[t],1)
    
l=1;
for i in range(2,len(L)):
  l=l*power(i,L[i])%P;
b=0;
for a in A:
  b=(b+inv(a))%P
print(l*b%P)