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

N = int(input())
# X = [[1 if i == j else 0 for j in range(N)] for i in range(N)]
X = [[0] * N for _ in range(N)]
for i in range(1, N):
    X[i][:i] = [int(a) for a in input()]
for i in range(N):
    for j in range(i+1, N):
        X[i][j] = X[j][i]^1
Y = [[] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if X[i][j]: Y[i].append(j)

dpl = [[0] * N for _ in range(N)]
dpr = [[0] * N for _ in range(N)]
for i in range(N):
    dpl[i][i] = 1
    dpr[i][i] = 1

for d in range(2, N+1):
    for i in range(N-d+1):
        j = i + d - 1
        for k in range(i+1, j+1):
            if X[i][k] and dpr[i+1][k] and dpl[k][j]:
                dpl[i][j] = 1
                break
        for k in range(i, j):
            if X[j][k] and dpr[i][k] and dpl[k][j-1]:
                dpr[i][j] = 1
                break

print(sum([1 if dpr[0][i] and dpl[i][N-1] else 0 for i in range(N)]))

### FIXED CODE ###

N = int(input())
X = [[0] * N for _ in range(N)]
for i in range(1, N):
    X[i][:i] = [int(a) for a in input()]
for i in range(N):
    for j in range(i+1, N):
        X[i][j] = X[j][i]^1

A = [1<<i for i in range(N)]
B = [1<<i for i in range(N)]
for i in range(N):
    for j in range(i):
        if i and B[i-1] >> j & 1 and X[i][j]: A[i] |= A[j]
    for j in range(i):
        if A[i] >> j+1 & 1 and X[j][i]: B[i] |= B[j]

print(sum([(A[i] & 1) * (B[N-1]>>i & 1) for i in range(N)]))
### BUGGY CODE ###

N = int(input())
S = input()
count = 0
for i in range(1,N+1):
    for j in range(i+1,N+1):
        for k in range(j+1,N+1):
            if j-i != k-j and S[i-1] != S[j-1] and S[j-1]!=S[k-1] and S[k-1]!=S[i-1]:
                count += 1
print(count)



### FIXED CODE ###

N = int(input())
S = input()
count = 0
r=0
g=0
b=0
#i,j,k-->i,j,2j-i
for i in range(N):
    if S[i]=="R":
        r+=1
    elif S[i]=="G":
        g+=1
    else:
        b+=1
    for j in range(i+1,N):
        if 2*j-i <= N-1:
            if S[i] != S[j] and S[j]!=S[2*j-i] and S[2*j-i]!=S[i]:
                count -= 1
count += r*g*b
print(count)
### BUGGY CODE ###

import bisect
from collections import Counter
N = int(input())
p = list(map(int, input().split()))

cnt = Counter(p)

ps = set(p)
plst = list(ps)
plst.sort()
temp = plst[:]
ans = 0
while temp:
    q = temp[0]
    lst = []
    for i in temp:
        if i%q!=0: lst.append(i)
    if cnt[q] == 1: ans += 1
    temp = lst[:]

print(ans)

### FIXED CODE ###

from collections import Counter
N = int(input())
p = list(map(int, input().split()))

cnt = Counter(p)

ps = set(p)
plst = list(ps)
plst.sort()

ans = [0] * (plst[-1] + 1)

for i in range(len(plst)):
    for j in range(plst[i], plst[-1]+1, plst[i]):
        ans[j] += 1
d = 0
for i in range(len(plst)):
    if ans[plst[i]]==1 and cnt[plst[i]]==1: d += 1
print(d)
### BUGGY CODE ###

from collections import Counter
n = int(input())
c = Counter(map(int, input().split()))
dp = [[[0]*(n+1) for _ in range(n+1)] for _ in range(n+1)]

for i in range(n+1):
    for j in range(n+1):
        for k in range(n+1):
            non_zero = i+j+k
            if non_zero == 0:
                continue
            dp[i][j][k] = n
            if 0 <= i-1 and j+1 <= n:
                dp[i][j][k] += dp[i-1][j+1][k]*i
            if 0 <= j-1 and k+1 <= n:
                dp[i][j][k] += dp[i][j-1][k+1]*j
            if 0 <= k-1:
                dp[i][j][k] += dp[i][j][k-1]*k
            dp[i][j][k] /= non_zero
print(dp[c[3]][c[2]][c[1]])

### FIXED CODE ###

from collections import Counter
n = int(input())
c = Counter(map(int, input().split()))
dp = [[[0]*(n+1) for _ in range(n+1)] for _ in range(n+1)]

for i in range(n+1):
    for j in range(n+1-i):
        for k in range(n+1-i-j):
            non_zero = i+j+k
            if non_zero == 0:
                continue
            dp[i][j][k] = n
            if 0 <= i-1 and j+1 <= n:
                dp[i][j][k] += dp[i-1][j+1][k]*i
            if 0 <= j-1 and k+1 <= n:
                dp[i][j][k] += dp[i][j-1][k+1]*j
            if 0 <= k-1:
                dp[i][j][k] += dp[i][j][k-1]*k
            dp[i][j][k] /= non_zero

print(dp[c[3]][c[2]][c[1]])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
#
import math
import sys
import itertools
import numpy as np
from collections import deque

h,w = map(int, input().split())

ch,cw = map(int, input().split())
dh,dw = map(int, input().split())

maze =["#"*(w+4) for i in range(2)] + ["##"+input()+"##" for i in range(h)] + ["#"*(w+4) for i in range(2)]
temp = [[-1]*(w+4) for i in range(h+4)]

#print(maze)

q = deque([(ch+1,cw+1)])
temp[ch+1][cw+1]=0

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

while q:
    y,x = q.popleft()
#    print(y,x)
    # aruki
    for i in opt:
        ty,tx = y+i[0], x+i[1]
        if maze[ty][tx]=='#':
            continue
        if (temp[ty][tx] == -1 or temp[ty][tx] > temp[y][x]):
            temp[ty][tx] = temp[y][x] # ikeru
            q.appendleft((ty,tx)) # new ikeru basho tuika
    # warp
    for i in range(-2,3):
        for j in range(-2,3):
            ty,tx = y+i, x+j
            if maze[ty][tx] == "#":
                continue
            if temp[ty][tx] == -1 or temp[ty][tx] > temp[y][x]+1:
                temp[ty][tx] =  temp[y][x]+1
                q.append((ty,tx))  # 
#    print(q)


print(temp[dh+1][dw+1])



### FIXED CODE ###

# -*- coding: utf-8 -*-
#
import math
import sys

from collections import deque

h,w = map(int, input().split())

ch,cw = map(int, input().split())
dh,dw = map(int, input().split())

maze =["#"*(w+4) for i in range(2)] + ["##"+input()+"##" for i in range(h)] + ["#"*(w+4) for i in range(2)]
temp = [[-1]*(w+4) for i in range(h+4)]

#print(maze)

q = deque([(ch+1,cw+1)])
temp[ch+1][cw+1]=0

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

while q:
    y,x = q.popleft()
#    print(y,x)
    # aruki
    for i in opt:
        ty,tx = y+i[0], x+i[1]
        if maze[ty][tx]=='#':
            continue
        if (temp[ty][tx] == -1 or temp[ty][tx] > temp[y][x]):
            temp[ty][tx] = temp[y][x] # ikeru
            q.appendleft((ty,tx)) # new ikeru basho tuika
    # warp
    for i in range(-2,3):
        for j in range(-2,3):
            ty,tx = y+i, x+j
            if maze[ty][tx] == "#":
                continue
            if temp[ty][tx] == -1 or temp[ty][tx] > temp[y][x]+1:
                temp[ty][tx] =  temp[y][x]+1
                q.append((ty,tx))  # 
#    print(q)


print(temp[dh+1][dw+1])
### BUGGY CODE ###

n = int(raw_input())
s = raw_input()
aa = s.split(" ")
aaa = []
for i in range(n):
	aaa.append((i+1,int(aa[i])))

ctr = 0

for (a,b) in aaa:
	if (b,a) in aaa:
		aaa.remove((a,b))
		aaa.remove((b,a))
		ctr = ctr + 1
# ctr = ctr / 2
print(str(ctr))

### FIXED CODE ###

n = int(raw_input())
s = raw_input()
aa = s.split(" ")
aa = [int(x)-1 for x in aa]

ctr = 0

for i in range(n):
	if i == aa[aa[i]]:
		ctr = ctr + 1

ctr = ctr / 2

print(str(ctr))
### BUGGY CODE ###

n = int(input())
s = input()
ans = 0

positions = {}
positions['R'] = [i for i in range(n) if s[i]=='R']
positions['G'] = [i for i in range(n) if s[i]=='G']
positions['B'] = [i for i in range(n) if s[i]=='B']
positions['RG'] = sorted(positions['R']+positions['G'])
positions['RB'] = sorted(positions['R']+positions['B'])
positions['GB'] = sorted(positions['G']+positions['B'])

for p1 in range(n-3):
    if s[p1] == 'R':
        pos2 = positions['GB']
    elif s[p1] == 'G':
        pos2 = positions['RB']
    else:
        pos2 = positions['RG']

    for p2 in pos2:
        if p2 > p1:
            if s[p1] == 'R' and s[p2] == 'G':
                pos3 = positions['B']
            elif s[p1] == 'R' and s[p2] == 'B':
                pos3 = positions['G']
            elif s[p1] == 'G' and s[p2] == 'B':
                pos3 = positions['R']
            elif s[p1] == 'G' and s[p2] == 'R':
                pos3 = positions['B']
            elif s[p1] == 'B' and s[p2] == 'R':
                pos3 = positions['G']
            elif s[p1] == 'B' and s[p2] == 'G':
                pos3 = positions['R']
            
            for p3 in pos3:
                if p3 > p2:                
                    if (p1-p2 != p2-p3):
                        ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
dup = 0
r = s.count('R')
g = s.count('G')
b = s.count('B')

for i in range(n):
    for j in range(i+1, n):
        k = 2*j - i
        if k < n:
            #print(i,j,k)
            if (s[i] != s[j]) and (s[j] != s[k]) and (s[i] != s[k]):
                #print(s[i], s[j], s[k])
                dup += 1
print(r*g*b - dup)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import math

big = 10 ** 9 + 7

N = int(input())
A = list(map(int, input().split()))
num = A[0]
for i in range(1, N):
    num = num * A[i] // math.gcd(num, A[i])

res = 0
for a in A:
    res += num // a % big

print(res % big)


### FIXED CODE ###

import sys
input = sys.stdin.readline
import math

def main():
    big = 10 ** 9 + 7

    N = int(input())
    A = list(map(int, input().split()))
    num = A[0]
    for i in range(1, N):
        num = num * A[i] // math.gcd(num, A[i])

    res = 0
    for a in A:
        res += num // a

    print(res % big)

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

from heapq import heappush, heappop

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]

