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

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

c=0
for i in range (N-2):
    for j in range (i+1,N-1):
        for k in range (j+1,N):
            if L[i]+L[j] > L[k] and L[j]+L[k] > L[i] and L[k]+L[i] > L[j]:
                c += 1

print(c)

### FIXED CODE ###

N = int(input())
L = list(map(int,input().split()))
L.sort()
c = 0
for i in range(N-2):
    for j in range(i+1,N-1):
        zum = L[i]+L[j]
        start = j+1
        goal = N-1
        now = (start + goal)//2

        if zum > L[goal]:
            c += goal - j
        elif zum <= L[start]:
            c += 0
        else:
            while not L[now] < zum <= L[now+1]:
                now = (start + goal)//2
                if zum > L[now]:
                    start = now
                else:
                    goal = now
            c += now - j

print(c)
### BUGGY CODE ###

import bisect

A,B,Q=map(int,input().split())

Z=[-10**10]
T=[-10**10]

for i in range(A):
    s=int(input())
    Z.append(s)
Z.append(10**11)
for i in range(B):
    t=int(input())
    T.append(t)
T.append(10**11)
    
for i in range(Q):
    x=int(input())
    a=max(Z[bisect.bisect_left(Z,x)],T[bisect.bisect_left(T,x)])-x
    b=x-min(Z[bisect.bisect_left(Z,x)-1],T[bisect.bisect_left(T,x)-1])
    c=Z[bisect.bisect_left(Z,x)]-T[bisect.bisect_left(T,x)-1]+(x-T[bisect.bisect_left(T,x)-1])
    d=Z[bisect.bisect_left(Z,x)]-T[bisect.bisect_left(T,x)-1]+(Z[bisect.bisect_left(Z,x)]-x)
    e=T[bisect.bisect_left(T,x)]-Z[bisect.bisect_left(Z,x)-1]+(x-Z[bisect.bisect_left(Z,x)-1])
    f=T[bisect.bisect_left(T,x)]-Z[bisect.bisect_left(Z,x)-1]+(T[bisect.bisect_left(T,x)]-x)
    print(min(a,b,c,d,e,f))

### FIXED CODE ###

import bisect
import sys
input = sys.stdin.readline
A,B,Q=map(int,input().split())

Z=[-10**10]
T=[-10**10]

for i in range(A):
    s=int(input())
    Z.append(s)
Z.append(10**11)
for i in range(B):
    t=int(input())
    T.append(t)
T.append(10**11)
    
for i in range(Q):
    x=int(input())
    a=max(Z[bisect.bisect_left(Z,x)],T[bisect.bisect_left(T,x)])-x
    b=x-min(Z[bisect.bisect_left(Z,x)-1],T[bisect.bisect_left(T,x)-1])
    c=Z[bisect.bisect_left(Z,x)]-T[bisect.bisect_left(T,x)-1]+(x-T[bisect.bisect_left(T,x)-1])
    d=Z[bisect.bisect_left(Z,x)]-T[bisect.bisect_left(T,x)-1]+(Z[bisect.bisect_left(Z,x)]-x)
    e=T[bisect.bisect_left(T,x)]-Z[bisect.bisect_left(Z,x)-1]+(x-Z[bisect.bisect_left(Z,x)-1])
    f=T[bisect.bisect_left(T,x)]-Z[bisect.bisect_left(Z,x)-1]+(T[bisect.bisect_left(T,x)]-x)
    print(min(a,b,c,d,e,f))
### BUGGY CODE ###

import numpy as np

s = input().strip()
t = input().strip()

dp = np.zeros((3100, 3100))

for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+1)
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j])
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j+1])

ans = ""
i = len(s)
j = len(t)
while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        ans = s[i-1] + ans
        i -= 1
        j -= 1

print(ans)


### FIXED CODE ###

s = input().strip()
t = input().strip()

dp = [[0 for _ in range(3100)] for _ in range(3100)]

for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+1)
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j])
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j+1])

ans = ""
i = len(s)
j = len(t)
while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        ans = s[i-1] + ans
        i -= 1
        j -= 1

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

import sys
from operator import mul
from functools import reduce

t = 10**18


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

if li.count(0) >= 1:
    print(0)
    sys.exit()

ans = reduce(mul,li)

if ans > t:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

import sys

t = 10**18


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

if li.count(0) >= 1:
    print(0)
    sys.exit()

