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

n, q = map(int, input().split())
s = input()
# l = list()
# r = list()
s_list = list()
for _ in range(q):
    l_i, r_i = map(int, input().split())
    # l.append(l_i)
    # r.append(r_i)
    s_list.append(s[l_i-1:r_i])

for i in s_list:
    print(i.count('AC'))

### FIXED CODE ###

def main():
    # n, q = map(int, input().split())
    # s = input()
    # # l = list()
    # # r = list()
    # s_list = list()
    # # s_tuple = tuple()
    # for _ in range(q):
    #     l_i, r_i = map(int, input().split())
    #     # l.append(l_i)
    #     # r.append(r_i)
    #     s_list.append(s[l_i - 1:r_i])
    #     # s_tuple = s_tuple + tuple(s[l_i - 1:r_i])
    # 
    # s_tuple = tuple(s_list)
    # 
    # for i in s_tuple:
    #     print(i.count('AC'))
    N, Q = map(int, input().split())
    S = input()
    cnt = [0] * (N + 1)
    for i in range(N):
        cnt[i + 1] = cnt[i] + (1 if S[i:i+2] == 'AC' else 0)
    for i in range(Q):
        l, r = map(int, input().split())
        print(cnt[r - 1] - cnt[l - 1])


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

n=int(input())
 
X=list(map(int,input().split()))
sort_X=sorted(X)
for i in range(n):
    if sort_X.index(X[i])<int(n/2):
        print(sort_X[int(n/2)])
    else:
        print(sort_X[int(n/2)-1])

### FIXED CODE ###

n=int(input())

X=list(map(int,input().split()))
sort_X=sorted(X)
for i in range(n):
    if X[i]<sort_X[int(n/2)]:
        print(sort_X[int(n/2)])
    else:
        print(sort_X[int(n/2)-1])
### BUGGY CODE ###

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)

    return len(divisors)

def main():
    n = int(input())
    s = 0
    
    for i in range(1,n+1):
        s += i * make_divisors(i)
    print(s)

main()

### FIXED CODE ###

def main():
    n = int(input())
    ans = 0
    for i in range(1,n+1):
        #print(range(i,n+1,i),sum(range(i,n+1,i)))
        ans += sum(range(i,n+1,i))

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

n,q=map(int,input().split())
s=input()
e=[]
for j in range(n-1):
    if s[j:j+2]=="AC":
        e.append(1)
    else :
        e.append(0)

for i in range(q):
    l,r=map(int,input().split())
    ll=e[l-1:r-1]
    print(sum(ll))



### FIXED CODE ###

n,q=map(int,input().split())
s=input()
t=[0]*(n+1)
for i in range(n):
    t[i+1]=t[i]+(1 if s[i:i+2]=="AC" else 0)

for i in range(q):
    l,r=map(int,input().split())
    print(t[r-1]-t[l-1])
### BUGGY CODE ###

n = int(input())
L = sum([list(map(int, input().split())) for i in range(n)], [])
next = 1
count = 0
while True:
  if next == 2:
    print(count)
    exit()
  elif count > n:
    print(-1)
    exit()    
  next = L[next-1]
  count += 1

### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
cur = 1
cnt = 0
while True:
    if cur == 2:
        print(cnt)
        exit()
    elif cnt > n:
        print(-1)
        exit()
    else:
        cur = a[cur - 1]
        cnt += 1
### BUGGY CODE ###

import sys
from collections import defaultdict
from collections import deque
import numpy as np

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)


N, M, S, T = map(int, input().split())
PATH = [[] for _ in range(N+1)]


for _ in range(M):
    u, v, a, b = map(int, input().split())
    PATH[u].append((v, a, b))
    PATH[v].append((u, a, b))

INF = 10 ** 15

da = [INF] * (N+1)
db = [INF] * (N+1)

usedA = [False] * (N+1)
usedB = [False] * (N+1)

da[S] = 0
for _ in range(N+2):
    d = -1
    v = -1
    for i in range(1, N+1):
        if not usedA[i]:
            if d == -1 or da[i] < d:
                v = i
                d = da[i]

    if d == -1:
        break

    usedA[v] = True

    for u, a, _ in PATH[v]:
        da[u] = min(da[u], da[v]+a)

db[T] = 0
for _ in range(N+2):
    d = -1
    v = -1
    for i in range(1, N+1):
        if not usedB[i]:
            if d == -1 or db[i] < d:
                v = i
                d = db[i]

    if d == -1:
        break

    usedB[v] = True

    for u, _, b in PATH[v]:
        db[u] = min(db[u], db[v]+b)

