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

N, P = map(int, input().split())
num = input().strip()
dp = [[0] * P for i in range(2)]
cur = True
ans = 0
for ele in num:
    last = ~cur
    cur_num = int(ele)
    for i in range(P):
        dp[cur][i] = 0

    for i in range(P):
        dp[cur][((i * 10) + cur_num) % P] += dp[last][i]
    dp[cur][cur_num % P] += 1
    ans += dp[cur][0]
    cur = ~cur
print(ans)


### FIXED CODE ###

N, P = map(int, input().split())
num = input().strip()
ans = 0
if P == 2:
    for idx, nu in enumerate(num):
        if nu in '24680':
            ans += idx + 1
elif P == 5:
    for idx, nu in enumerate(num):
        if nu in '50':
            ans += idx + 1
else:
    nnum = [0] * N
    base = 1
    for i in range(N-1, -1, -1):
        nnum[i] = (int(num[i]) * base) % P
        base = (base * 10) % P
    for i in range(1, N):
        nnum[i] = (nnum[i] + nnum[i-1]) % P
    dp = [0] * P
    for i in range(N):
        if nnum[i] == 0:
            ans += 1 + dp[nnum[i]]
        else:
            ans += dp[nnum[i]]
        dp[nnum[i]] += 1
print(ans)
### BUGGY CODE ###

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

a = a[k:]
c = 1

while True:
    if len(a) == 0:
      break
    a = a[k-1:]
    c += 1
print(c)

### FIXED CODE ###

import math

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

a = a[k:]
c = 1

c += math.ceil(len(a) / (k-1))
print(c)
### BUGGY CODE ###

#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))
  
n=int(input())
A=input_array()
ans=0
for i in range(n-1):
	for j in range(i,n):
		if i!=j:
			ans+=A[i]*A[j]

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

### FIXED CODE ###

#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))
  
n=int(input())
A=input_array()
acc_A=[0]

for i in range(n):
	acc_A.append(acc_A[i]+A[i])
ans=0
for i in range(n):
	ans+=A[i]*(acc_A[n]-acc_A[i+1])

print(ans %(10**9+7))
### BUGGY CODE ###

def main():
    N, K = map(int, input().split())
    X = []
    Y = []
    XY = []
    for _ in range(N):
        x, y = map(int, input().split())
        X.append(x)
        Y.append(y)
        XY.append((x, y))
    X.sort()
    Y.sort()

    ans = float('INF')
    for l in range(N):
        for r in range(l + 1, N):
            for d in range(N):
                for t in range(d + 1, N):
                    lx = X[l]
                    rx = X[r]
                    ty = Y[t]
                    dy = Y[d]
                    c = 0
                    for x, y in XY:
                        if lx <= x <= rx and dy <= y <= ty:
                            c += 1
                    if c >= K:
                        ans = min(ans, abs(rx - lx) * abs(ty - dy))
    print(ans)


main()


### FIXED CODE ###

def main():
    N, K = map(int, input().split())
    X = []
    Y = []
    XY = []
    for _ in range(N):
        x, y = map(int, input().split())
        X.append(x)
        Y.append(y)
        XY.append((x, y))
    X.sort()
    Y.sort()

    ans = float('INF')
    for l in range(N):
        for r in range(l + 1, N):
            for d in range(N):
                for t in range(d + 1, N):
                    lx = X[l]
                    rx = X[r]
                    ty = Y[t]
                    dy = Y[d]
                    c = 0
                    for x, y in XY:
                        if lx <= x <= rx and dy <= y <= ty:
                            c += 1
                    if c >= K:
                        ans = min(ans, abs(rx - lx) * abs(ty - dy))
    print(ans)


main()
### BUGGY CODE ###

# https://atcoder.jp/contests/abc077/tasks/arc084_a
# C - Snuke Festival

N = int(input().split()[0])
a_list = sorted(list(map(int, input().split())))
b_list = sorted(list(map(int, input().split())))
c_list = sorted(list(map(int, input().split())))

# あらかじめ計算しておく
b2c_dict = {}
for i in range(N):  # 10 ** 5
    b = b_list[i]
    b2c_dict[i] = len([c for c in c_list if c > b])  # 10 ** 5