ans = 1
for i in range(n):
    ans = ans*li[i]
    if ans > t:
        print(-1)
        sys.exit()

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

STRI = input()
DICT = STRI.split()
A=int(DICT[0])
B=int(DICT[1])
K=int(DICT[2])
cA=A
cB=B

for TIMES in range(K):
    if cA > 0:
        cA=cA-1
    elif cB > 0:
        cB=cB-1

print(str(cA) + " " + str(cB))

### FIXED CODE ###

STRI = input()
DICT = STRI.split()
A=int(DICT[0])
B=int(DICT[1])
K=int(DICT[2])

cA = A
cB = B

if A+B <= K:
    cA = 0
    cB = 0
else:
    if A >= K:
        if A == K:
            cA = 0
        elif A > K:
            cA = A - K
    else:
        cA = 0
        if A+B <= K:
            cA = 0
            cB = 0
        else:
            cB = B - (K - A)

print(cA,cB)
### BUGGY CODE ###

from sys import stdin

import time
import numpy as np
import math

############################################

# read data for n sequences.
temp = stdin.readline().split()
N = int(temp[0])
temp = stdin.readline().split()
data = temp[0]


r = np.sum(np.asarray([d for d in data])=="R")
g = np.sum(np.asarray([d for d in data])=="G")
b = np.sum(np.asarray([d for d in data])=="B")
out = r*g*b

if N > 2:
    for ii, i in enumerate(data[:-2]):
        for jj,j in enumerate(data[ii+1:-1]):
            jj = jj+ii+1
            if i!=j:
                sum1 = 0                    
                for d in np.asarray([d for d in "RGB"]):
                    if i!=d and j!=d:
                        let = d
                if jj+jj-ii<N:
                    if data[jj+jj-ii]==let:                    
                        out-=1
print(out)

### FIXED CODE ###

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

############################################

# read data for n sequences.
N = int(input())
data = input()

out = 0
r=0;g=0;b=0;
for d in data:
    if d =="R":
        r+=1
    elif d=="B":
        b+=1
    else:
        g+=1
out = r*g*b

if N > 2:
    for ii, i in enumerate(data[:-2]):
        for jj,j in enumerate(data[ii+1:-1]):
            jj = jj+ii+1
            if i!=j:
                sum1 = 0                    
                for d in [d for d in "RGB"]:
                    if i!=d and j!=d:
                        let = d

                if jj+jj-ii<N:
                    if data[jj+jj-ii]==let:                    
                        out-=1
print(out)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
k=1
for i in range(n):
    k*=a[i]

if k>10**18:print(-1)
else:print(k)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
k=1
for i in range(n):
    if a[i]==0:
        print(0)
        exit()
for i in range(n):
    k*=a[i]
    if k>10**18:
        print(-1)
        exit()
print(k)
### BUGGY CODE ###

N, K = map(int, input().strip().split(" "))
scores = [int(x) for x in input().strip().split(" ")]
i = 0
grade = 1
for i in range(K):
    grade *= scores[i]

for i in range(K, N):
    last = grade;
    grade = int(grade / scores[i-K])
    grade *= scores[i]
    if (grade > last):
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

N, K = map(int, input().strip().split(" "))
scores = input().strip().split(" ")

for i in range(K, N):
    if (int(scores[i]) > int(scores[i-K])):
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import math
def cmb(n, r):
    return math.factorial(n)// ( math.factorial(n-r) * math.factorial(r) )



N,M = input().split()

N = int(N)
M = int(M)

a = []
ans = 1

for i in range(M):
    newa = int(input())
    a.append(newa)

if (M != 0):
    for k in range(M-1):
        if (a[k+1] - a[k] == 1):
            ans = 0
            
    
    
    for i in range(M + 1):
    

        if (i == 0):
            dan = a[i] - 1
        elif (i == M):
            dan = N - a[i - 1] - 1
        else:
            dan = a[i] - a[i - 1] - 2

        abletwo = (dan - (dan % 2)) // 2
        now = 0

        if (dan != 0):

            for j in range(abletwo + 1):

                now += cmb (dan - j , j )

        else:
            now = 1
        
        ans *= now

else:
    ans = 0
    abletwo = (N - (N % 2)) // 2

    for j in range(abletwo + 1):

        ans += cmb (N - j , j )

ans = ans % 1000000007
print (ans)


### FIXED CODE ###


N, M = input().split()

N = int(N)
M = int(M)
a = []
c = []

for i in range(M):

    anew = int(input())
    a.append(anew)