dist = [(i, da[i]+db[i]) for i in range(1, N+1)]
dist.sort(key=lambda x: x[1])
idx = 0

for i in range(N):
    while(dist[idx][0] <= i):
        idx += 1

    print(10**15 - dist[idx][1])


### FIXED CODE ###

import sys
from collections import defaultdict
from collections import deque
import numpy as np
import heapq
from heapq import heappop, heappush

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)


N, M, S, T = map(int, input().split())
PATH = [[] for _ in range(N+1)]


for _ in range(M):
    u, v, a, b = map(int, input().split())
    PATH[u].append((v, a, b))
    PATH[v].append((u, a, b))


def dijkstra(s, mode):
    INF = 10 ** 15
    dist = [INF] * (N+1)
    dist[s] = 0
    que = [(0, s)]

    while que:
        d, v = heappop(que)
        if dist[v] < d:
            continue

        for u, *a in PATH[v]:
            dv = d + a[mode]

            if dv < dist[u]:
                dist[u] = dv
                heappush(que, (dv, u))

    return dist


da = dijkstra(S, 0)
db = dijkstra(T, 1)

score = [10**15 - (da[i]+db[i]) for i in range(1, N+1)]

ans = [10**15] * N
ans[-1] = score[-1]

for i in range(N-2, -1, -1):
    ans[i] = max(ans[i+1], score[i])

for i in range(N):
    print(ans[i])
### BUGGY CODE ###

#! /usr/bin/env python3
# -*- coding: utf-8 -*-
import collections
N,M = [int(x) for x in input().split()]
ans =[0]*N
for i in range (M):
    L,R = [int(x) for x in input().split()]
    ans[L-1:R] = map(lambda x: x+1, ans[L-1:R] )

count = 0
for i in ans:
    if i == M :
        count+= 1

       

print(count)







### FIXED CODE ###

#! /usr/bin/env python3
# -*- coding: utf-8 -*-
N,M = [int(x) for x in input().split()]
Llist =[]
Rlist =[]
for i in range (M):
    L,R = [int(x) for x in input().split()]
    Llist.append(L)
    Rlist.append(R)
 
lmax = max(Llist)
Rmax = min(Rlist)

if lmax > Rmax:
    print(0)
else:
    print(Rmax-lmax+1)
### BUGGY CODE ###

s = input()
t = input()
S = len(s)
T = len(t)
dp = [[[0, ""] for j in range(T+1)] for _ in range(S+1)]
for i in range(S):
    for j in range(T):
        if s[i] == t[j]:
            dp[i+1][j+1][0] = dp[i][j][0]+1
            dp[i+1][j+1][1] = dp[i][j][1]+s[i]
        else:
            if dp[i+1][j][0] >= dp[i][j+1][0]:
                dp[i+1][j+1][0] = dp[i+1][j][0]
                dp[i+1][j+1][1] = dp[i+1][j][1]
            else:
                dp[i+1][j+1][0] = dp[i][j+1][0]
                dp[i+1][j+1][1] = dp[i][j+1][1]
print(dp[S][T][1])


### FIXED CODE ###

def main():
    s = input()
    t = input()
    S = len(s)
    T = len(t)
    dp = [[0 for j in range(T+1)] for _ in range(S+1)]
    for i in range(S):
        for j in range(T):
            if s[i] == t[j]:
                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][j+1])

    res = ""
    i = S
    j = T
    while i > 0 and j > 0:
        if dp[i][j] == dp[i][j-1]:
            j -= 1
        elif dp[i][j] == dp[i-1][j]:
            i -= 1
        else:
            res = s[i-1]+res
            i -= 1
            j -= 1
    print(res)


main()
### BUGGY CODE ###

a,b,n=map(int,input().split())
ans=0
for x in range(n+1):
  test_ans=int(a*x/b)-a*int(x/b)
  if test_ans>ans:
    ans=test_ans
print(ans)

### FIXED CODE ###