comb_n_list = []

for i in range(N):  # 10 ** 5
    a = a_list[i]
    comb_n_list.append(sum([b2c_dict[j] for j, b in enumerate(b_list) if b > a]))

ans = sum(comb_n_list)
print(ans)


### FIXED CODE ###

# https://atcoder.jp/contests/abc077/tasks/arc084_a
# C - Snuke Festival
import bisect

N = int(input().split()[0])
a_list = sorted(list(map(int, input().split())))
b_list = sorted(list(map(int, input().split())))
c_list = sorted(list(map(int, input().split())))

comb_n = 0
comb_n_list = []

# 自分より大きい個数
start_c_index = 0
start_a_index = 0

for i in range(N):  # 10 ** 5
    b = b_list[i]
    a_n = bisect.bisect_left(a_list, b)
    c_n = N - bisect.bisect_right(c_list, b)
    comb_n += a_n * c_n
ans = comb_n
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    n, q = map(int, input().split())
    dic = {}
    stxs = [list(map(int, input().split())) for i in range(n)]
    stxs.sort(key=lambda x:x[2])

    for s, t, x in stxs:
        left = max(0, s - x)
        right = max(0, t - x)

        for i in range(left, right):
            if i not in dic:
                dic[i] = x

    ds = [int(input()) for _ in range(q)]

    for d in ds:
        if d in dic:
            print(dic[d])
        else:
            print(-1)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from heapq import heappush, heappop
from collections import defaultdict
input = sys.stdin.readline

num, person = map(int, input().split())
arr = []

for i in range(num):
    s, t, x = map(int, input().split())
    arr.append((s - x - 0.5, 1, x, i))
    arr.append((t - x - 0.5, -1, x, i))

for i in range(person):
    d = int(input())
    arr.append((d,))

arr.sort()

heap = []
done = defaultdict(int)

for elem in arr:
    if len(elem) == 1:
        d = elem[0]
        while heap and done[heap[0][1]] and d > done[heap[0][1]]:
            heappop(heap)
        if heap:
            print(heap[0][0])
        else:
            print(-1)
        continue

    time, kind, x, i = elem
    if kind == 1:
        heappush(heap, (x, i))
    elif kind == -1:
        done[i] = time
### BUGGY CODE ###

import numpy as np
H,W = map(int,input().split())
S = [list(input()) for _ in range(H)]
L = np.zeros((H,W),dtype=np.int)
R = np.zeros((H,W),dtype=np.int)
U = np.zeros((H,W),dtype=np.int)
D = np.zeros((H,W),dtype=np.int)
for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            L[i][j] = 0
        else:
            L[i][j] = L[i][j-1]+1
        if S[-i-1][-j-1] == "#":
            R[-i-1][-j-1] = 0
        else:
            R[-i-1][-j-1] = R[-i-1][-j]+1

for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            U[i][j] = 0
        else:
            U[i][j] = U[i-1][j]+1
        if S[-i-1][-j-1] == "#":
            D[-i-1][-j-1] = 0
        else:
            D[-i-1][-j-1] = D[-i][-j-1]+1
print(np.max(L+R+U+D)-3)

### FIXED CODE ###

import numpy as np
H,W = map(int,input().split())
S = np.array([list(input()) for _ in range(H)])
S = np.where(S=='.',1,0)


L = np.zeros((H,W),dtype=np.int)
R = np.zeros((H,W),dtype=np.int)
U = np.zeros((H,W),dtype=np.int)
D = np.zeros((H,W),dtype=np.int)

for i in range(W):
    L[:,i] = (L[:,i-1]+1)*S[:,i]
    R[:,-i-1] = (R[:,-i]+1)*S[:,-i-1]
for j in range(H):
    U[j,:] = (U[j-1,:]+1)*S[j,:]
    D[-j-1,:] = (D[-j,:]+1)*S[-j-1,:]

print(np.max(L+R+U+D)-3)
### BUGGY CODE ###

n = int(input())
s = input()
r = []
g = []
b = []
for i in range(n):
	if s[i] == "R":
		r.append(i)
	if s[i] == "G":
		g.append(i)
	if s[i] == "B":
		b.append(i)