now_a = 0
a.append(-1)
ans = 0

for i in range( N + 1 ):

    if (i == 0):
        c.append(1)
        
    elif (i == 1):

        if (a[now_a] == i):
            c.append(0)
            now_a += 1
        else:
            c.append(1)

    else:

        if (a[now_a] == i):
            c.append(0)
            now_a += 1
        else:
            c.append( c[i - 1] + c[i - 2])
        

ans = c[N] % 1000000007

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

import math
n,m = map(int,input().split())

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

for i in range(m):
    s = max(list1)
    list1[list1.index(s)]= math.floor(s/2)
print(sum(list1))

### FIXED CODE ###

import math
n,m = map(int,input().split())

a = input()
list1 = list(map(int,a.split()))
list1.sort()
list1.reverse()
i = 0
s = math.floor(list1[0]/2)

if n == 1:
    print(math.floor(list1[0]/(2**m)))
    exit()

while True:
    while True:
        if i+1 > n:
            break
        if list1[i] < s or m == 0:
            break
        list1[i] = math.floor(list1[i]/2)
        m -= 1
        i += 1
    if m == 0:
        break
    list1.sort()
    list1.reverse()
    s = math.floor(list1[0]/2)
    i = 0
print(sum(list1))
### BUGGY CODE ###

ss = input()[::-1]
sv = ''
mods = [ 0 for i in range(2019) ]

for s in ss:
    sv = s + sv
    i = int(sv) % 2019
    mods[i] += 1

ans = 0
for i,v in enumerate(mods):
    if i == 0 and v > 0:
        ans += 1
    else:
        ans += (v * (v - 1)) // 2

print(ans)

### FIXED CODE ###

s = input()[::-1] # 右からn桁の数についてループを回していきたいので、文字列を反転させる

sum_of_digits = 0 # 余りの値
cnts = [0] * 2019 # 余りの値ごとに余りが同じ値の数を格納する変数。2019で割る場合、余りは0~2018までの2019通りあるので、リストの長さは2019
cnts[0] = 1 # ※1
d = 1 # sum_of_digitsの計算に使う10の累乗値

# まず余りの値ごとに余りが同じ値の数を数える
for c in s:
    sum_of_digits += int(c) * d
    sum_of_digits %= 2019
    d *= 10
    d %= 2019 # ※2
    cnts[sum_of_digits] += 1

# 次に余りの値ごとにその組み合わせを計算し、足し合わせる
ans = 0
for cnt in cnts:
    ans += cnt * (cnt - 1) // 2

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

a=list(map(int, input().split()))
taka=a[0]
ao=a[1]
K=a[2]
i=0
while 1:
    if i<K:
        if taka>0:
            taka-=1
            i+=1
        elif ao>0:
            ao-=1
            i+=1
        else:
            break
    else:
        break
print(taka,ao)

### FIXED CODE ###

a=list(map(int, input().split()))
taka=a[0]
ao=a[1]
K=a[2]
if K==taka:
    print(0,ao)
elif K<taka:
    print(taka-K,ao)
elif K>taka and K-taka<=ao:
    print(0,ao-(K-taka))
elif K>taka and K-taka>=ao:
    print(0,0)
### BUGGY CODE ###

n = int(input())
ans = 0
for i in range(1,n):
    ans += i

print(ans)

### FIXED CODE ###

n = int(input())
ans = (n-1)*n // 2
print(ans)
### BUGGY CODE ###

s = input()

dp = [[0 for i in range(13)] for j in range(len(s)+1)]

mod = 10**9+7

for i in reversed(range(len(s))):
    keta = len(s) - i - 1
    if i == len(s) - 1:
        if s[i] == '?':
            for k in range(10):
                amari = (k*(10**keta)) % 13
                dp[keta+1][amari] += 1
                
        else:
            amari = (int(s[i])*(10**keta)) % 13
            #print(keta,amari)
            dp[keta+1][amari] += 1
        continue
    
    
    if s[i] == '?':
        for k in range(10):
            for j in range(13):
                amari = (j+k*(10**keta)) % 13
                #print(amari,i)
                dp[keta+1][amari] += dp[keta][j]
                dp[keta+1][amari] %= mod
    else:
        for j in range(13):
            amari = (j+(int(s[i])*(10**keta))) % 13
            #print(keta,amari)
            dp[keta+1][amari] += dp[keta][j]
            dp[keta+1][amari] %= mod
            
