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

def pre_cmb(N, MOD):
    FACT = [1, 1]  # 階乗
    INV = [0, 1]  # 各iの逆元
    FACTINV = [1, 1]  # 階乗の逆元

    for i in range(2, N + 1):
        FACT.append((FACT[-1] * i) % MOD)
        INV.append((-INV[MOD % i] * (MOD // i)) % MOD)
        FACTINV.append((FACTINV[-1] * INV[-1]) % MOD)
    PRELIST = FACT, FACTINV
    return PRELIST


def cmb(N, R, MOD, PRELIST):
    FACT, FACTINV = PRELIST
    if (R < 0) or (N < R):
        return 0
    R = min(R, N - R)
    return FACT[N] * FACTINV[R] * FACTINV[N-R] % MOD


n, m, k = map(int, input().split())
mod = 998244353

m_exp = [1]
for i in range(1, n):
    m_exp.append(m_exp[i - 1] * (m - 1))
prelist = pre_cmb(n, mod)

cnt = 0
for i in range(k + 1):
    cnt += (m * m_exp[n - i - 1] * cmb(n - 1, i, mod, prelist))

print(cnt % mod)



### FIXED CODE ###

def pre_cmb(N, MOD):
    FACT = [1, 1]  # 階乗
    INV = [0, 1]  # 各iの逆元
    FACTINV = [1, 1]  # 階乗の逆元

    for i in range(2, N + 1):
        FACT.append((FACT[-1] * i) % MOD)
        INV.append(pow(i,MOD-2,MOD))
        FACTINV.append((FACTINV[-1] * INV[-1]) % MOD)
    PRELIST = FACT, FACTINV
    return PRELIST


def cmb(N, R, MOD, PRELIST):
    FACT, FACTINV = PRELIST
    if (R < 0) or (N < R):
        return 0
    R = min(R, N - R)
    return FACT[N] * FACTINV[R] * FACTINV[N-R] % MOD


n, m, k = map(int, input().split())
mod = 998244353

prelist = pre_cmb(n, mod)

cnt = 0
for i in range(k + 1):
    cnt += (m * pow(m - 1, n - i - 1, mod) * cmb(n - 1, i, mod, prelist)) % mod

print(cnt % mod)
### BUGGY CODE ###

import bisect,collections,copy,heapq,itertools,math,string
import sys
def S(): return sys.stdin.readline().rstrip()
def M(): return map(int,sys.stdin.readline().rstrip().split())
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
N = I()
xx = 10**9+7
ans = 1
for i in range(1, N+1):
    ans = ans*i
print(ans%xx)

### FIXED CODE ###

import bisect,collections,copy,heapq,itertools,math,string
import sys
def S(): return sys.stdin.readline().rstrip()
def M(): return map(int,sys.stdin.readline().rstrip().split())
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
N = I()
print(math.factorial(N)%(10**9+7))
### BUGGY CODE ###

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

l = [0]*100000
r = [0]*100000

for i in range(0,m):
    l[i],r[i] = map(int,input().split())

count = 0
num = 0

for key in range(1,n + 1):#鍵の番号
    for i in range(0,m):#
        if(key >= l[i] and key <= r[i]):
            count += 1
    if(count == m):
        num += 1
    count = 0
        
print(num)
        

### FIXED CODE ###

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

l = [0]*m
r = [0]*m
b = [0]*(n + 2)

count = 0

for i in range(0,m):
    l[i],r[i] = map(int,input().split())

l_max = max(l)
r_min = min(r)

for i in range(1,n+1):
        if(i >= l_max and i <= r_min ):
                count += 1
        
print(count)
### 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)

    divisors.sort()
    return divisors

def main():
    n = int(input())
    ans = 0
    div = make_divisors(n)
    for i in div[::1]:
        var = n
        while not var%i:
            var = var // i
        if var%i == 1:
            ans += 1
    ans += len(make_divisors(n-1)) - 1
    print(ans)

main()


### FIXED 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)

    divisors.sort()
    return divisors

def main():
    n = int(input())
    ans = 0
    div = make_divisors(n)
    for i in div[1:]:
        var = n
        while not var%i:
            var = var // i
        if var%i == 1:
            ans += 1
    ans += len(make_divisors(n-1)) - 1
    print(ans)

main()
### BUGGY CODE ###

N,A=map(int, input().split())
x=list(map(int, input().split()))
W=sum(x)
dp=[[[0]*(W+1) for _ in range(N+1)] for _ in range(N+1)]
for j in range(N+1):
    dp[j][0][0]=1
for j in range(1,N+1):
    for k in range(1, N+1):
        for s in range(1, sum(x)+1):
            if s<x[j-1]:
                dp[j][k][s]=dp[j-1][k][s]
            else:
                dp[j][k][s]=dp[j-1][k][s]+dp[j-1][k-1][s-x[j-1]]

ans=0
for k in range(1,N+1):
    if k*A<=W:
        ans+=dp[N][k][k*A]
print(ans)


### FIXED CODE ###

import sys
from sys import stdin
input = stdin.readline

def solve(N, A, x):
    W=sum(x)
    dp=[[[0]*(W+1) for _ in range(N+1)] for _ in range(N+1)]
    for j in range(N+1):
        dp[j][0][0]=1
    for j in range(1,N+1):
        xj=x[j-1]
        for k in range(1, N+1):
            for s in range(1, W+1):
                if s<xj:
                    dp[j][k][s]=dp[j-1][k][s]
                else:
                    dp[j][k][s]=dp[j-1][k][s]+dp[j-1][k-1][s-xj]

    ans=0
    for k in range(1,N+1):
        if k*A<=W:
            ans+=dp[N][k][k*A]
        else:
            break
    return ans


def main(args):
    N,A=map(int, input().split())
    x=[int(x) for x in input().split()]
    ans=solve(N,A,x)
    print(ans)

if __name__ == '__main__':
    main(sys.argv[1:])
### BUGGY CODE ###

# 考えると、隣り合う列は結局 2*H 回ずることになり、
# それぞれの列間について最適な沈め順を見つけると、
# その順序関係を崩さないように全体の順番も構築できる（トポロジカルソートみたいに）ので、
# 各列間の最適解を求めて総和をとればいい

# TLE が厳しすぎる

def accumulate(idx1, idx2):
    res = [0]
    c = 0
    for i in range(H - max(idx1, idx2)):
        if C1[i+idx1] == C2[i+idx2]:
            c += 1
        res.append(c)
    return res

inf = 2 * 10**9
H, W = map(int, input().split())
C = [input() for _ in range(H)]
C_T = list(zip(*C))
C_T = ["".join(s) for s in C_T]
ans = 0
for C1, C2 in zip(C_T[:-1], C_T[1:]):
    # Z[i][j] := i 個ずれてて沈んでない方が j 個沈んでる状態の連結個数
    Z1 = []  # 左を押したとき（右が上にあるとき）
    Z2 = []  # 右を押したとき（左が上にあるとき）
    z1 = accumulate(0, 0);  z1.reverse()
    Z1.append(z1)
    Z2.append([])
    for j in range(1, H+1):
        z1 = accumulate(0, j);  z1.reverse();  Z1.append(z1)
        z2 = accumulate(j, 0);  z2.reverse();  Z2.append(z2)
    # dp[i][j] := 左を i 個、右を j 個沈めるまでの最小コスト  # 逆かも（どっちでもいい）
    dp = [[inf] * (H+2) for _ in range(H+2)]
    dp[0][0] = 0
    for j in range(H+1):
        for k in range(H+1):
            cost = dp[j][k] + (Z1[j-k][k] if j>=k else Z2[k-j][j])
            dp[j+1][k] = min(dp[j+1][k], cost)
            dp[j][k+1] = min(dp[j][k+1], cost)
    ans += dp[H][H]
print(ans)


### FIXED CODE ###

# 考えると、隣り合う列は結局 2*H 回ずることになり、
# それぞれの列間について最適な沈め順を見つけると、
# その順序関係を崩さないように全体の順番も構築できる（トポロジカルソートみたいに）ので、
# 各列間の最適解を求めて総和をとればいい

def accumulate_reverse(S1, S2):
    n = min(len(S1), len(S2))
    res = [0] * (n+1)
    c = 0
    for i in range(n):
        if S1[i] == S2[i]:
            c += 1
        res[n-i-1] = c
    return res

inf = 10**8
H, W = map(int, input().split())
C = [input() for _ in range(H)]
C_T = list(zip(*C))
C_T = ["".join(s) for s in C_T]
ans = 0
for C1, C2 in zip(C_T[:-1], C_T[1:]):
    # Z[i][j] := i 個ずれてて沈んでない方が j 個沈んでる状態の連結個数
    Z1 = []  # 左を押したとき（右が上にあるとき）
    Z2 = []  # 右を押したとき（左が上にあるとき）
    Z1.append(accumulate_reverse(C1, C2))
    for j in range(1, H+1):
        Z1.append(accumulate_reverse(C1, C2[j:]))
        Z2.append(accumulate_reverse(C1[j:], C2))
    Z1 += Z2[::-1]
    # dp[i][j] := 左を i 個、右を j 個沈めるまでの最小コスト  # 逆かも（どっちでもいい）
    dp = [[inf] * (H+2) for _ in range(H+2)]
    dp[0][0] = 0
    for j in range(H+1):
        for k in range(H+1):
            cost = dp[j][k] + Z1[j-k][min(j, k)]
            dp[j+1][k] = min(dp[j+1][k], cost)
            dp[j][k+1] = min(dp[j][k+1], cost)
    ans += dp[H][H]
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

N,M = map(int, input().split())
abc = [[int(j) for j in input().split()] for _ in range(M)]
con=[[] for _ in range (N+1)]
inf = float("inf")

allcost = [ -inf] * (N+1)
allcost[1] = 0

for i in range(M):
    a,b,c = abc[i]
    con[a].append(b)

for n in range(1, N):
    for edge in range(M):
        a,b,c = abc[edge]
        if allcost[b] < allcost[a] + c:
            allcost[b] = allcost[a] + c
def dfs(a):
  if N in con[a]:
    return True
  if len(con[a])==0:
    return False
  tmp=False 
  for ch in con[a]:
    if dfs(ch):
      tmp=True 
      break
  return tmp
for edge in range(M):
    a,b,c = abc[edge]
    if allcost[a] + c > allcost[b]:
        if dfs(a):
          print("inf")
          exit(0)

print(allcost[N])





### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

N,M = map(int, input().split())
abc = [[int(j) for j in input().split()] for _ in range(M)]
con=[[] for _ in range (N+1)]
inf = float("inf")

allcost = [ -inf] * (N+1)
allcost[1] = 0

for i in range(M):
    a,b,c = abc[i]
    con[a].append(b)

for n in range(1, N):
    for edge in range(M):
        a,b,c = abc[edge]
        if allcost[b] < allcost[a] + c:
            allcost[b] = allcost[a] + c
neg=[False]*(N+1)
for edge in range(M):
    a,b,c = abc[edge]
    if allcost[a] + c > allcost[b]:
        neg[b]=True
    if neg[a]==True:
      neg[b]=True
if neg[N]:
  print("inf")
  exit(0)
print(allcost[N])
### BUGGY CODE ###

N, K = list(map(int, input().split()))
H=[]
for i in range(N):
  H.append(int(input()))

H.sort()

ans=10**9
for i in range(N-K+1):
  ans = min(ans, max(H[i:i+K]) - min(H[i:i+K]))
  
print(ans)


### FIXED CODE ###

N, K = list(map(int, input().split()))
H=[]
for i in range(N):
  H.append(int(input()))

H.sort()

ans=10**9
for i in range(N-K+1):
  ans = min(ans, H[i+K-1] - H[i])
  
print(ans)
### BUGGY CODE ###

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

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)

def gcd_list(list):
    a = list.pop()
    for b in list:
        a = gcd(a,b)
    return a

ans = []
for i in range(n):
    B = A.copy()
    B.pop(i)
    ans.append(gcd_list(B))
print(max(ans))

### FIXED CODE ###

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

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)

ans = 0
L = [0]*(n)
R = [0]*(n+1)
for i in range(n-1):
    L[i+1] = gcd(L[i], A[i])
    R[i+1] = gcd(R[i], A[-i-1])
for l, r in zip(L[::-1],R):
    ans = max(ans, gcd(l, r))
print(ans)
### BUGGY CODE ###

N = int(input())
S = [input() for x in range(N)]

S_L = list(set(S))

# for i in S:
    # if i not in S_L:
        # S_L.append(i)
# print(S_L)

S_N = [0] * len(S_L)

for j in S:
    ind = S_L.index(j)
    S_N[ind] += 1
# print(S_N)

S_max = [] # 最大の数を持つ文字列を入れるリスト
S_N_max = max(S_N) # 最大の数を追加

for k in range(len(S_N)):
    if S_N[k] == S_N_max:
        S_max.append(S_L[k])

ans_L = sorted(S_max)

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

### FIXED CODE ###

from collections import Counter
N = int(input())
S = [input() for _ in range(N)]

S_cnt = Counter(S)
max_cnt = max(S_cnt.values())
# print(max_cnt)

names = [name for name, v in S_cnt.items() if v == max_cnt]
names.sort()

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

N, K = map(int, input().split())
p = list(map(int,input().split()))
ans = []
volatility = 0
a = 0

for i in range(len(p)):
    ex = (1 + p[i])/2
    p[i] = ex
    
for i in range(K, N+1):
    for j in range(i-K, i):
        volatility += p[j]
    
    ans.append(volatility)
    volatility = 0

a = max(ans)
print(a)

### FIXED CODE ###

N, K = map(int, input().split())
p = list(map(int,input().split()))
ans = 0
cum = [0]

for i in range(len(p)):
    ex = (1 + p[i])/2
    p[i] = ex
    
for i in  range(len(p)):
    cum.append(p[i] + cum[i])
    
for i in range(K, N+1):
    ans  = max(ans, cum[i] - cum[i-K])

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


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

blacks = []
for i in range(H):
    for j in range(W):
        if maze[i][j] == '#':
            blacks.append((i, j))
# print(blacks)

count = 0
while len(blacks) != 0:
    count += 1
#     print(blacks)
    nexts = []
    for x, y in blacks:
        for nx, ny in [(x-1, y), (x+1,y), (x,y-1),(x,y+1)]:
            if 0<=nx<H and 0<=ny<W and maze[nx][ny] == '.':
                maze[nx][ny] = '#'
                nexts.append((nx, ny))
#     print(maze)
    blacks = nexts
    
print(count-1)

### FIXED CODE ###


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

blacks = []
for i in range(H):
    for j in range(W):
        if maze[i][j] == '#':
            blacks.append((i, j))
# print(blacks)

count = 0
while len(blacks) != 0:
    count += 1
#     print(blacks)
    nexts = []
    for x, y in blacks:
        for nx, ny in [(x-1, y), (x+1,y), (x,y-1),(x,y+1)]:
            if 0<=nx<H and 0<=ny<W and maze[nx][ny] == '.':
                maze[nx][ny] = '#'
                nexts.append((nx, ny))
#     print(maze)
    blacks = nexts
    
print(count-1)
### BUGGY CODE ###

n = int(input())
out = 1
an = list(map(int,input().split()))

for a in an:
  out *= a
if out>10**18:
  out=-1
print(out)

### FIXED CODE ###

n = int(input())
out = 1
an = list(map(int,input().split()))
check = True
if 0 in an:
  print(0)
else:
  for a in an:
    out *= a
    if out>1000000000000000000:
      check = False
      break
  if check:
      print(out)
  else:
      print(-1)
### BUGGY CODE ###

def is_prime(q):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    return pow(2, q-1, q) == 1

n,m = map(int, input().split())
  
if m % n == 0:
  print(m//n)
  exit()
  
elif is_prime(m):
  print(1)
  
else:
  i = 1
  ans = 0
  while i  <= m // n:
    if (m - i * n) % i == 0:
      ans = i
    i += 1

  print(ans)

### FIXED CODE ###

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

ans = 1

for i in range(1, int(m ** 0.5)+1):
  if m % i == 0:
    if i >= n:
      ans = max(ans, m // i)
    elif m // i >= n:
      ans = max(ans, i)
      
      
print(ans)
### BUGGY CODE ###


def solve():
    i = L//2019
    ans = 0
    is_ok = False
    while L <= 2019*i <= R:
        i += 1
        is_ok = True
#    print(i)
    if is_ok:
        print(ans)
    else:
        ans = 2020
        for n in range(L,R):
            for m in range(n+1,R+1):
                ans = min(ans, (n*m)%2019)
        print(ans)

if __name__ == "__main__":
    L,R = list(map(int, input().split()))
    solve()


### FIXED CODE ###


def solve():
    i = (L//2019) + 1
    ans = 0
    if L <= 2019*i <= R:
        print(ans)
    else:
        ans = 2020
        for n in range(L,R):
            for m in range(n+1,R+1):
                ans = min(ans, (n*m)%2019)
            if ans == 0:
                break
        print(ans)

if __name__ == "__main__":
    L,R = list(map(int, input().split()))
    solve()
### BUGGY CODE ###

n,W = (int(i) for i in input().split())
weights = []
values = []
for j in range(n):
    wt, val = [int(i) for i in input().split()]
    weights.append(wt)
    values.append(val)

dp = [[0]*(W+1) for i in range(n+1)]

for i in range(1,n+1):
    wI = weights[i-1]
    vI = values[i-1]
    for j in range(1,W+1):
        if wI>j:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j],vI+dp[i-1][j-wI])

print(dp[-1][-1])


### FIXED CODE ###

import numpy as np

n,W = (int(i) for i in input().split())
weights = []
values = []
for j in range(n):
    wt, val = [int(i) for i in input().split()]
    weights.append(wt)
    values.append(val)

dp  = np.zeros(W+1)

for i in range(1,n+1):
    w = weights[i-1]
    v = values[i-1]
    dp[w:] = np.maximum(dp[w:],v+dp[:-w])

print(int(dp[-1]))
### BUGGY CODE ###

n,m = map(int,input().split())
abl = []
for _ in range(m):
   a,b = map(int,input().split())
   cl = list(map(int,input().split()))
   bit = 0
   for c in cl:
      bit += 2**(c-1)
   abl.append((a,bit))


ans = float("inf")
for i in range(2 ** m):
   bit = [0] * m
   for j in range(m):
       if ((i >> j) & 1):
           bit[j] = 1
   state = 0
   tmp = 0
   for j in range(m):
      if bit[j] == 1:
         state |= abl[j][1]
         tmp += abl[j][0]
   if state == (1 << n) - 1:
      ans = min(ans, tmp)

if ans == float("inf"):
   print(-1)
else:
   print(ans)
   

### FIXED CODE ###

n,m = map(int,input().split())
abl = []
for _ in range(m):
   a,b = map(int,input().split())
   cl = list(map(int,input().split()))
   bit = 0
   for c in cl:
      bit += 2**(c-1)
   abl.append((a,bit))

bitdp = [[float('inf') for i in range(1<<n)] for i in range(m+1)]
   
bitdp[0][0] = 0

for i in range(m):
   for j in range(1<<n):
      bitdp[i+1][j] = min(bitdp[i][j], bitdp[i+1][j])
      bitdp[i+1][j|abl[i][1]] = min(bitdp[i][j] + abl[i][0], bitdp[i][j|abl[i][1]], bitdp[i+1][j|abl[i][1]])

if bitdp[-1][(1<<n)-1] == float('inf'):
   print(-1)
else:
   print(bitdp[-1][(1<<n)-1])
### BUGGY CODE ###

n,p = map(int,input().split())
if n == 1:
    print(p)
    exit()
i =2
ans =1
while i**n <= p:
    if p%(i**n)==0:
        ans *= i
        p =p//(i**n)
    else:
        i += 1
print(ans)


### FIXED CODE ###

n,p = map(int,input().split())
if n == 1:
    print(p)
    exit()
if n >=40:
    print(1)
    exit()
i =2
ans =1
while i**n <= p:
    if p%(i**n)==0:
        ans *= i
        p =p//(i**n)

    else:
        i += 1
print(ans)
### BUGGY CODE ###

def resolve():
    s = input()
    query = int(input())
    r = 0
    for i in range(query):
        q = input()
        if q[0]=='2':
            _,f,c = q.split()
            if (int(f)+r)%2 == 0:
                s = s + c
            else:
                s = c + s
        else:
            r = (r+1)%2
    print(s if r==0 else s[::-1])
resolve()

### FIXED CODE ###

def resolve():
    s = input()
    query = int(input())
    r = 0
    left = ''
    for i in range(query):
        q = input()
        if q[0]=='2':
            _,f,c = q.split()
            if (int(f)+r)%2 == 0:
                s += c
            else:
                left += c
        else:
            r = (r+1)%2
    print(left[::-1]+s if r==0 else s[::-1]+left)
resolve()
### BUGGY CODE ###

n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = 0

a.insert(0, 0)
b.insert(0, 0)

for i in range(n+1):
    for j in range(m+1):
        if sum(a[0:i+1]) + sum(b[0:j+1]) <= k and i + j > ans:
            ans = i + j

print(ans)

### FIXED CODE ###

n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = 0
amax = 0
samax = 0

for i in range(n):
    if samax + a[i]<=k:
        amax += 1
        samax += a[i]
    else:
        break
        
book = amax
ans = book
samax = sum(a[0:amax])
sbmax = 0

for j in range(m):
    sbmax += b[j]
    while samax + sbmax > k and amax >= 1:
        amax -= 1
        samax = samax - a[amax]
        book -= 1
    if samax + sbmax <= k:
        book += 1
        if book > ans:
            ans = book
    else:
        break

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

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

S = S[::-1]
static = 0
strg = ""
for i,s in enumerate(S):
    if s != "?":
        s = int(s)
        static += s*(10**i)
        strg += "0"
    else:
        strg += "?"
mod = static%13

dp = [0]*13
dp[mod] = 1
for i,s in enumerate(strg):
    new = [0]*13
    if s == "?":
        for j in range(10):
            m = (j*(10**i))%13
            for k in range(13):
                new[k] += dp[k-m]
        for j in range(13):
            dp[j] = new[j]%MOD
print(dp[5]) 

### FIXED CODE ###

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

dp = [0]*13
dp[0] = 1

for s in S:
    prev = [x for x in dp]
    dp = [0]*13
    if s == "?":
        r = range(10)
    else:
        r = [int(s)]
    for i in range(13):
        for x in r:
            dp[(10*i+x)%13] += prev[i]
    dp = [x % MOD for x in dp]
print(dp[5])
### BUGGY CODE ###

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

r = []
g = []
b = []
for i in range(n):
    if s[i]=="R":
        r.append(i)
    elif s[i]=="G":
        g.append(i)
    else:
        b.append(i)

score = len(r)*len(g)*len(b)
for i in r:
    for j in g:
        dist=abs(j-i)
        if (i>j):
            bi = i+dist
            if bi in b:
                score -=1
            bi = j-dist
            if bi in b:
                score -=1
        else:
            bi = j+dist
            if bi in b:
                score-=1
            bi = i-dist
            if bi in b:
                score-=1
        if((i+j)%2==0 and (i+j)/2 in b):
            score-=1
# print(count_)
print(score)

### FIXED CODE ###

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

r=set()
g=set()
b=set()
for i in range(n):
    if s[i]=='R':
        r.add(i)
    if s[i]=='G':
        g.add(i)
    if s[i]=='B':
        b.add(i)
score = len(r)*len(g)*len(b)
for i in r:
    for j in g:
        dist=abs(j-i)
        if (i>j):
            bi = i+dist
            if bi in b:
                score -=1
            bi = j-dist
            if bi in b:
                score -=1
        else:
            bi = j+dist
            if bi in b:
                score-=1
            bi = i-dist
            if bi in b:
                score-=1
        if((i+j)%2==0 and (i+j)/2 in b):
            score-=1
# print(count_)
print(score)
### BUGGY CODE ###

MOD = 10 ** 9 + 7

def mymodBinomial(n, k, p):
	if k < 0 or k > n:
		return 0
	else:
		numerator = 1
		for i in range(k):
			numerator = (numerator * (n - i)) % p
		denominator = 1
		for i in range(1, k + 1):
			denominator = (denominator * i) % p
		return (numerator * pow(denominator, p - 2, p)) % p


if __name__ == "__main__":
	N, K = map(int, input().split())
	A = list(map(int, input().split()))
	A.sort()
	# print(A)
	l = [0]*(N + 1)
	for i in range(1, N+1):
		l[i] = mymodBinomial(i-1, K-1, MOD)
	ans = 0
	# print(l)
	for i in range(N):
		ans += (A[i] - A[N-1-i])* l[i+1] % MOD
	print(ans % MOD)

### FIXED CODE ###

MOD = 10 ** 9 + 7

# def mymodBinomial(n, k, p):
# 	if k < 0 or k > n:
# 		return 0
# 	else:
# 		numerator = 1
# 		for i in range(k):
# 			numerator = (numerator * (n - i)) % p
# 		denominator = 1
# 		for i in range(1, k + 1):
# 			denominator = (denominator * i) % p
# 		return (numerator * pow(denominator, p - 2, p)) % p

def modBinomiallist(n, k, p):
	l = [0 for i in range(n)]
	for i in range(n):
		if i < k:
			l[i] = 0
		elif i == k:
			l[i] = 1
		else:
			l[i] = l[i - 1] * i * pow(i-k, p-2, p) % p
	return l


if __name__ == "__main__":
	N, K = map(int, input().split())
	A = list(map(int, input().split()))
	A.sort()
	# print(A)
	# l = [0]*(N + 1)
	# for i in range(1, N+1):
	# 	l[i] = mymodBinomial(i-1, K-1, MOD)
	# print(l)
	l = modBinomiallist(N, K-1, MOD)
	# print(l)
	ans = 0
	# print(l)
	for i in range(N):
		ans += (A[i] - A[N-1-i])* l[i] % MOD
	print(ans % MOD)
### BUGGY CODE ###

def is_prime(q):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    return pow(2, q-1, q) == 1


N=input()
min_n=float("inf")
max_n=float("-inf")
a=[]
for i in range(N):
	l,r=map(int,raw_input().split())
	a.append((l,r))
	min_n=min(min_n,l)
	max_n=max(max_n,r)

#print min_n,max_n
#print a

C={}
cnt=0
for i in range(min_n, max_n+1):
	if is_prime(i) and is_prime( (i+1)/2 ):
		cnt+=1
		C[i]=cnt
	else:
		C[i]=cnt
#print C

for i,j in a:
	if i==j:
		if C[i]>0:
			print 1
		else:
			print 0
	else:
		if i==min(C.keys()):
			print C[j]
		else:
			print C[j]-C[i-1]
		

### FIXED CODE ###

N=input()
min_n=float("inf")
max_n=float("-inf")
a=[]
for i in range(N):
	l,r=map(int,raw_input().split())
	a.append((l,r))
	min_n=min(min_n,l)
	max_n=max(max_n,r)

prime=[i for i in range(0, max_n+1)]
prime[1]=0
p_len=len(prime)
for i in range(2,p_len):
	if prime[i]!=0:
		for j in range (i+i,p_len,i):
			prime[j]=0
#print prime

C=[0 for i in range(max_n+1)]
cnt=0
for i in range(max_n+1):
	if prime[i]!=0 and prime[(i+1)/2]!=0:
		cnt+=1
		C[i]=cnt
	else:
		C[i]=cnt

#print C


for i,j in a:
	print C[j]-C[i-1]
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=1
for i in a:
    ans*=i
    if a.count(0)==0 and ans>10**18:
        print(-1)
        exit()
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=1
a=sorted(a)
for i in a:
    ans*=i
    if i==0:
        print(0)
        exit()
    elif ans>10**18:
        print(-1)
        exit()
print(ans)