count = len(r)*len(g)*len(b)
for i in r:
	for j in g:
		if (max(i,j)+abs(i-j)) in b:
			count -= 1
		if (min(i,j)-abs(i-j)) in b:
			count -= 1
		if abs(i-j)%2 == 0:
			if (i+j)//2 in b:
				count -= 1
print(count)

### FIXED CODE ###

from collections import Counter
# これは, u749194f さんの改造です。
# オリジナルではございません。
# https://atcoder.jp/contests/abc162/submissions/11825963
n = int(input())
s = input()
flag = True
if len(set(s))<=2:
    print(0)
    flag = False
if flag:
    r = [i+1 for i in range(n) if s[i]=='R']
    b = [i+1 for i in range(n) if s[i]=='B']
    g = [i+1 for i in range(n) if s[i]=='G']
    minus = 0
    def cnt_cmb(a, b, c):
        cnt = 0
        set_c = set(c)
        for i in a:
            for j in b:
                if (i+j)/2 in set_c:
                    cnt += 1
        return cnt
    minus += cnt_cmb(r, b, g)
    minus += cnt_cmb(b, g, r)
    minus += cnt_cmb(g, r, b)
    a = Counter(s)
    rslt = 1
    for value in a.values():
        rslt *= value
    print(len(r)*len(b)*len(g)-minus)
### BUGGY CODE ###

n, k = map(int, input().split())
p = [(int(i) + 1) / 2 for i in input().split()]
m = 0
for i in range(n - k + 1):
    a = 0
    for j in range(k):
        a += p[i+j]
    if m < a:
        m = a
print(m)


### FIXED CODE ###

n, k = map(int, input().split())
p = [(int(i) + 1) / 2 for i in input().split()]
a = 0
for j in range(k):
    a += p[j]
m = a
for i in range(1, n - k + 1):
    a += p[i + k-1] - p[i-1]
    if m < a:
        m = a
print(m)
### BUGGY CODE ###

def main():
  import sys
  input=sys.stdin.readline
  
  h,n=map(int,input().split())
  AB=tuple([list(map(int,input().split()))for _ in range(n)])
  
  DP=[10**8+1 for _ in range(h+2)]
  DP[0]=0
  for i in range(1,h+2):
    for a,b in AB:
      if i<=a:
        DP[i]=min(DP[i],b)
      else:
        DP[i]=min(DP[i],DP[i-a]+b)
        
  print(DP[h])
  
if __name__=="__main__":
  main()

### FIXED CODE ###

def main():
  
  h,n=map(int,input().split())
  AB=tuple([list(map(int,input().split()))for _ in range(n)])
  
  DP=[float("inf") for _ in range(h+2)]
  DP[0]=0
  for i in range(1,h+2):
    for a,b in AB:
      if i<=a:
        DP[i]=min(DP[i],b)
      else:
        DP[i]=min(DP[i],DP[i-a]+b)
        
  print(DP[h])
  
if __name__=="__main__":
  main()
### BUGGY CODE ###

# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

H, W, K = lr()
S = np.array([list(map(int, sr())) for _ in range(H)])
Scum = np.array([row.cumsum() for row in S])
INF = 10 ** 10
answer = INF
for pattern in range(1<<H-1):
    cnt = 0
    Tcum = Scum.copy()
    for i in range(H-1):
        if pattern>>i & 1:  # 切れ目
            cnt += 1
        else:
            Tcum[i+1] += Tcum[i]
    prev = -1
    w = 0
    while w < W:
        if np.any(Tcum[:, w] - (Tcum[:, prev] if prev >= 0 else 0) > K):
            if prev == w - 1:  # 1列でKをオーバー
                break
            cnt += 1
            prev = w - 1
        else:
            w += 1
    else:
        answer = min(answer, cnt)

print(answer)


### FIXED CODE ###

import sys
from itertools import accumulate

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