print(dp[len(s)][5])
#print(dp[len(s)][5])

### FIXED CODE ###

s = input()

dp = [[0 for i in range(13)] for j in range(len(s)+1)]

mod = 10**9+7
mul = 1
dp[0][0] = 1

for i in reversed(range(len(s))):
    keta = len(s) - i - 1
    if s[i] == '?':
        for k in range(10):
            for j in range(13):
                amari = (j+k*(mul)) % 13
                #print(amari,i)
                dp[keta+1][amari] += dp[keta][j]
                dp[keta+1][amari] %= mod
    else:
        num = int(s[i])
        for j in range(13):
            amari = (j+(num*(mul))) % 13
            #print(keta,amari)
            dp[keta+1][amari] += dp[keta][j]
            dp[keta+1][amari] %= mod
    mul = mul * 10 % 13
            
print(dp[len(s)][5])
#print(dp[len(s)][5])
### BUGGY CODE ###

import sys

N=int(sys.stdin.readline())
A=list(map(int,sys.stdin.readline().split()))
B=list(map(int,sys.stdin.readline().split()))

#print(A,B)
#print([bin(A[i]) for i in range(N)])
#print([bin(B[i]) for i in range(N)])

ANS=""
for i in range(1,30):
    XA=sorted([A[t]%(2**i) for t in range(N)])
    XB=sorted([B[t]%(2**i) for t in range(N)])
    XB.append(2**(i+1))
    XA.reverse()

    #print(XA,XB)

    b0=0
    b1=0
    b2=0
    #b3=0
    count=0

    for xa in XA:
        for j in range(b0,N+1):
            if 2**(i-1)<=xa+XB[j]:
                break

        b0=j
        for j in range(b1,N+1):
            if xa+XB[j]>=2**i:
                break
        b1=j

        for j in range(b2,N+1):
            if 2**(i-1)*3<=xa+XB[j]:
                break
        b2=j

        #for j in range(b3,N):
        #    if xa+XB[j]>=2**(i+1):
        #        break
        #b3=j

        #print(xa,XB,b0,b1,b2)

        count+=b1-b0+N-b2

    ANS+=str(count%2)

#print(ANS)
print(int(ANS[::-1],2))

### FIXED CODE ###

import sys

N=int(sys.stdin.readline())
A=list(map(int,sys.stdin.readline().split()))
B=list(map(int,sys.stdin.readline().split()))

ANS=""
for i in range(1,30):
    k=2**i
    XA=sorted([a%k for a in A],reverse=True)
    XB=sorted([b%k for b in B])
    XB.append(k*2)

    b0=0
    b1=0
    b2=0
    count=0

    for xa in XA:
        for j in range(b0,N+1):
            if k//2<=xa+XB[j]:
                b0=j
                break

        if b1<b0:
            b1=b0

        
        for j in range(b1,N+1):
            if xa+XB[j]>=k:
                b1=j
                break

        if b2<b1:
            b2=b1

        for j in range(b2,N+1):
            if k*3//2<=xa+XB[j]:
                b2=j
                break

        count+=(b1-b0+N-b2)

    ANS+=str(count%2)

print(int(ANS[::-1],2))
### BUGGY CODE ###

def solve(N, Q, S, L_R):
    answers = [0] * Q
    for i in range(len(S) - 1):
        if S[i] == "A" and S[i + 1] == "C":
            for j in range(len(L_R)):
                l, r = L_R[j]
                if l <= i + 1 < r:
                    answers[j] += 1
    return answers


N, Q = map(int, input().split())
S = input()
L_R = [tuple(map(int, input().split())) for _ in range(Q)]
for ans in solve(N, Q, S, L_R):
    print(ans)

### FIXED CODE ###

def solve(N, Q, S, L_R):
    memo = [None] * N
    cumsum = 0
    for i in range(len(S) - 1):
        memo[i] = cumsum
        if S[i] == "A" and S[i + 1] == "C":
            cumsum += 1
    memo[N - 1] = cumsum
    for l, r in L_R:
        print(memo[r - 1] - memo[l - 1])


N, Q = map(int, input().split())
S = input()
L_R = [tuple(map(int, input().split())) for _ in range(Q)]
solve(N, Q, S, L_R)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

sys.setrecursionlimit(10**6)
INF = 10**12
m = 10**9 + 7

N, M, R = map(int, input().split())
r = list(map(int, input().split()))
    
adj = [[INF]*N for _ in range(N)]
perm_list = []

