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

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

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

xh.sort()

ans = 0
L = 0
H = 0
while L < n:
    while H < n:
        if xh[H][0] > xh[L][0] + d * 2:
            H -= 1
            break
        H += 1
    if H == n:
        H -= 1

    temp = xh[L][1] // a
    if xh[L][1] % a > 0:
        temp += 1
    ans += temp
    temp *= a
    xh[L][1] = 0
    for i in range(L+1, H+1):
        xh[i][1] -= temp

    while xh[L][1] <= 0:
        L += 1
        if L >= n:
            break

print(ans)

### FIXED CODE ###

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

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

xh.sort()

R = [0] * n
H = 0
for L in range(n):
    while H < n:
        if xh[H][0] > xh[L][0] + d * 2:
            H -= 1
            break
        H += 1
    if H == n:
        H -= 1
    R[L] = H + 1

cs = [0] * (n+1)
H = n - 1
ans = 0
for i in range(n-1, -1, -1):
    x = xh[i][1] // a
    if xh[i][1] % a > 0:
        x += 1
    y = cs[i+1] - cs[R[i]]
    if y >= x:
        cs[i] = cs[i+1]
    else:
#        ans += x - y
        cs[i] = cs[i+1] + x - y

print(cs[0])
### BUGGY CODE ###

N = int(input())
A = []
for i in range(N):
  A.append(int(input()))

#num = [0]*(N+1)
#for i in range(N):
#num[i+1] = num[i] + A[i]

for j in range(N):
  result = A[:j]+A[j+1:]
  print(max(result))

### FIXED CODE ###

N=int(input())
A = []
for i in range(N):
  A.append(int(input()))

left=[0]*(N+1)
right=[0]*(N+1)
for i in range(N):
  left[i+1]=max(left[i],A[i])
  right[N-1-i]=max(right[N-i],A[N-i-1])

ans=0
for i in range(N):
  ans=max(left[i],right[i+1])
  print(ans)
### BUGGY CODE ###

def main():
    S = input()
    Q = int(input())
    reverse = False

    for _ in range(Q):
        TFC = list(input().split())
        if len(TFC) == 1:
            reverse = not(reverse)
        else:
            t,f,c = TFC
            if reverse:
                if f == "2":
                    S = c + S
                else:
                    S = S + c

            else:
                if f == "1":
                    S = c + S
                else:
                    S = S + c
    if reverse:
        print(S[::-1])
    else:
        print(S)
    return

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    S = input()
    Q = int(input())
    reverse = False
    front = []
    back = []
    for _ in range(Q):
        TFC = list(input().split())
        if len(TFC) == 1:
            reverse = not(reverse)
        else:
            t,f,c = TFC
            if reverse:
                if f == "2":
                    front.append(c)
                else:
                    back.append(c)

            else:
                if f == "1":
                    front.append(c)
                else:
                    back.append(c)
    if reverse:
        print("".join(back[::-1]) + S[::-1] + "".join(front))
    else:
        print("".join(front[::-1]) + S + "".join(back))
    return

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

n=input()
a=map(int,input().split())
m=0
from itertools import combinations
for i,j in combinations(a,2):
    k=i*j
    m+=k
v=m%1000000007
if m<=1000000007:
    print(m)
else:
    print(v)

### FIXED CODE ###

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

cumsum = [A[0]]
for i in range(1, N):
    cumsum.append(A[i] + cumsum[i - 1])

ans = 0
for i in range(N):
    ans += (A[i] * (cumsum[-1] - cumsum[i])) % MOD
    ans %= MOD

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

A,B= map(int, input().split())
now_sum = A
ans = 1
while True:
     if now_sum >= B:
         print(ans)
     now_sum += A-1
     ans += 1


### FIXED CODE ###

A,B= map(int, input().split())
now_sum = 1
ans = 0
while True:
     if  now_sum >= B:
         print(ans)
         break
     now_sum += A-1
     ans += 1
### BUGGY CODE ###

Q=int(input())
L=[list(map(int,input().split())) for i in range(Q)]
A,B=zip(*L)
a=max(max(A),max(B))
def get_primenumber(N):
  #素数リスト
  prime_list = [2]
    #3からNまでの数字を一つずつ取り出す
  for num in range(3,N+1,2):
    #取り出した数字が素数リストの要素で割れなければ素数リストに追加する
    if all( num % prime != 0 for prime in prime_list):
      prime_list.append(num)
  return prime_list