H, W, K = lr()
S = [list(map(int, sr())) for _ in range(H)]
Scum = [list(accumulate(x)) for x in S]
answer = 10000
for bit in range(1<<(H-1)):
    count = 0
    for i in range(H-1):
        if bit >> i & 1:
            count += 1
    bit += 1 << H-1 # 最後の切れ目
    # 縦のラインは貪欲法
    prev = -1
    w = 0
    while w < W:
        white = 0
        cut = False
        for i in range(H):
            white += Scum[i][w] - (Scum[i][prev] if prev >= 0 else 0)
            if (bit >> i) & 1: # 切れ目が来た
                if white > K:
                    cut = True
                white = 0
        if cut:
            if prev == w-1: # 一列でKをオーバー
                break
            count += 1
            prev = w-1
        else:
            w += 1
    else:
        answer = min(answer, count)

print(answer)
### BUGGY CODE ###

import math
H,W,A,B=map(int, input().split())

def comb(x,y):
  return(math.factorial(x)//(math.factorial(x-y)*math.factorial(y)))

alls=comb(H+W-2,W-1)
for i in range(B):
  alls-=comb(H-A-1+i,H-A-1)*comb(W+A-2-i,A-1)

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

### FIXED CODE ###

from math import factorial
H,W,A,B=map(int, input().split())
p=10**9+7
ans=0
X=[1,1]  #階乗テーブル
Y=[1,1]  #階乗の逆元テーブル
calc=[0,1]  #逆元計算用テーブル
for i in range( 2, H+W-2 ):
    X.append( ( X[-1] * i ) % p )
    calc.append( ( -calc[p % i] * (p//i) ) % p )
    Y.append( (Y[-1] * calc[-1]) % p )
for i in range(B,W):
  ans+=(X[H-A-1+i]*X[A+W-2-i]*Y[H-A-1]*Y[i]*Y[A-1]*Y[W-1-i])%p

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

a, b, n = map(int, input().split())

ans = 0
if b > n:
    x = n
    ans = int(a * x // b) - int(a * (x // b))
else:
    m = 0
    for i in range(b):
        if int(a * (n - i) // b) - int(a * ((n - i) // b)) > m:
            m = int(a * (n - i) // b) - int(a * ((n - i) // b))
    ans = m
print(ans)


### FIXED CODE ###

a, b, n = map(int, input().split())

ans = 0
if b > n:
    x = n
    ans = int(a * x // b) - int(a * (x // b))
else:
    x = n
    ans1 = int(a * x // b) - int(a * (x // b))
    x = (n//b)*b-1
    ans2 = int(a * x // b) - int(a * (x // b))
    ans = max(ans1,ans2)
print(ans)
### BUGGY CODE ###

from statistics import mean, median,variance,stdev
import sys
import math
import fractions

def j(q):
    if q==1: print("YES")
    else:print("NO")
    exit(0)


def ct(x,y):
    if (x>y):print("")
    elif (x<y): print("")
    else: print("")

def ip():
    return int(input())

n = ip()                              #入力整数1つ
#n,k= (int(i) for i in input().split())      #入力整数横2つ
#x,y,z = (int(i) for i in input().split())    #入力整数横3つ
#n,m,x,y= (int(i) for i in input().split())  #入力整数横4つ
#a = [int(i) for i in input().split()]        #入力整数配列
#a = input()                                  #入力文字列
#a = input().split()                          #入力文字配列

#jの変数はしようできないので注意
a = []
b = []
for i in range(n):
    x,y = (int(i) for i in input().split())
    b.append(y)
    a.append(x)
sum = 0
c = [a,b]
ma = a.index(max(a))
mb = b.index(max(b))
for i in range(n):
    if a[ma] == 0: ma = a.index(max(a))
    if b[mb] == 0: mb = b.index(max(b))
    if b[ma] < b[mb] and a[mb] == a[ma] and i%2==0:
        ma = mb
    if a[ma] > a[mb] and b[mb] == b[ma] and i%2:
        mb = ma
    if i%2==0: de = a[ma]
    else : de = -b[mb]
    sum+=de
    a[ma] = 0
    b[ma] = 0
print(sum)

### FIXED CODE ###

import math
import fractions
import copy
import numpy as np
def j(q):
    if q==1: print("Yes")
    elif q == 0:print("No")
    exit(0)
rem = pow(10,9)+7
"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def iprow():
    return [int(i) for i in input().split()]
def ips():
    return (int(i) for i in input().split())
def printrow(a):
    for i in a:
        print(i)
def combinations(n,r):
    if n<r:return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def permutations(n,r):
    if n<r:return 0
    return math.factorial(n) // math.factorial(n - r)
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

#n,m = ips()
#a = input()                                  #入力文字列
#a = input().split()                          #入力文字配列
n = ip()                      #入力セット(整数改行あり)(1/2)
#a=[ip() for i in range(m)]    #入力セット(整数改行あり)(2/2)
#a=[input() for i in range(n)]    #入力セット(整数改行あり)(2/2)
#jの変数はしようできないので注意
#a.pop(0)は10^5あるときTLEしやすい!注意!抜くなら逆ソート!
b = []
for i in range(n):
    b.append(iprow())
a = []
for i in range(n):
    c = [sum(b[i]),b[i][0],b[i][1]]
    a.append(c)
a.sort(reverse=True)
s = 0
ct = 0
for i in range(n):
    a[i][2]*=-1
for i in a:
    s+=i[ct+1]
    ct+=1
    ct%=2
print(s)
### BUGGY CODE ###

N=int(input())
from collections import defaultdict
import math
d = defaultdict(int)
MOD=10**9+7
for i in range(N):
  a,b=map(int,input().split())
  x=math.gcd(a,b)
  if x==0:
    if a>b:
      d[(1,0)]+=1
    elif b>a:
      d[(0,1)]+=1
    else:
      d[(0,0)]+=1
  else:
    a,b=a//x,b//x
    if a<0:
      a,b=-a,-b
    d[(a,b)]+=1
ans=0
def C(x):
  X=math.factorial(x)
  _=0
  for i in range(1,x+1):
    _+=X//math.factorial(i)//math.factorial(x-i)
  return _
if d[(0,0)]>0:
  x=d[(0,0)]
  X=math.factorial(x)
  for i in range(1,x+1):
    ans+=X//math.factorial(i)//math.factorial(x-i)
ind=defaultdict(int)
index=1
_ans=[1]
for a,b in list(d.keys()):
  if b<0:
    _k=(-b,a)
  else:
    _k=(b,-a)
  if d[_k]==0:
    _ans.append(C(d[(a,b)])+1)
    index+=1
  else:
    if ind[_k]==0:
      _ans.append(C(d[(a,b)]))
      ind[(a,b)]=index
      index+=1
    else:
      _ans[ind[_k]]+=C(d[(a,b)])+1
_=1
for a in _ans:
  _*=a
print((ans+_-1)%MOD)

### FIXED CODE ###

N=int(input())
from collections import defaultdict
import math
d = defaultdict(int)
MOD=10**9+7
for i in range(N):
  a,b=map(int,input().split())
  x=math.gcd(abs(a),abs(b))
  if a==0:
    if b==0:
      k=(0,0)
    else:
      k=(0,1)
  elif b==0:
    k=(1,0)
  else:
    if a<0:
      a,b=-a,-b
    if b<0:
      a,b=a//x,-((-b)//x)
    else:
      a,b=a//x,b//x
    k=(a,b)
  d[k]+=1

ind=defaultdict(int)
index=1
_ans=[1]
for a,b in list(d.keys()):
  if a==b==0:
    continue
  if b<=0:
    _k=(-b,a)
  else:
    _k=(b,-a)
  if d[_k]==0:
    _ans[0]*=pow(2,d[(a,b)])
  else:
    if ind[_k]==0:
      _ans.append(pow(2,d[(a,b)],MOD))
      ind[(a,b)]=index
      index+=1
    else:
      _ans[ind[_k]]+=pow(2,d[(a,b)],MOD)-1
ans=1
for a in _ans:
  ans=ans*a%MOD
print((d[(0,0)]+ans-1+MOD)%MOD)
### BUGGY CODE ###

def main():
    n, p = map(int, input().split())
    s = input()
    mu = [None]*n
    ans = 0
    c = [0]*10000
    if 10%p == 0:
        for i in range(n):
            if int(s[i])%p == 0:
                ans += i+1
        print(ans)
        return
    for i in range(n):
        v = int(s[i:])%p
        mu[i] = v
        c[v] += 1
    c[0] += 1
    for i in mu:
        c[i] -= 1
        ans += c[i]
        
    print(ans)
    

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n, p = map(int, input().split())
    s = input()
    mu = [None]*n
    ans = 0
    c = [0]*p
    if 10%p == 0:
        ss = map(int, s)
        ss = list(ss)
        for i in range(n):
            if ss[i]%p == 0:
                ans += i+1
        print(ans)
        return
    sr = s[::-1]
    ssr = map(int, sr)
    tens = 1
    v = 0
    for i, si in enumerate(ssr):
        v = (v + (si%p)*tens)%p
        mu[i] = v
        c[v] += 1
        tens *= 10
        tens %= p
    c[0] += 1
    for i in c:
        if i:
            ans += ((i-1)*i)//2
        
    print(ans)
    

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

n,m,k = map(int,input().split())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
import sys
sys.setrecursionlimit(10**6)
maxc = 0
a_i=0
b_i=0
def dfs(a_i,b_i,t,cnt):
    global maxc
    
    if(a_i==n and b_i==m):
        maxc = m+n
        return
    if(k < t):
        maxc = max(maxc,cnt-1)
        return 
    if(a_i < n):
        dfs(a_i+1,b_i,A[a_i]+t,cnt+1)
 
    if(b_i < m):
        dfs(a_i,b_i+1,B[b_i]+t,cnt+1)
 
 
 
        
dfs(0,0,0,0)
print(maxc)

### FIXED CODE ###

import bisect

n,m,k = map(int,input().split())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

A_sum = [0]*(n+1)
B_sum = [0]*(m+1)

for i in range(n):
    A_sum[i+1] = A_sum[i] + A[i]

for i in range(m):
    B_sum[i+1] = B_sum[i] + B[i]

A_limit = bisect.bisect_right(A_sum,k) - 1
mc = 0
B_i = 0
for i in range(A_limit,-1,-1):
    remain_k = k - A_sum[i]
    while((remain_k-B_sum[B_i])>=0):
        B_i += 1
        if(B_i==(m+1)):
            break
    B_i -= 1
    mc = max(mc,(i+B_i))

print(mc)
### BUGGY CODE ###

N = int(input())
a = list(map(int,input().split()))
b = [0] * N
for i in range(N):
    b[i] = a[i]
s = [0] * 30
t = [0] * 30
for i in range(N):
    for j in range(30):
        if a[i] == 0:
            break
        s[j] += a[i]%2
        a[i] = a[i]//2
for i in range(30):
    s[i] = s[i]%2
for i in range(N):
    ans1 = [0] * 30
    for j in range(30):
        ans1[j] = b[i]%2
        b[i] = b[i]//2
        if s[j] == 1:
            ans1[j] = (ans1[j] + 1)%2
    ans = 0
    for j in range(30):
        ans += ans1[j]*(2**j)
    print(ans,end = " ")
print()

### FIXED CODE ###

N = int(input())
a = list(map(int,input().split()))
s = [0] * 30
t = [1] * 30
for i in range(29):
    t[i + 1] = t[i] * 2
ss = a[0]
for j in range(N - 1):
    ss = ss ^ a[j + 1]
for j in range(N):
    print(a[j] ^ ss,end = " ")
print()
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
N,A,B,C=map(int,input().split())
pr=10**9+7
def gya(n):
    return pow(n,pr-2,pr)
MAX_NUM = 2*10**5 + 1
fac  = [0 for _ in range(MAX_NUM)]
finv = [0 for _ in range(MAX_NUM)]
inv  = [0 for _ in range(MAX_NUM)]
fac[0]  = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2,MAX_NUM):
    fac[i] = fac[i-1] * i % pr
    inv[i] = pr - inv[pr%i] * (pr // i) % pr
    finv[i] = finv[i-1] * inv[i] % pr
def c(n,k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % pr) % pr
a=0
ab=A+B
ap=pow(A,N,pr)
bp=pow(B,N,pr)
abp=1
bap=1
for i in range(N):
    a+=(i+N)*c(N+i-1,N-1)%pr*pow(ab,N-1-i)%pr*(ap*abp+bp*bap)%pr
    abp=abp*B%pr
    bap=bap*A%pr
    a%=pr
a=a*100*gya(pow(ab,2*N,pr))%pr
print(a)

### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
N,A,B,C=map(int,input().split())
pr=10**9+7
def gya(n):
    return pow(n,pr-2,pr)
MAX_NUM = 2*10**5 + 1
fac  = [0 for _ in range(MAX_NUM)]
finv = [0 for _ in range(MAX_NUM)]
inv  = [0 for _ in range(MAX_NUM)]
fac[0]  = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2,MAX_NUM):
    fac[i] = fac[i-1] * i % pr
    inv[i] = pr - inv[pr%i] * (pr // i) % pr
    finv[i] = finv[i-1] * inv[i] % pr
def c(n,k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % pr) % pr
a=0
ab=A+B
ap=pow(A,N,pr)
bp=pow(B,N,pr)
abp=1
bap=1
for i in range(N):
    a+=(i+N)*c(N+i-1,N-1)%pr*pow(ab,N-1-i,pr)%pr*(ap*abp+bp*bap)%pr
    abp=abp*B%pr
    bap=bap*A%pr
    a%=pr
a=a*100*gya(pow(ab,2*N,pr))%pr
print(a)
### BUGGY CODE ###

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

k = [0]*N

def kitaiti(n):
    sum = 0
    for i in range(1,n+1):
        sum += i
    return sum / n
    
for i in range(N):
    k[i] = kitaiti(p[i])
ans = 0
for i in range(N-K+1):
    ans = max(ans,sum(k[i:i+K]))
print(ans)
    


### FIXED CODE ###

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

def kitaiti(n):
    return 0.5*n + 0.5

ans = 0

s=[0]*(N+1)
for i in range(N):
    s[i+1] = s[i] + p[i]

for i in range(N-K+1):
    val = s[K+i] - s[i]
    if ans<val:
        ans = val

print(kitaiti(ans)+0.5*(K-1))
### BUGGY CODE ###

n = int(input())
p = 1
for i in range(1, n+1):
  p *= i
print(p%(10**9+7))

### FIXED CODE ###

import math
n = int(input())
print(math.factorial(n)%(10**9+7))
### BUGGY CODE ###

num = int(input())
res = ""

while num != 0:
	num -= 1
	rem = num % 26
	res += chr(ord('a') + int(rem))
	num /= 26

print(res)

### FIXED CODE ###

N = int(input())
ans = ""

while N > 0:
	N -= 1
	ans += chr(ord('a') + N % 26)
	N //= 26

print(ans[::-1])
### BUGGY CODE ###

num=raw_input()
tmp=map(int, raw_input().split(" "))
arr=[]
arr_v=[]
for i in set(tmp):
    if tmp.count(i) > 1:
        arr.append(i)
    if tmp.count(i) > 3:
        arr_v.append(i)

if len(arr)<2:
    print 0
else:
    arr.sort()
    if arr[-1] in arr_v:
        print arr[-1]**2
    else:
        print arr[-2]*arr[-1]


### FIXED CODE ###

num=raw_input()
tmp=map(int, raw_input().split(" "))
tmp.sort()
tmp.reverse()
oldnum=0
arr=[]
flag=0
out=0
for i in range(len(tmp)-1):
    if tmp[i]==tmp[i+1] and flag==0:
            arr.append(tmp[i])
            flag=1
    else:
        flag=0
    if len(arr)==2:
        out=arr[0]*arr[1]
        break
    try:
        if tmp[i]==tmp[i+1] and tmp[i]==tmp[i+2] and tmp[i]==tmp[i+3]:
            out=tmp[i]**2
            break
    except:
        pass
print out
### BUGGY CODE ###

N, K = map(int, input().split(' '))
h = [int(val) for val in input().split(' ')]
dp = [0]

for i in range(1, len(h)):
    min_cost = float('inf')
    for j in range(min(i, K)):
        cost = dp[i-j-1] + abs(h[i]-h[i-j-1])
        if cost < min_cost:
            min_cost = cost
    dp.append(min_cost)
print(dp[-1])

### FIXED CODE ###

import numpy as np

N, K = map(int, input().split(' '))
h = np.array(list(map(int, input().split(' '))))
dp = np.zeros(len(h), dtype=int)
for i in range(1, len(h)):
    start = max(0, i-K)
    dp[i] = min(dp[start:i] + np.abs(h[i] - h[start:i]))
print(dp[-1])