def make_permutation(l,R):
    if R == 0:
        perm_list.append(l)
    else:
        for a in r:
            if a not in l:
                make_permutation(l+[a],R-1)

def main():
    for _ in range(M):
        A, B, C = map(int, input().split())
        adj[A-1][B-1] = C
        adj[B-1][A-1] = C
    
    # 方針: Warshall-Floydで各頂点間の最短距離を求めてからrの順列全探索
    for i in range(N):
        for j in range(N):
            for k in range(N):
                adj[i][j] = min(adj[i][j], adj[i][k]+adj[k][j])

    make_permutation([],R)
    ans = INF
    for ps in perm_list:
        tmp = 0
        for i in range(R-1):
            tmp += adj[ps[i]-1][ps[i+1]-1]
        ans = min(ans,tmp)
    print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

sys.setrecursionlimit(10**6)
INF = 10**12
m = 10**9 + 7

N, M, R = map(int, input().split())
r = list(map(int, input().split()))
    
adj = [[INF]*N for _ in range(N)]
perm_list = []

def make_permutation(l,R):
    if R == 0:
        perm_list.append(l)
    else:
        for a in r:
            if a not in l:
                make_permutation(l+[a],R-1)

def main():
    for _ in range(M):
        A, B, C = map(int, input().split())
        adj[A-1][B-1] = C
        adj[B-1][A-1] = C
    
    # 方針: Warshall-Floydで各頂点間の最短距離を求めてからrの順列全探索
    for k in range(N):
        for i in range(N):
            for j in range(N):
                adj[i][j] = min(adj[i][j], adj[i][k]+adj[k][j])

    make_permutation([],R)
    ans = INF
    for ps in perm_list:
        tmp = 0
        for i in range(R-1):
            tmp += adj[ps[i]-1][ps[i+1]-1]
        ans = min(ans,tmp)
    print(ans)
    # print(perm_list)

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

import operator
from functools import reduce
from scipy.misc import comb


def ncr(n, r):
    return comb(n, r, exact=True)