# floor(a/b)=(a-(a%b))/b
# ax%b=a(x%b)%b
a,b,n=map(int,input().split())
if(n>=b-1):
    print(a*(b-1)//b)
else:
    print(a*n//b)
### BUGGY CODE ###

from heapq import heapify, heappush, heappop

N, M = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(N)]
AB.sort()
queue = []
heapify(queue)
ans = 0

for i in range(1, M+1):
    while len(AB) > 0:
        if AB[0][0] <= i:
            heappush(queue, -AB.pop(0)[1])
        else:
            break

    if queue:
        ans += -heappop(queue)

print(ans)


### FIXED CODE ###

from heapq import heappush, heappop

N, M = map(int, input().split())
salary = [[] for i in range(M+1)]
for i in range(N):
    A, B = map(int, input().split())
    if A <= M:
        salary[A].append(B)
queue = []
ans = 0

for i in range(1, M+1):
    for s in salary[i]:
        heappush(queue, -s)
    if queue:
        ans += -heappop(queue)

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

from pprint import pprint

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

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


dp_table = [[-float("inf")]*(n+1) for _ in range(w+1)]

dp_table[0][0] = 0

for i in range(1,n+1):
    for before_w in range(w):
        #i番目の品物を選ばない場合
        dp_table[before_w][i] = max(dp_table[before_w][i], dp_table[before_w][i-1])
        #i番目の品物を選ぶ場合
        if wv[i-1][0]+before_w <= w:
            dp_table[wv[i-1][0]+before_w][i] = max(dp_table[wv[i-1][0]+before_w][i], dp_table[before_w][i-1] + wv[i-1][1])
        else:
            continue

result = 0

for y in range(w+1):
    result = max(result,dp_table[y][-1])

print(result)

### FIXED CODE ###

from pprint import pprint

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

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


dp_table = [[-float("inf")]*(w+1) for _ in range(n+1)]

dp_table[0] = [0]*(w+1)

#sum_w以下の重さの時のvalueの合計の最大を求めていく。

for i in range(1,n+1):
    for sum_w in range(w+1):
        #i番目の品物を選ばない場合
        dp_table[i][sum_w] = max(dp_table[i][sum_w], dp_table[i-1][sum_w])
        #i番目の品物を選ぶ場合
        if sum_w >= wv[i-1][0]:
            dp_table[i][sum_w] = max(dp_table[i][sum_w], dp_table[i-1][sum_w-wv[i-1][0]] + wv[i-1][1])
        else:
            continue


result = dp_table[n][w]
print(result)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
count = int(input())
num = []
num = input().split()

total = 1
for i in range(count):
    total = int(num[i])*total
    
if total > 10**18:
    total = -1
    
print(total)

### FIXED CODE ###

# coding: utf-8
# Your code here!

count = int(input())
num = []
num = input().split()

hantei = 0
for i in range(count):
    if int(num[i]) == 0:
        hantei = 1
        total = 0
    else:
        continue
      #print("z")
      
if hantei == 0:
    total = 1
    for i in range(count):
        total = int(num[i])*total
        if total > 10**18:
            total = -1
            break
    
print(total)
### BUGGY CODE ###

n, c = map(int, input().split())
D = [tuple(map(int, input().split())) for _ in range(c)]
C = [tuple(map(lambda x:int(x)-1, input().split())) for _ in range(n)]

grid = [[(i+j)% 3 for i in range(n)] for j in range(n)]

mind = 1000*500*500
from itertools import permutations
for p in permutations(list(range(c)), 3):
    sumd = 0
    for i in range(n):
        for j in range(n):
            c_to = p[grid[i][j]]
            c_from = C[i][j]
            sumd += D[c_from][c_to]
        if sumd > mind:
            break
    else:
        mind = sumd

print(mind)


### FIXED CODE ###

n, c = map(int, input().split())
D = [tuple(map(int, input().split())) for _ in range(c)]
C = [tuple(map(lambda x:int(x)-1, input().split())) for _ in range(n)]

# 全ての色について違和感を記録
dst = [[0, 0, 0] for _ in range(c)]
for ci in range(c):
    for i in range(n):
        for j in range(n):
            c_from = C[i][j]
            dst[ci][(i+j)%3] += D[c_from][ci]

from itertools import permutations
d = 1000*500*500
for p0, p1, p2 in permutations(list(range(c)), 3):
    d = min(d, dst[p0][0] + dst[p1][1] + dst[p2][2])
print(d)
### BUGGY CODE ###

import sys
tmp=sys.stdin.readline().rstrip()
def main():
   cnt=[0]*2019
   cnt[0]+=1
   for i in reversed(range(len(tmp))):
      cnt[int(tmp[i:])%2019] += 1
   import collections
   cnt=collections.Counter(cnt).items()
   ans=0
   for i,j in cnt:
      if i > 1:
         ans+=i*(i-1)//2*j
   print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
tmp=sys.stdin.readline().rstrip()
def main():
   ans=0
   cnt=[0]*2019
   cnt[0]+=1
   t=0
   d=1
   for i in reversed(tmp):
      t=(t+int(i)*d)%2019
      cnt[t]+=1
      d=d*10%2019
   for i in cnt:
      ans+=i*(i-1)//2
   print(ans)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

s = str(input())

ans = 0
for i in range(len(s)-1):
  if s[i:i+2] == 'BC':
    cnt = 0
    for j in range(i):
      if s[i-1-j] == 'A':
        cnt += 1
      else:
        break
    s = s[:i-cnt] + 'BC' + 'A'*cnt + s[i+2:]
    ans += cnt
print(ans)

### FIXED CODE ###

s = str(input())

ans, cnt, i = 0, 0, 0
while i < len(s)-1:
  if s[i] == 'A':
    cnt += 1
    i += 1
  else:
    if s[i:i+2] == 'BC':
      ans += cnt
      i += 2
    else:
      cnt = 0
      i += 1
print(ans)
### BUGGY CODE ###

from collections import Counter

s = list(map(int, list(input())))[::-1]
N = len(s)
cusum = [0]*(N+1)
cusum[0] = s[0] % 2019
power = 1
for i in range(1, N):
    power = 10**i % 2019
    cusum[i] = (cusum[i-1] + power * s[i]) % 2019
counter = Counter(cusum)
print(sum(x*(x-1)//2 for x in counter.values()))


### FIXED CODE ###

from collections import Counter

s = list(map(int, list(input())))[::-1]
N = len(s)
cusum = [0]*(N+1)
cusum[0] = s[0] % 2019
for i in range(1, N):
    power = pow(10, i, 2019)
    cusum[i] = (cusum[i-1] + power * s[i]) % 2019
counter = Counter(cusum)
print(sum(x*(x-1)//2 for x in counter.values()))
### BUGGY CODE ###

from sys import stdin
from statistics import median_low,median_high
from math import factorial

n = int(stdin.readline().rstrip())
li = list(map(int,stdin.readline().rstrip().split()))
li.sort()
a = li.pop()
b1 = median_low(li)
b2 = median_high(li)

def combinations_count(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))

if combinations_count(a,b1) >= combinations_count(a,b2):
    print(a,b1)
else:
    print(a,b2)

### FIXED CODE ###

from sys import stdin
import bisect

n = int(stdin.readline().rstrip())
li = list(map(int,stdin.readline().rstrip().split()))

li.sort()

a = li.pop()
if len(li) == 1:
    print(a,li[0])
else:
    bi = bisect.bisect_left(li,a/2)
    b = li[bi]
    if bi != 0:
        c = li[bi-1]
        if abs(a/2-c) <= abs(a/2-b):
            print(a,c)
        else:
            print(a,b)
    else:
        print(a,b)
### BUGGY CODE ###

from heapq import heappush,heappop
import numpy as np
n,m,s,t=map(int,input().split())
a=[[]for i in range (n+1)]
b=[[]for i in range(n+1)]
for i in range(m):
    p,q,r,g=map(int,input().split())
    a[p].append((q,r))
    a[q].append((p,r))
    b[p].append((q,g))
    b[q].append((p,g))
def f(x,r):
    p=[float("INF")for i in range(n+1)]
    p[x],q=0,[[0,x]]
    while q:
        y,z=heappop(q)
        for i,j in r[z]:
            if p[i]>y+j:
                p[i]=y+j
                heappush(q,[p[i],i])
    return p[1:]
s1,t1=f(s,a),f(t,b)
p=[]
for i in range(n):
    p.append((s1[i]+t1[i],i+1))
p,e=sorted(p),0
for i in range(n):
    while p[e][1]<=i: e+=1
    print(10**15-p[e][0])

### FIXED CODE ###

from heapq import heappush,heappop
n,m,s,t=map(int,input().split())
a,b=[[]for i in range (n+1)],[[]for i in range(n+1)]
for i in range(m):
    p,q,r,g=(int(i) for i in input().split())
    a[p].append((q,r))
    a[q].append((p,r))
    b[p].append((q,g))
    b[q].append((p,g))
def f(x,r):
    p=[float("inf")for i in range(n+1)]
    p[x],q=0,[[0,x]]
    while q:
        y,z=heappop(q)
        for i,j in r[z]:
            if p[i]>y+j:
                p[i]=y+j
                heappush(q,[p[i],i])
    return p
s1,t1,p=f(s,a),f(t,b),[]
for i in range(1,n+1):
    p.append((s1[i]+t1[i],i))
p,e=sorted(p),0
for i in range(n):
    while p[e][1]<=i: e+=1
    print(10**15-p[e][0])
### BUGGY CODE ###

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

N = int(input())
g = 0
for n in range(N):
    A = factorization(n+1)
    f = 1
    for row in A:
        f *= row[1]+1
    g += (n+1) * f

print(g-1)

### FIXED CODE ###

n = int(input())
ans = 0
for i in range(1,n+1):
  k = n//i
  ans += i*(k*(k+1))//2
print(ans)
### BUGGY CODE ###

div=10**9+7
def modinv(a, m=div):
    b = m
    u = 1
    v = 0
    while b:
        t = a//b
        a -= t*b 
        a = a^b
        b = a^b
        a = a^b
        u -= t*v
        u = u^v
        v = u^v
        u = u^v
    u %= m 
    if u < 0: u += m
    return u

N,A,B,C=list(map(int,input().split()))
fact=[1]*(2*N+1)
res = 0
invAB = modinv(A+B)
reveven = (modinv(100-C)*100) % div
memoA = [1]*(N+1)
memoB = [1]*(N+1)

for i in range(1, 2*N + 1): fact[i] = fact[i-1]*i % div
# print(fact)
def ncr(n, r): return fact[n]*modinv(fact[r]*fact[n-r]%div)%div

for i in range(1, N+1): 
    memoA[i] = (memoA[i-1]*A*invAB) % div
    memoB[i] = (memoB[i-1]*B*invAB) % div

for i in range(N, 2*N):
    kitai1 = (
        ((ncr(i-1, N-1)*memoA[N]) % div)*memoB[i-N] + 
        ((ncr(i-1, N-1)*memoB[N]) % div)*memoA[i-N]) % div
    res += kitai1*reveven*i % div

print(res % div)


### FIXED CODE ###

div=10**9+7
def modinv(a, m=div):
    b = m
    u = 1
    v = 0
    while b:
        t = a//b
        a -= t*b 
        a = a^b
        b = a^b
        a = a^b
        u -= t*v
        u = u^v
        v = u^v
        u = u^v
    u %= m 
    if u < 0: u += m
    return u

N,A,B,C=list(map(int,input().split()))
ncr_memo = {}

def ncr(n, r):
    if r == 0: return 1
    if n in ncr_memo:
        return ncr_memo[n]
    if n-1 in ncr_memo:
        ncr_memo[n] = (ncr_memo[n-1]*n*modinv(n-(N-1))) % div
        return ncr_memo[n]
    orn = n

    res = 1
    for i in range(1, r+1):
        res = res*n*modinv(i, div) % div
        n = n-1
    res %= div
    ncr_memo[orn] = res
    return res

for i in range(N, 2*N):
    ncr(i-1, N-1)

res = 0
inv100 = modinv(A+B)

reveven = (modinv(100-C)*100) % div
memoA = [1]*(N+1)
memoB = [1]*(N+1)

for i in range(1, N+1): memoA[i] = (memoA[i-1]*A*inv100) % div
for i in range(1, N+1): memoB[i] = (memoB[i-1]*B*inv100) % div

for i in range(N, 2*N):
    kitai1 = (
        (((ncr(i-1, N-1)*memoA[N]))*memoB[i-N]) + 
        (((ncr(i-1, N-1)*memoB[N]))*memoA[i-N])) % div
    res += kitai1*reveven*i % div

print(res  % div)
### BUGGY CODE ###

hoge = int(input())
n = list(map(int,input().split()))
ans = "YES"
count = 0

for i in n :
    
    for j in n :
        if i == j :
            count += 1
    
    if count >= 2 :
        ans = "NO"
    
    count = 0

print(ans)

### FIXED CODE ###

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

ans = "YES" if len(n) == len(set(n)) else "NO"
print(ans)
### BUGGY CODE ###

from bisect import bisect_left, bisect_right
from operator import itemgetter


def main():
    N, Q = map(int, input().split())
    constructions = [None] * N
    for i in range(N):
        S, T, X = map(int, input().split())
        constructions[i] = (S, T, X)
    D = [(int(input()), i) for i in range(Q)]
    D.sort(key=itemgetter(0))
    ans = [-1] * Q
    for S, T, X in constructions:
        l = bisect_left(D, (S-X, -1))
        r = bisect_right(D, (T-X, -1))
        for i in range(l, r):
            idx = D[i][1]
            if ans[idx] == -1 or ans[idx] > X:
                ans[idx] = X
    for a in ans:
        print(a)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from bisect import bisect_left, bisect_right
from operator import itemgetter
import sys
input = sys.stdin.readline


def main():
    N, Q = map(int, input().split())
    constructions = [None] * N
    for i in range(N):
        S, T, X = map(int, input().split())
        constructions[i] = (S, T, X)
    constructions.sort(key=itemgetter(2))
    D = [int(input()) for _ in range(Q)]
    ans = [-1] * Q
    nxt = list(range(1, Q+1))
    for S, T, X in constructions:
        l = bisect_left(D, S-X)
        r = bisect_right(D, T-X-1)
        idx = l
        while idx < r:
            if ans[idx] == -1:
                ans[idx] = X
            nidx = nxt[idx]
            nxt[idx] = max(nxt[idx], r)
            idx = nidx
    for a in ans:
        print(a)


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

N=int(input())
s=input()
PIN=[]
for i in range(N-2):
    for j in range(i+1,N-1):
        for k in range(j+1,N):
            PIN.append(s[i]+s[j]+s[k])
print(len(set(PIN)))

### FIXED CODE ###

N=int(input())
s=input()
PIN=[]
firs=[]
sec=[]
thir=[]
for i in range(N-2):
    if s[i] not in firs:
        firs.append(s[i])
        for j in range(i+1,N-1):
            if s[j] not in sec:
                sec.append(s[j])
                for k in range(j+1,N):
                    if s[k] not in thir:
                        thir.append(s[k])
                        PIN.append(s[i]+s[j]+s[k])
                thir=[]
        sec=[]       
print(len(PIN))
### BUGGY CODE ###

n, m = map(int, input().split())
a = []
for _ in range(m):
  a.append(int(input()))
  
dp = [0]*(n+1)
dp[0] = 1

for i in range(1, n+1):
  if i in a:
    dp[i] = 0
    continue
  dp[i] = dp[i-1] + dp[i-2]

mod = 1000000007
print(dp[-1]%mod)

### FIXED CODE ###

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

safe = [True] * (n + 1)
for _ in range(m):
  safe[int(input())] = False
dp = [0] * (n + 1)

dp[0] = 1
if safe[1]:
  dp[1] = 1

for i in range(2, n + 1):
  if safe[i - 1]:
    dp[i] += dp[i - 1]
  if safe[i - 2]:
    dp[i] += dp[i - 2]
  dp[i] %= 1000000007
 
print(dp.pop())
### BUGGY CODE ###

N=int(input())

power=1
i=1
while i<=N: 
    power=power*i
    i+=1

ans=power%(1000000000+7)
print(ans)

### FIXED CODE ###

import math
N=int(input())

power=math.factorial(N)

ans=power%(1000000000+7)
print(ans)
### BUGGY CODE ###

N, T = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]

dp = [-1] * (T + 3000)
dp[0] = 0
for a, b in sorted(AB):
    for j in range(T - 1, -1, -1):
        if dp[j] == -1:
            continue
        t = dp[j] + b
        if dp[j + a] < t:
            dp[j + a] = t
print(max(dp))


### FIXED CODE ###

def main():
    N, T = map(int, input().split())
    AB = [list(map(int, input().split())) for _ in range(N)]

    dp = [-1] * (T + 3000)
    dp[0] = 0
    for a, b in sorted(AB):
        for j in range(T - 1, -1, -1):
            if dp[j] == -1:
                continue
            if dp[j] + b > dp[j + a]:
                dp[j + a] = dp[j] + b
    print(max(dp))


main()
### BUGGY CODE ###

n = int(input())
l = [list(input()) for i in range(n)]
l = ["".join(sorted(i)) for i in l]
l = [i for i in l if i != 1]
l.sort()
s = 0
for i in range(len(l)-1):
  for j in range(i+1,len(l)):
    if l[i] == l[j]:
      s += 1
print(s)


### FIXED CODE ###

import collections
n = int(input())
s = ["".join(sorted(input())) for i in range(n)]
l = collections.Counter(s)
ans = sum(i*(i-1)//2 for i in l.values())
print(ans)