X=get_primenumber(a)

def F(n):
  ans=0
  Z=get_primenumber(n)
  for i in Z:
    if (i+1)//2 in Z:
      ans+=1
  return ans

for s,t in L:
  print(F(t)-F(s-1))

### FIXED CODE ###

Q=int(input())
A=[list(map(int,input().split())) for i in range(Q)]
B,C=zip(*A)
a=max(max(B),max(C))
def get_primenumber(N):
  prime_list=[2]
  for num in range(3,N+1,2):
    if all(num%prime != 0 for prime in prime_list):
      prime_list.append(num)
  return prime_list

X=get_primenumber(a)
P=[False]*(a+1)
L=[False]*(a+1)
for i in X:
  P[i]=True
for i in X:
  if P[(i+1)//2]:
    L[i]=True
C=[]
c=0
for i in range(a+1):
  if L[i]:
    c+=1
  C.append(c)
for s,t in A:
  print(C[t]-C[s-1])
### BUGGY CODE ###

from collections import deque
N = int(input())
A = [deque(list(map(int, input().split()))) for _ in range(N)]
ans = 0
t = 0
for i in range(10**5):
    for k in range(N):
        if A[k] != deque([]):
            if A[k][0] == 0:
                A[k].popleft()
        else:
            t += 1
    if t == N:
        break
    t = 0
    for j in range(N):
        if A[j]:
            tmp = A[j][0]
        else:
            continue
        if tmp-1 > j and A[tmp-1][0] -1 == j:
            A[j][0] = 0
            A[tmp-1][0] = 0
    ans += 1
if ans == 100000:
    print(-1)
    exit()
print(ans-1)

### FIXED CODE ###

from collections import deque
import time     #ズルです…
start = time.time()
N = int(input())
A = [deque(list(map(int, input().split()))) for _ in range(N)]
ans = 0
t = 0
z = 0
Atmp = []
for i in range(10**6):
    for k in range(N):
        if A[k] != deque([]):
            if A[k][0] == 0:
                A[k].popleft()
            else:
                z += 1
        else:
            t += 1
    if t == N:
        break
    if t+z == N and i != 0:
        ans = 0
        break
    z = 0
    t = 0
    for j in range(N):
        if A[j]:
            tmp = A[j][0]
        else:
            continue
        if tmp-1 > j and A[tmp-1][0] -1 == j:
            A[j][0] = 0
            A[tmp-1][0] = 0
    ans += 1
    aida = time.time()
    if aida-start > 1.7:
        print(N*(N-1)//2)       #ズル
        exit()
print(ans-1)
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))

def main():
  dp=[[0]*(k+1) for _ in range(n+1)]
  mod=1000000007
  #i人目までに0個配る方法は1通り
  #for i in range(n+1):
  #  dp[i][0]=1
  for i in range(0,n+1):
    for j in range(0,k+1):
      if i==0 and j==0:
        dp[i][j]=1
        break
      if j==0:
        dp[i][j]=1
        continue
      tmp=dp[i - 1][j] + dp[i][j - 1]
      if tmp>=mod:
        tmp%=mod
      dp[i][j]=tmp
      if j-a[i-1]-1>=0:
        tmp=dp[i][j]-dp[i-1][j-a[i-1]-1]
        if tmp>=mod:
          tmp%=mod
        dp[i][j]=tmp
    #print(dp)   
  print(dp[n][k])
main()

### FIXED CODE ###

import sys
from itertools import accumulate

def main():
  input=sys.stdin.readline
  n,k=map(int,input().split())
  A=list(map(int,input().split()))
  mod=10**9+7
  dp=[0]*(k+1)
  dp[0]=1
  for a in A:
    dp=list(accumulate(dp))
    #print("accumulated",dp)
    for j,d in enumerate(dp[:k-a],start=a+1):
      dp[j]-=d
    dp=[dpi%mod for dpi in dp]
    #print(dp)
  print(dp[k])