def step2patterns(num_step):
    pats = 0
    for j in range(0, (num_step//2)+1):
        pats += ncr(num_step-j, j)
    return pats


# def step2patterns(num_step, step_dict):
#     try:
#         return step_dict[num_step]
#     except KeyError:
#         ret = calc_step2patterns(num_step)
#         step_dict[num_step] = ret
#         return ret


num_stair, num_wet = map(int, input().split(' '))

last_wet = -1
num_pattern = 1
d = {}

for i in range(0, num_wet):
    wet = int(input())
    dry_step = wet - last_wet - 1
    last_wet = wet

    if dry_step <= 0:
        print('0')
        exit(0)

    elif dry_step == 1 or dry_step == 2:
        continue

    else:
        num_pattern *= step2patterns(dry_step - 1)

    num_pattern %= 1000000007

# last step
dry_step = num_stair - last_wet

num_pattern *= step2patterns(dry_step - 1)

print(num_pattern % 1000000007)
exit(0)


### FIXED CODE ###

def exec_ncr(max_step, record_dict):
    for i in range(2, max_step+1):
        record_dict[i] = record_dict[i-1] + record_dict[i-2]


num_stair, num_wet = map(int, input().split(' '))

last_wet = -1
num_pattern = 1
d = {0: 1, 1: 1}
exec_ncr(num_stair, d)

for i in range(0, num_wet):
    wet = int(input())
    dry_step = wet - last_wet - 1
    last_wet = wet

    if dry_step <= 0:
        print('0')
        exit(0)

    elif dry_step == 1 or dry_step == 2:
        continue

    else:
        num_pattern *= d[dry_step-1]

# last step
dry_step = num_stair - last_wet

num_pattern *= d[dry_step-1]

print(num_pattern % 1000000007)
exit(0)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
ma = max(A)
xma = 1
for i in range(20):
    xma = xma  * 2
    if xma >= ma:
        break
ans = 0
a = 0
for l in range(N):
    a = A[l]
    x = A[l]
    for j in range(l+1,N):
        a += A[j]
        x = x ^ A[j]
        if a == x:
            ans += 1
        elif a >= xma:
            break
print(ans + N)



### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = 0
num = 0
a = 0
x = 0
k = 0
for l in range(N):
    for j in range(k,N):
        a += A[j]
        x =  x ^ A[j]
        if a  != x:
            ans += j - l
            k = j
            x = x ^ A[l] ^ A[j]
            a = a - A[l] - A[j]
            break
        elif j == N-1:
            ans += N-l
            k = j
            x = x ^ A[l] ^ A[j]
            a = a - A[l] - A[j]
print(ans )
### BUGGY CODE ###

[n,m] = [int(i) for i in input().split()]
a = []
for i in range(m):
    a.append(int(input()))
dp = [0] * (n+1)
dp[0] = 1
if n > 1:
    for i in range(1,n+1):
        if i not in a:
            if i == 1:
                dp[i] = 1
            else:
                dp[i] = dp[i-2]+dp[i-1]
        else:
            dp[i] = 0
    print((dp[n])%(10 ** 9 + 7))
else:
    if 1 in a:
        print(0)
    else:
        print(1)


### FIXED CODE ###

[n,m] = [int(i) for i in input().split()]
a = []
for i in range(m):
    a.append(int(input()))
ok = [0] * (n+1)
for i in range(m):
    ok[a[i]] = 1
dp = [0] * (n+1)
dp[0] = 1
if n > 1:
    for i in range(1,n+1):
        if ok[i] != 1:
            if i == 1:
                dp[i] = 1
            else:
                dp[i] = (dp[i-2]+dp[i-1])%(10**9+7)
        else:
            dp[i] = 0
    print((dp[n])%(10 ** 9 + 7))
else:
    if 1 in a:
        print(0)
    else:
        print(1)
### BUGGY CODE ###

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

import re
pos = [m.end() for m in re.finditer(r'AC', s)]

def cnt(at):
    ret=0
    for p in pos:
        if p>at:
            break
        ret+=1
    return ret

ans=[]    
for _ in range(Q):
    l,r = list(map(int, input().split()))
    ans.append(cnt(r)-cnt(l))

print(*ans, sep='\n')

### FIXED CODE ###

import re
import itertools

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

pos = [m.end() for m in re.finditer(r'AC', s)]

dp = [0] * (N+1)
for p in pos:
    dp[p] = 1
dp = list(itertools.accumulate(dp))

ans=[]    
for _ in range(Q):
    l,r = list(map(int, input().split()))
    ans.append(dp[r]-dp[l])

print(*ans, sep='\n')
### BUGGY CODE ###

X = input()
X_ = ''
while X!=X_:
    X_ = X
    X = X.replace('ST', '')
print(len(X))

### FIXED CODE ###

from collections import deque
X = input()
que = deque()
for x in X:
    if x=='S':
        que.append('S')
    elif x=='T' and (not que or que[-1]=='T'):
        que.append('T')
    elif x=='T' and que[-1]=='S':
        _ = que.pop()
print(len(que))
### BUGGY CODE ###

a,b,c,d = map(int,input().split())

f = 1
while True:
    if f:
        c -= b
        f = 0
        if c == 0:
            print("Yes")
            break
    else:
        a -= d
        f = 1
        if a == 0:
            print("No")
            break
    


### FIXED CODE ###

import math
a,b,c,d = map(int,input().split())

ans_1 = math.ceil(c / b)
ans_2 = math.ceil(a / d)

#print(ans_1,ans_2)
if ans_1 > ans_2:
    print("No")
else:
    print("Yes")
### BUGGY CODE ###

h, w = map(int, input().split())
rb = [['#'] * (w + 2)]
a = rb + [list('#' + input() + '#') for _ in range(h)] + rb
p = [(i, j) for i in range(1, h + 1) for j in range(1, w + 1) if a[i][j] == '#']
d = (-1, 0), (1, 0), (0, -1), (0, 1)
r = -1
while p:
    r += 1
    s = []
    for i, j in p:
        for di, dj in d:
            di += i
            dj += j
            if a[di][dj] == '.':
                a[di][dj] = '#'
                s.append((di, dj))
    p = s
print(r)


### FIXED CODE ###

h, w = map(int, input().split())
a = [['#'] * (w + 2)] + [['#'] + list(input()) + ['#']
                          for _ in range(h)] + [['#'] * (w + 2)]
p = [(i, j) for i in range(1, h + 1) for j in range(1, w + 1) if a[i][j] == '#']
d = (-1, 0), (1, 0), (0, -1), (0, 1)
r = -1
while p:
    r += 1
    s = []
    for i, j in p:
        for di, dj in d:
            di += i
            dj += j
            if a[di][dj] == '.':
                a[di][dj] = '#'
                s.append((di, dj))
    p = s
print(r)