ans = 0
hq = []
for i in range(1, m+1):
    for a, b in ab:
        if a == i:
            heappush(hq, (-b, a))
    
    if len(hq) != 0:
        ans -= heappop(hq)[0]
    
print(ans)

### FIXED CODE ###

from heapq import heappush, heappop

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]

ab.sort()
ans = 0
hq = []
idx = 0
for i in range(1, m+1):
    for j in range(idx, n):
        if ab[j][0] == i:
            heappush(hq, (-ab[j][1], ab[j][0]))
            idx += 1
        else:
            break
    if len(hq) != 0:
        ans -= heappop(hq)[0]
    
print(ans)
### BUGGY CODE ###

from collections import Counter
 
input()
c = Counter(map(int, input().split()))
r = int(c[1] == 1)
if c[1] == 0:
  for k, v in c.items():
    if v == 1:
      i = 2
      while i * i <= k and (k % i or c[i] == c[k // i] == 0):
        i += 1
      if i * i > k:
        r += 1
print(r)


### FIXED CODE ###

N = 1000001
a = [0]* N
input()
for x in input().split():
  a[int(x)] += 1
for i in range(1, N):
  for j in range(i + i, N, i):
    if a[i]:
      a[j] = 0
print(a.count(1))
### BUGGY CODE ###

MOD = 10**9 + 7

fact = {i: None for i in range(10**6+1)}                 # n!
inverse = {i: None for i in range(1, 10**6+1)}       # inverse of n in the field Z/(MOD)Z
fact_inverse = {i: None for i in range(10**6+1)}  # inverse of n! in the field Z/(MOD)Z

fact[0] = fact[1] = 1
fact_inverse[0] = fact_inverse[1] = 1
inverse[1] = 1
for i in range(2, 10**6+1):
    fact[i] = i * fact[i-1] % MOD
    inverse[i] = - inverse[MOD % i] * (MOD // i) % MOD
    fact_inverse[i] = inverse[i] * fact_inverse[i-1] % MOD

def combination(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    else:
        return fact[n] * (fact_inverse[r] * fact_inverse[n-r] % MOD) % MOD

n = int(input())
A = list(map(int, input().split()))

dup_num = sum(A) - n*(n+1)//2
dup_idx = []
for i, a in enumerate(A):
    if a == dup_num:
        dup_idx.append(i)
        
left, right = dup_idx[0], dup_idx[1]
        
for k in range(1, n+2):
    print((combination(n+1, k) - combination(n + 1 - (right - left + 1), k - 1)) % MOD)

### FIXED CODE ###

MOD = 10**9 + 7
n = int(input())
A = list(map(int, input().split()))

fact = {i: None for i in range(n+2)}                 # n!
inverse = {i: None for i in range(1, n+2)}       # inverse of n in the field Z/(MOD)Z
fact_inverse = {i: None for i in range(n+2)}  # inverse of n! in the field Z/(MOD)Z

fact[0] = fact[1] = 1
fact_inverse[0] = fact_inverse[1] = 1
inverse[1] = 1
for i in range(2, n+2):
    fact[i] = i * fact[i-1] % MOD
    inverse[i] = - inverse[MOD % i] * (MOD // i) % MOD
    fact_inverse[i] = inverse[i] * fact_inverse[i-1] % MOD

def combination(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    else:
        return fact[n] * (fact_inverse[r] * fact_inverse[n-r] % MOD) % MOD

dup_num = sum(A) - n*(n+1)//2
dup_idx = []
for i, a in enumerate(A):
    if a == dup_num:
        dup_idx.append(i)
        
left, right = dup_idx[0], dup_idx[1]
        
for k in range(1, n+2):
    print((combination(n+1, k) - combination(n + 1 - (right - left + 1), k - 1)) % MOD)
### BUGGY CODE ###

import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l():
    return list(map(int,input().split()))
def m():
    return map(int,input().split())
def onem():
    return int(input())
def s(x):
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa == x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x):
    return " ".join(map(str,x))

n,m = m()

S = l()
T = l()

dp = [ [0 for i in range(n+1)]  for j in range(m+1)]

for i in range(n+1):
    dp[0][i] = 1
for i in range(m+1):
    dp[i][0] = 1

for i in range(n):
    for j in range(m):
        if S[i] == T[j]:
            dp[j+1][i+1] += dp[j][i]
        dp[j+1][i+1] +=dp[j+1][i] + dp[j][i+1] - dp[j][i]
        dp[j+1][i+1] %= 10**9+7
print(dp[-1][-1])



### FIXED CODE ###

import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l():
    return list(map(int,input().split()))
def m():
    return map(int,input().split())
def onem():
    return int(input())
def s(x):
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa == x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x):
    return " ".join(map(str,x))

n,m = m()

S = l()
T = l()

dp = [ [0 for i in range(n+1)]  for j in range(m+1)]

for i in range(n+1):
    dp[0][i] = 1
for i in range(m+1):
    dp[i][0] = 1

for i in range(n):
    for j in range(m):
        if S[i] == T[j]:
            dp[j+1][i+1] += dp[j][i]
        dp[j+1][i+1] +=dp[j+1][i] + dp[j][i+1] - dp[j][i]
        dp[j+1][i+1] %= 10**9+7
print(dp[-1][-1])
### BUGGY CODE ###

import bisect
N = int(input())
A = [int(input()) for _ in range(N)]
first = []
for a in A:
    i = bisect.bisect_left(first,a)
    if i == 0:
        first.insert(0,a)
    else:
        first[i-1] = a
print(len(first))

### FIXED CODE ###

import bisect
N = int(input())
A = [int(input()) for _ in range(N)]
first = [-1 for _ in range(N)]
for a in A:
    i = bisect.bisect_left(first,a)
    first[i-1] = a
ctr = N
for f in first:
    if f == -1:
        ctr -= 1
print(ctr)
### BUGGY CODE ###

import heapq
import numpy as np

N, M = [int(x) for x in input().split(" ")]

e = {i: [] for i in range(N)}
for _ in range(M):
  a, b = [int(x)-1 for x in input().split(" ")]
  e[a] = e[a] + [b]
  e[b] = e[b] + [a]

# roots = [[int(x) for x in input().split(" ")] for _ in range(M)]

d = np.ones(N, dtype=int) * np.inf
d[0] = 0
prev = np.ones(N, dtype=int) * -1
q = [(d[0], 0)]
heapq.heapify(q)

while len(q) != 0:
  c, u = heapq.heappop(q)
  for nv in e[u]:
    alt = d[u] + 1
    if d[nv] > alt:
      d[nv] = alt
      prev[nv] = u
      heapq.heappush(q, (alt, nv))

print("Yes")
for p in prev[1:]:
  print(p+1)


### FIXED CODE ###

import numpy as np
N, M = map(int, input().split(" "))

goto = {i: [] for i in range(1, N+1)}
sign = np.zeros(N, dtype=int)
for _ in range(M):
  A, B = map(int, input().split(" "))
  goto[A].append(B)
  goto[B].append(A)

# print(goto)

visited = set([1])
queue = [1]
while len(queue) > 0:
  v = queue.pop(0)
  for nex in goto[v]:
    if nex in visited:
      continue
    sign[nex-1] = v
    queue.append(nex)
    visited.add(nex)
print("Yes")
for s in sign[1:]:
  print(s)
### BUGGY CODE ###

S = input()
INF = 10 ** 9 + 7

dp = [[0 for _ in range(13)] for _ in range(len(S) + 1)]
index = 1
dp[0][0] = 1
for i in range(len(S)):
    c = S[-i - 1]
    if c == '?':
        for j in range(10):
            for k in range(13):
                dp[i + 1][(j * index + k) % 13] += dp[i][k]
                dp[i + 1][(j * index + k) % 13] %= INF
    else:
        c = int(c)
        for k in range(13):
            dp[i + 1][(c * index + k) % 13] += dp[i][k]
            dp[i + 1][(c * index + k) % 13] %= INF
    index *= 10

print(dp[len(S)][5])

### FIXED CODE ###

S = input()
INF = 10 ** 9 + 7

dp = [[0 for _ in range(13)] for _ in range(len(S) + 1)]
index = 1
dp[0][0] = 1
for i in range(len(S)):
    c = S[-i - 1]
    if c == '?':
        for j in range(10):
            for k in range(13):
                dp[i + 1][(j * index + k) % 13] += dp[i][k]
                dp[i + 1][(j * index + k) % 13] %= INF
    else:
        c = int(c)
        for k in range(13):
            dp[i + 1][(c * index + k) % 13] += dp[i][k]
            dp[i + 1][(c * index + k) % 13] %= INF
    index *= 10
    index %= 13

print(dp[len(S)][5])
### BUGGY CODE ###

import math


def k_choose_r(k,r):
    return math.factorial(k) / math.factorial(r) / math.factorial(k-r)


n = int(raw_input())
nums = map(int, raw_input().split())

nums = sorted(nums)
top = nums[-1]
best_value = 0
low = nums[n / 2 - 1]
high = nums[n / 2]

low_val = k_choose_r(top, low)
high_val = k_choose_r(top, high)

if low_val > high_val:
    bottom = low
else:
    bottom = high

if bottom == top:
    bottom = low + high - bottom

print "{} {}".format(top, bottom)


### FIXED CODE ###

import bisect


def get_closest(nums, target):
    pos = bisect.bisect_left(nums, target)
    if pos == 0:
        return nums[0]
    if pos == len(nums):
        return nums[-1]

    before = nums[pos - 1]
    after = nums[pos]

    if target in [before, after]:
        return target

    if after - target < target - before:
        return after
    else:
        return before


n = int(raw_input())
nums = map(int, raw_input().split())

nums = sorted(nums)
top = nums[-1]
nums.remove(top)

if top % 2 == 0:
    optimal = top / 2
    bottom = get_closest(nums, optimal)
else:
    res1 = get_closest(nums, top / 2)
    res2 = get_closest(nums, (top + 1) / 2)

    if abs(res1 - (top/2)) < abs(res2 - ((top + 1) / 2)):
        bottom = res1
    else:
        bottom = res2

print "{} {}".format(top, bottom)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sat Aug 10 21:22:42 2019

@author: doppe
"""
import copy
import math


def isAnagram(dict, str2):
    dictCopy = copy.copy(dict)
    for c2 in str2:
        if (c2 in dictCopy):
            dictCopy[c2] -= 1
            if (dictCopy[c2] < 0):
                return False
        else:
            return False
    return True
 
def makeDict(str1):
    dict = {}
    for c in str1:
        if (c in dict):
            dict[c] += 1
        else:
            dict[c] = 1
    return dict

A = int(input())
S = []
for i in range (0, A):
    S.append(input())

ans = 0
groupList = []
groupDict = {}
for i in range(0, len(S)):
    if (i in groupList):
        continue
    dict = makeDict(S[i])
    for j in range(i + 1, len(S)):
        if (j in groupList):
            continue
        if (isAnagram(dict, S[j])):
            groupList.append(j)
            if (S[i] in groupDict):
                groupDict[S[i]] += 1
            else:
                groupDict[S[i]] = 2

for v in groupDict.values():
    ans += (v * (v - 1)) / 2

print(int(ans))

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sat Aug 10 23:27:57 2019

@author: doppe
"""

A = int(input())
S = []
for i in range (0, A):
    S.append(input())

ans = 0
groupList = []
groupDict = {}

ans = 0
for i in range(0, len(S)):
    a = list(S[i])
    a.sort()
    b = ''.join(a)
    if b in groupDict:
        groupDict[b] += 1
    else :
        groupDict[b] = 1

for v in groupDict.values():
    ans += (v * (v - 1)) / 2
        
print(int(ans))
### BUGGY CODE ###

import sys
from functools import lru_cache
sys.setrecursionlimit(10**9)


@lru_cache(maxsize=None)
def dp(x1, x2, x3):
    if x1 == x2 == x3 == 0:
        return 0
    eat1 = dp(x1-1, x2, x3)*(x1/N) if x1 > 0 else 0
    eat2 = dp(x1+1, x2-1, x3)*(x2/N) if x2 > 0 else 0
    eat3 = dp(x1, x2+1, x3-1)*(x3/N) if x3 > 0 else 0
    return (1 + eat1 + eat2 + eat3) * (N/(x1+x2+x3))


N = int(input())
a = list(map(int, input().split()))

cnt = [0] * 4
for i in range(N):
    cnt[a[i]] += 1
# print(dp(cnt[1], cnt[2], cnt[3]))
print(dp(0, 0, 300))


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline

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

    cnt = [0] * 3
    for a in A:
        cnt[a-1] += 1

    dp = [[[0.] * (N+1) for _ in range(N+1)] for _ in range(N+1)]
    for k in range(N+1):
        for j in range(N+1-k):
            for i in range(N+1-j-k):
                ijk = float(i + j + k)
                if ijk == 0:
                    continue
                x = N / ijk
                tmp = 0
                if i > 0:
                    tmp += (dp[i-1][j][k] + x) * (i / ijk)
                if j > 0 and i < N:
                    tmp += (dp[i+1][j-1][k] + x) * (j / ijk)
                if k > 0 and j < N:
                    tmp += (dp[i][j+1][k-1] + x) * (k / ijk)
                dp[i][j][k] = tmp
    print(dp[cnt[0]][cnt[1]][cnt[2]])


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

n,k = map(int,input().split())
rc = [list(map(int,input().split())) for i in range(k)]

tmp = set(range(1,n+1))

for i in rc:
    tmp = tmp & set(range(i[0],i[1]+1))

print(len(tmp))

### FIXED CODE ###

n,k = map(int,input().split())
rc = [list(map(int,input().split())) for i in range(k)]
transpose = [x for x in zip(*rc)]

ans = min(transpose[1]) - max(transpose[0])

if ans<0:
    print(0)
else:
    print(ans+1)
### BUGGY CODE ###

#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin
from array import array
n = int(stdin.readline())
dll = array('i')
while n:
    n -= 1
    cmd = stdin.readline()
    if cmd.startswith('insert '):
        dll.insert(0, int(cmd[7:]))
    elif cmd.startswith('deleteFirst'):
        del dll[0]
    elif cmd.startswith('deleteLast'):
        del dll[-1]
    elif cmd.startswith('delete '):
        key = int(cmd[7:])
        if dll.count(key):
            dll.remove(key)
print(*dll)

### FIXED CODE ###

#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin
from collections import deque

n = int(stdin.readline())
dll = deque()
fcode = ord('F')
lcode = ord('L')
while n:
    n -= 1
    cmd = stdin.readline().rstrip()
    if cmd.startswith('i'):
        dll.appendleft(int(cmd[7:]))
    elif cmd.startswith('d'):
        c = ord(cmd[6])
        if c == fcode:
            dll.popleft()
        elif c == lcode:
            dll.pop()
        else:
            try:
                dll.remove(int(cmd[7:]))
            except ValueError:
                pass
print(*dll)
### BUGGY CODE ###


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

answer = 0
mod = 10**9 + 7
for i in range(N):
  for j in range(i+1, N):
    multi = (A[i] * A[j])
    answer += multi
answer = answer % mod
print(int(answer))

### FIXED CODE ###

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

answer = 0
a_sum = sum(A)
mod = 10**9+7

for i in range(N-1):
  a_sum -= A[i]
  answer += a_sum * A[i]
print(str(answer % mod))