"""
def main():
  dp=[[0]*(k+1) for _ in range(n+1)]
  mod=1000000007
  #i人目までに0個配る方法は1通り
  #for i in range(n+1):
  #  dp[i][0]=1
  for i in range(0,n+1):
    for j in range(0,k+1):
      if i==0 and j==0:
        dp[i][j]=1
        break
      if j==0:
        dp[i][j]=1
        continue
      tmp=dp[i - 1][j] + dp[i][j - 1]
      if tmp>=mod:
        tmp%=mod
      dp[i][j]=tmp
      if j-a[i-1]-1>=0:
        tmp=dp[i][j]-dp[i-1][j-a[i-1]-1]
        if tmp>=mod:
          tmp%=mod
        dp[i][j]=tmp
    #print(dp)   
  print(dp[n][k])"""
main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
# template


N, Q = mi()
# print(N, Q)
S = li()
Alist = []
for i in range(N - 1):
    if S[i] == 'A' and S[i + 1] == 'C':
        Alist.append(i)
AClist = [0]*(N+1)
for i in range(N - 1):
    if i in Alist:
        AClist[i + 2] = AClist[i+1] + 1
    else:
        AClist[i+2] = AClist[i+1]

# print(AClist)

for i in range(Q):
    l, r = mi()
    if AClist[l - 1] != AClist[l]:
        print(AClist[r] - AClist[l])
    else:
        print(AClist[r] - AClist[l-1])

### FIXED CODE ###

import sys
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
# template


N, Q = mi()
# print(N, Q)
S = li()
Alist = []
for i in range(N - 1):
    if S[i] == 'A' and S[i + 1] == 'C':
        Alist.append(i)
Aset = set(Alist)
AClist = [0]*(N+1)
for i in range(N-1):
    if i in Aset:
        AClist[i + 2] = AClist[i + 1] + 1
    else:
        AClist[i+2] = AClist[i+1]
        # print(AClist)

for i in range(Q):
    l, r = mi()
    if AClist[l - 1] != AClist[l]:
        print(AClist[r] - AClist[l])
    else:
        print(AClist[r] - AClist[l-1])
### BUGGY CODE ###


S = input()
N = len(S)
n = 10 ** 6
while n != len(S):
    n = len(S)
    S = S.replace('01', '')
    S = S.replace('10', '')

ans = N - len(S)
print(ans)

### FIXED CODE ###


S = input()
a = S.count('0')
b = S.count('1')

ans = min(a, b) * 2

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

n, x = map(int, input().split())
a = list(map(int, input().split()))
if n == 1:
    print(abs(x-a[0]))
    exit()
else:
    a.sort()
    box = [a[i+1]-a[i] for i in range(n-1)]
    b = min(box)
    for i in range(1,b+1):
        for j in range(n-1):
            if box[j]%i:
                break
            if j == n-2:
                ans = i
    d = abs(x-a[0])
    if ans <= d:
        for i in range(1,ans+1):
            if d%i:
                continue
            else:
                temp = i
        print(temp)
    else:
        for i in range(1,d+1):
            if ans%i:
                continue
            else:
                temp = i
        print(temp)



### FIXED CODE ###

n, x = map(int, input().split())
a = list(map(int, input().split()))
if n == 1:
    print(abs(x-a[0]))
    exit()
else:
    a.append(x)
    a.sort()
    box = [a[i+1]-a[i] for i in range(n)]
    b = min(box)
    for i in range(1,b+1):
        for j in range(n-1):
            if box[j]%i:
                break
            if j == n-2:
                ans = i
    print(ans)
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
l.sort()
ans=0
import bisect
for i in range(n):
    for j in range(n):
        if i<j:
            a=l[i]
            b=l[j]
            x=bisect.bisect_left(l,a+b)
            for k in range(x):
                if k==i or k==j:
                    continue
                else:
                    c=l[k]
                    if a<(b+c) and b<(a+c) and c<(a+b):
                        ans+=1
print(ans//3)


### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
l.sort()
ans=0
import bisect
for i in range(n):
    for j in range(n):
        if i<j:
            a=l[i]
            b=l[j]
            x=bisect.bisect_left(l,a+b)
            y=bisect.bisect_right(l,b-a)
            if b-a>=a:
                ans+=max(0,x-y-1)
            else:
                ans+=max(0,x-y-2)
print(ans//3)
### BUGGY CODE ###

import sys
stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()
sys.setrecursionlimit(10**6)

n = ni()
a = na()
b = []
for i in range(n):
    b.append((a[i],i))

b.sort(reverse=True)

ans = 0

def f(left,right,k,c):
    if k == n:
        return c
    i,j = b[k]
    x = abs(j-left)
    y = abs(right-j)
    return max(f(left+1,right,k+1,c+x*i), f(left,right-1,k+1,c+y*i))

ans = f(0,n-1,0,0)

print(ans)


### FIXED CODE ###

import sys
stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()
sys.setrecursionlimit(10**6)

n = ni()
a = na()
b = []
for i in range(n):
    b.append((a[i],i))
 
b.sort(reverse=True)

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

for i in range(1,n+1):
    x,y = b[i-1]
    for j in range(i+1):
        left = dp[i-1][j-1] + x*abs(y-j+1) if j > 0 else -1
        right = dp[i-1][j] + x*abs(n-i+j-y) if j < i else -1
        dp[i][j] = max(left,right)

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

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

S = int(input())
count = 0
l = [0]*2019
l[0] = 1

for i in range(1,len(str(S))+1):
   l[(S%10**i)%2019] += 1

for j in range(2019):
    if l[j] >= 2:
        count += comb(l[j],2)

print(count)


### FIXED CODE ###

S = input()
count = 0
l = [0]*2019
l[0] = 1
mod = 2019
tmp = 0

for i in range(1,len(S)+1):
    tmp = (tmp + int(S[len(S)-i])*pow(10,i-1,mod))%mod
    l[tmp] += 1
    

for j in range(2019):
    if l[j] >= 2:
        count += l[j]*(l[j]-1)//2

print(count)
### BUGGY CODE ###

N, K = map(int, input().split())
p = list(map(int, input().split()))

exp = []
sum_list = [0]
result_list = []
result = 0
for i in range(N):
    exp.append((p[i]+1)/2)
    sum_list.append(sum(exp))  
for i in range(N-K+1):
    tmp = sum_list[K+i] - sum_list[i]
    if result < tmp:
        result = tmp
    
print(result)


### FIXED CODE ###

N, K = map(int, input().split())
p = list(map(int, input().split()))
 
exp = []
sum_list = []
result_list = []
result = 0
count = 0
tmp = 0
for i in range(N):
    if count < K-1:
        a = (p[i]+1)/2
        exp.append(a)
        tmp += a
    else:
        a = (p[i]+1)/2
        exp.append(a)
        tmp += a
        sum_list.append(tmp)
        tmp -= exp[count-K+1]
    count += 1

print(max(sum_list))
### BUGGY CODE ###

import fractions
import sys
input = sys.stdin.readline

mod = 10 ** 9 + 7
def modpow(a, x):
    if a == 0:
        return 0
    if x == 0:
        return 1
    elif x % 2 == 0:
        return modpow((a * a) % mod, x // 2) % mod
    else:
        return (modpow((a * a) % mod , x // 2) % mod * a) % mod


def factorization(x):
    ans = []
    i = 2
    in_x = x
    while i <= x:
        count = 0
        while x % i == 0:
            x = x // i
            count += 1
        if count > 0:
            ans.append((i, count))
        i += 1
    return ans


N = int(input())
A = list(map(int, input().split(" ")))
primes = {}
for a in A:
    factors = factorization(a)
    for f in factors:
        if f[0] in primes:
            primes[f[0]] = max(primes[f[0]], f[1])
        else:
            primes[f[0]] = f[1]

lcm = 1
for p in primes:
    lcm *= modpow(p, primes[p])
    lcm %= mod

ans = 0
for a in A:
    ans += (lcm * modpow(a, mod - 2)) % mod
    ans %= mod
print(ans)

### FIXED CODE ###

import sys
import fractions
input = sys.stdin.readline


mod = 10 ** 9 + 7
N = int(input().strip())
A = list(map(int, input().strip().split(" ")))

lcm = 1
for a in A:
    lcm = a // fractions.gcd(a, lcm) * lcm

ans = 0
for a in A:
    ans += lcm // a

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

from collections import deque

n,x,y=map(int,input().split())
g = [[i-1,i+1] for i in range(1,n-1)]
g.insert(0,[1])
g.append([n-2])
g[x-1].append(y-1)
g[y-1].append(x-1)
dist = []


def bfs(i):
    d = [float("inf")]*n
    
    que = deque([])
    que.append(i)
    d[i] = 0

    while que:
        idx = que.popleft()
        l = g[idx]
        
        for j in l:
            if d[j] == float("inf"):
                d[j] = d[idx] + 1
                que.append(j)
            elif d[j] > d[idx] + 1:
                d[j] = d[idx] + 1
                que.append(j)
    
    dist.extend(d)

for i in range(n):
    bfs(i)

dist.sort()
for i in range(1,n):
    print(dist.count(i)//2)


### FIXED CODE ###

n,x,y=map(int, input().split())
ans=[0]*n

for i in range(1,n):
	for j in range(i+1,n+1):
		a = min(j-i, abs(x-i)+1+abs(y-j))
		ans[a-1] += 1
		
for i in range(n-1):
	print(ans[i])
### BUGGY CODE ###

import numpy as np
N, K, Q = map(int, input().split())
S = []
for _ in range(Q):
    S.append(int(input())) 
P=np.array([K]*N)
for i in range(Q):
  a=np.array([-1]*N)
  a[S[i]-1]=0
  P +=a
for i in range(N):
  if P[i] <= 0:
    print("No")
  else:
    print("Yes")

### FIXED CODE ###

import numpy as np
N, K, Q = map(int, input().split())
S = []
for _ in range(Q):
    S.append(int(input())) 
P=[K]*N
for i in range(Q):
  P[S[i]-1]+=1
P = np.array(P)
P -= Q
for i in range(N):
  if P[i] <= 0:
    print("No")
  else:
    print("Yes")
### BUGGY CODE ###

N = int(input())
h=list(map(int,input().split()))
c = 0
A = [h[0]]
for i in range(0,N):
    A.append(h[i])
    if min(A) >= h[i]:
        c += 1
print(c)

### FIXED CODE ###

N = int(input())
h=list(map(int,input().split()))
c = 0
a = h[0]
for i in range(0,N):
    if a > h[i]:
        a = h[i]
    if a >= h[i]:
        c += 1
print(c)
### BUGGY CODE ###

import itertools

N,M,R=map(int,input().split())
r=list(map(int,input().split()))
n=len(r)

graph=[[float("inf")]*N for _ in range(N)]
for i in range(M):
    A,B,C=map(int,input().split())
    A-=1
    B-=1
    graph[A][B]=C
    graph[B][A]=C

def dijkstra(start,cost):
    d=[float("inf")]*N
    used=[False]*N
    d[start]=0

    while True:
        v=-1
        for i in range(N):
            if (not used[i]) and (v==-1):
                v=i
            elif (not used[i]) and d[i]<d[v]:
                v=i
        if v==-1:
            break
        used[v]=True

        for j in range(N):
            d[j]=min(d[j],d[v]+cost[v][j])
    
    return d

d=[]
for i in range(N):
    d.append(dijkstra(i,graph))

anss=[]
for city in itertools.permutations(r):
    ans=0
    for i in range(n-1):
        ans+=d[city[i]-1][city[i+1]-1]
    anss.append(ans)
print(min(anss))

### FIXED CODE ###

import itertools

N,M,R=map(int,input().split())
r=list(map(int,input().split()))
n=len(r)

graph=[[float("inf")]*N for _ in range(N)]
for i in range(M):
    A,B,C=map(int,input().split())
    A-=1
    B-=1
    graph[A][B]=C
    graph[B][A]=C

def dijkstra(start,cost):
    d=[float("inf")]*N
    used=[False]*N
    d[start]=0

    while True:
        v=-1
        for i in range(N):
            if (not used[i]) and (v==-1):
                v=i
            elif (not used[i]) and d[i]<d[v]:
                v=i
        if v==-1:
            break
        used[v]=True

        for j in range(N):
            d[j]=min(d[j],d[v]+cost[v][j])
    
    return d

d=[]
for i in range(N):
    d.append(dijkstra(i,graph))

ans=float("inf")
for city in itertools.permutations(r):
    tmp=0
    for i in range(n-1):
        tmp+=d[city[i]-1][city[i+1]-1]
    ans=min(ans,tmp)
print(ans)
### BUGGY CODE ###

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

d = {}
for _ in range(N):
    S,T,X = map(int,input().split())
    for x in range(max(0,S-X),max(0,T-X)):
        if x in d.keys():
            d[x] = min(d[x],X)
        else:
            d[x] = X

for _ in range(Q):
    D = int(input())
    if D in d.keys():
        print(d[D])
    else:
        print(-1)

### FIXED CODE ###

#5814544

from bisect import bisect_left

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

STX = []
D = []
for _ in range(N):
    STX.append(list(map(int,input().split())))
for _ in range(Q):
    D.append(int(input()))

STX.sort(key=lambda x:x[2])

ans = [-1]*Q
skip = [-1]*Q

for s,t,x in STX:
    left = bisect_left(D,s-x)
    right = bisect_left(D,t-x)

    while left < right:
        if skip[left] == -1:
            ans[left] = x
            skip[left] = right
            left += 1
        else:
            left = skip[left]
    
for a in ans:
    print(a)
### BUGGY CODE ###

import math
A, B = map(int, input().split())
tmpa = math.floor(A / 0.08)
tmpb = math.floor(B / 0.1)
alst = []
blst = []

indexa = 0
while True:
    tmp = math.floor((tmpa + indexa) * 0.08)
    if tmp == A:
        alst.append(tmpa + indexa)
        indexa += 1
    elif tmp > A:
        break
    else:
        indexa += 1

indexb = 1
while True:
    tmp = math.floor((tmpb + indexb) * 0.1)
    if tmp == B:
        blst.append(tmpb + indexb)
        indexb += 1
    elif tmp == B:
        break
    else:
        indexb += 1
ans = -1
alst.sort()
blst.sort()
for i in alst:
    if blst.count(i) >= 1:
        ans = i
        break

print(ans)

### FIXED CODE ###

import math
A, B = map(int, input().split())
tmpa = math.floor(A / 0.08)
tmpb = math.floor(B / 0.1)
alst = []
blst = []

indexa = 0
while True:
    tmp = math.floor((tmpa + indexa) * 0.08)
    if tmp == A:
        alst.append(tmpa + indexa)
        indexa += 1
    elif tmp > A:
        break
    else:
        indexa += 1

indexb = 0
while True:
    tmp = math.floor((tmpb + indexb) * 0.1)
    if tmp == B:
        blst.append(tmpb + indexb)
        indexb += 1
    elif tmp > B:
        break
    else:
        indexb += 1
ans = -1
alst.sort()
blst.sort()
for i in alst:
    if blst.count(i) >= 1:
        ans = i
        break

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

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

ans = float('inf')
w_left = [0]
e_right = [0]

for i in range(1,n):
  if s[i-1] == 'W':
    w_left.append(w_left[i-1]+1)
  else :
    w_left.append(w_left[i-1])
      
for i in range(1,n):
  if s[n-i] == 'E':
    e_right.insert(0,e_right[0]+1)
  else :
    e_right.insert(0,e_right[0])

for i in range(n):
    ans = min(ans , w_left[i]+e_right[i])
print(ans)

### FIXED CODE ###

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

ans = float('inf')
w_left = [0]*n
e_right = [0]*n

for i in range(1,n):
  if s[i-1] == 'W':
    w_left[i] = w_left[i-1]+1
  else :
    w_left[i] = w_left[i-1]
      
for i in range(1,n):
  if s[n-i] == 'E':
    e_right[n-i-1] = e_right[n-i]+1
  else :
    e_right[n-i-1] = e_right[n-i]

for i in range(n):
    if ans > w_left[i]+e_right[i]:
        ans = w_left[i]+e_right[i]
print(ans)
### BUGGY CODE ###

N,W = list(map(int,input().split()))
w_l = []
v_l = []
for i in range(N):
    w,v = list(map(int,input().split()))
    w_l.append(w)
    v_l.append(v)
def knapsack(N,W,w_l,v_l):
    if (N==0 or W==0):
        return 0
    elif(w_l[N-1]>W):
        return knapsack(N-1,W,w_l,v_l)
    
    else:
        return max(knapsack(N-1,W,w_l,v_l), v_l[N-1]+knapsack(N-1,W-w_l[N-1],w_l,v_l))
ans = knapsack(N,W,w_l,v_l)
print(ans)

### FIXED CODE ###

import numpy as np

N,W = list(map(int,input().split()))
dp = np.zeros(W+1,dtype = int)
for i in range(N):
    w,v = list(map(int,input().split()))
    dp[w:] = np.maximum(dp[w:],dp[:-w] + v)
print(dp[-1])
### BUGGY CODE ###

N = int(input())
power = 1
for _ in range(1, N + 1):
    power *= _

print(power % (10**9 + 7))

### FIXED CODE ###

N = int(input())
power = 1
for _ in range(1, N + 1):
    power *= _
    if power > 10**9 + 7:
        power %= (10**9 + 7)

print(power % (10**9 + 7))