Harryxun/stf_run huggingface dataset:
s = input()
t = input()

S = []
T = []

S_a = []

for i in range(len(s)):
    S.append(s[i])

for i in range(len(t)):
    T.append(t[i])

for i in range(len(S)):
    if S[i] == T[0]:
        for j in range(len(T)):
            if S[i + j] != T[j] and S[i + j] != "?":
                print('a')
                print(S[i+j] + T[j])
                break
        if j == len(T) - 1:
            string = S[0:i] + T + S[i + len(T)::]
            S_a.append(string)
            for k in range(len(string)):
                if string[k] == "?":
                    string[k] = "a"
S_a.sort()
if S_a == []:
    print("UNRESTORABLE")
else: print(''.join(S_a[0]))

### FIXED CODE ###

S = list(input())
T = list(input())

ans = -1
ansS = []
if len(S) < len(T):
    ans = -1
else:
    for i in range(len(S) - len(T) + 1):
        ans = 1
        for j in range(len(T)):
            #print(S[i + j], T[j])
            if S[i + j] != T[j] and S[i + j] != "?":
                ans = -1
                break
        if ans == 1:
            thisS = S[:i] + T + S[i + len(T):]
            for j in range(len(S)):
                if thisS[j] == "?":
                    thisS[j] = "a"
            ansS.append(thisS)

if len(ansS) == 0:
    print("UNRESTORABLE")
else:
    ansS.sort()
    for i in ansS[0]:
        print(i, end = "")
    print()
from line_profiler import LineProfiler
from collections import deque
from sys import stdin

def main():
    while(True):
        W, H = map(int, stdin.readline().split())
        if not W: break
        tx,ty = map(int, stdin.readline().split())
        kx,ky = map(int, stdin.readline().split())
        ma = [[False]*(W+2) for _ in range(H+2)]
        for i in range(1,H+1):
            for j,a in enumerate(stdin.readline().split()):
                ma[i][j+1] = bool(1-int(a))
        que = deque([[tx,ty,kx,ky,0]])
        pas = set()
        ans = "NA"
        while(que):
            tx,ty,kx,ky,c = que.popleft()
            if tx == kx and ty == ky:
                ans = c
                break
            for dx,dy in [[-1,0],[0,-1],[1,0],[0,1]]:
                tdx, tdy = [ dx, dy] if ma[ty+dy][tx+dx] else [0,0]
                kdx, kdy = [-dx,-dy] if ma[ky-dy][kx-dx] else [0,0]
                if (tx+tdx,ty+tdy,kx+kdx,ky+kdy) in pas: continue
                if c+1 > 100: continue
                que.append([tx+tdx,ty+tdy,kx+kdx,ky+kdy,c+1])
                pas.add((tx+tdx,ty+tdy,kx+kdx,ky+kdy))
        print(ans)

if __name__ == "__main__":
    prf = LineProfiler()
    prf.add_function(main)
    prf.runcall(main)
    prf.print_stats()
    # main()


### FIXED CODE ###

# from line_profiler import LineProfiler
from collections import deque
from sys import stdin

def main():
    while(True):
        W, H = map(int, stdin.readline().split())
        if not W: break
        tx,ty = map(int, stdin.readline().split())
        kx,ky = map(int, stdin.readline().split())
        ma = [[False]+[bool(1-int(a)) for a in stdin.readline().split()]+[False] for i in range(H)]
        ma = [[False]*(W+2)] + ma + [[False]*(W+2)]
        que = deque([[tx,ty,kx,ky,0]])
        pas = set()
        ans = "NA"
        while(que):
            tx,ty,kx,ky,c = que.popleft()
            if tx == kx and ty == ky:
                ans = c
                break
            if c+1 > 100: continue
            for dx,dy in [[-1,0],[0,-1],[1,0],[0,1]]:
                tdx, tdy = ( dx, dy) if ma[ty+dy][tx+dx] else (0,0)
                kdx, kdy = (-dx,-dy) if ma[ky-dy][kx-dx] else (0,0)
                if (tx+tdx,ty+tdy,kx+kdx,ky+kdy) in pas: continue
                que.append([tx+tdx,ty+tdy,kx+kdx,ky+kdy,c+1])
                pas.add((tx+tdx,ty+tdy,kx+kdx,ky+kdy))
        print(ans)

if __name__ == "__main__":
    # prf = LineProfiler()
    # prf.add_function(main)
    # prf.runcall(main)
    # prf.print_stats()
    main()
n,m,x,y = map(int, input().split())
x_city = sorted(list(map(int, input().split())))
y_city = sorted(list(map(int, input().split())))

if x_city[len(x_city)-1] < y_city[0] and (x < y_city[0] <= y)
    print("No War")
else:
    print("War")


### FIXED CODE ###

n,m,x,y = map(int, input().split())
x_city = sorted(list(map(int, input().split())))
y_city = sorted(list(map(int, input().split())))

if x_city[len(x_city)-1] < y_city[0] and (x < y_city[0] <= y):
    print("No War")
else:
    print("War")
N=input()
print('YES' if N%9==0 else 'NO')

### FIXED CODE ###

N = input()
sum = 0
for c in N:
    sum += int(c)
if sum % 9 == 0:
    print('Yes')
else:
    print('No')
n,k = map(int, input().split())
array = list(map(int, input().split()))
one_tento:int = 0
for i in range(n-1):
    for j in range(i+1,n):
        if array[i] > array[j]:
            one_tento += 1
two_tento:int = 0
for i in range(n):
    for j in range(n):
        if array[i] > array[j]:
            two_tento += 1

result1:int = (one_tento * k) % (7 + 10**9)
result2:int = (two_tento * k * (k - 1) / 2) % (7 + 10**9)
result3:int = (result1 + result2)% (7 + 10**9)
print(int(result3))

### FIXED CODE ###

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

one_tento = 0
for i in range(n-1):
    for j in range(i+1,n):
        if array[i] > array[j]:
            one_tento += 1
one_tento = int(one_tento)

two_tento = 0
for i in range(n):
    for j in range(n):
        if array[i] > array[j]:
            two_tento += 1
two_tento = int(two_tento)

result1 = (one_tento * k) % (7 + 10**9)
result2 = ((two_tento % (7 + 10**9)) * ((k * (k - 1) // 2) % (7 + 10**9))) % (7 + 10 **9)
result3 = (result1 + result2) % (7 + 10**9)
print(int(result3))
A,B=map(int,input().split())
print(6-(a+B))

### FIXED CODE ###

a=int(input())
b=int(input())
print(6-a-b)
W,H,x,y,z = map(int, input().split())
if x-r >= 0 and x + r <= W and y-r >= 0 and y + r <= H:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

W,H,x,y,r = map(int, input().split())
if (x-r >= 0 and x + r <= W) and (y - r >= 0 and y + r <= H):
                                                            print("Yes")
else:
                                                            print("No")
a, b = map(int, intpu().split())
print(a * b)

### FIXED CODE ###

a, b = map(int, input().split())
print(a * b)
import itertools

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

s = [sum(c) for c in list(itertools.combinations(a, 2))]

f = False
for i in range(n):
    if s[i] >= h:
        f = True
        break

print('Yes' if f == True else 'No')

### FIXED CODE ###

h, n = map(int, input().split())
a = list(map(int, input().split()))
print('Yes' if sum(a) >= h else 'No')
Q = 6-A-B;
print(Q);

### FIXED CODE ###

A = int(input())
B = int(input())
Q = 6-A-B

print(Q)
import io,sys
sys.setrecursionlimit(10**6)

def main():
    s = sys.stdin.readline().rstrip().split()
    a = int(s[0])

    b = int(float(s[1])*100+0.1)

    print(ans=a*b//100)
main()

### FIXED CODE ###

import io,sys
sys.setrecursionlimit(10**6)

def main():
    s = sys.stdin.readline().rstrip().split()
    a = int(s[0])

    b = int(float(s[1])*100+0.1)

    print(a*b//100)
main()
import numpy as np  

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

dp = np.array([0] * w+1)

for i in range(n):
    weight, value = map(int, input().split())

    dp[weight:] = np.maximum(dp[weight:], dp[:-weight] + value) 

print(int(dp[-1]))

### FIXED CODE ###

import sys
import numpy as np
import itertools
import heapq
import bisect
import math
import queue
from operator import itemgetter #sortedの対象を決めたい
from fractions import gcd #最大公約数
from copy import deepcopy #参照で影響されないコピー
from collections import Counter, deque, defaultdict #要素ごとの出現回数、双方向アクセス可能データ型
from functools import reduce
mod = 1000000007
inf = 10**10
sys.setrecursionlimit(1000000)

input = sys.stdin.readline

def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res
 
def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)
# template


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

    dp = np.zeros([n+1, w+1])
    
    for i, itm in enumerate(wv):
        dp[i+1, :itm[0]] = dp[i, :itm[0]]
        dp[i+1, itm[0]:] = np.max([dp[i, itm[0]:], dp[i, :w-itm[0]+1] + itm[1]], axis=0)

    print(int(dp[n, w]))


if __name__ == "__main__":
    main()
#include<bits/stdc++.h>
using namespace std;
int main(){
    long long A,B;

    cin >> A >> B;

    long long C;

    if(A>=B){
        C = A%B;
    }else{
        C = B%A;
    }

    long long count = 0LL;

    long long now = 0; 
    long long a = 2;

    vector<int> yakusu;
    while(C >= a*a){
        if(C%a == 0){
            if (a != now){
                count++;
                yakusu.push_back(a);
                now = a;
            }
            C /= a;
        }else{
            a++;
        }
    }

    if(std::count(yakusu.begin(), yakusu.end(), C) == 0) count++;

    count++;

    cout << count << endl;
    return 0;


}

### FIXED CODE ###

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


A_yaku = []

now = 0

a = 2

while A >= a*a:
  if A%a == 0:
    if a != now:
      A_yaku.append(a)
      now = a
    A /= a
  else:
    a +=1

if A != now and A != 1:
  A_yaku.append(A)

B_yaku = []

now = 0

a = 2

while B >= a*a:
  if B%a == 0:
    if a != now:
      B_yaku.append(a)
      now = a
    B /= a
  else:
    a +=1

if B != now and B != 1:
  B_yaku.append(B)

count = 0

if(len(A_yaku) >= len(B_yaku)):
  for i in range(0,len(B_yaku)):
    if(B_yaku[i] in A_yaku):
      count += 1
else:
  for i in range(0,len(A_yaku)):
    if(A_yaku[i] in B_yaku):
      count += 1

count += 1

print(count)
N=int(input().split())
B=list(map(int,input().split()))
A=[0]*N
A[0]=B[0]
A{N-1]=B[N-2]
for i in range(1,N-2):
  A[i]=min(B[i-1],B[i])
print(sum(A))

### FIXED CODE ###

N=int(input())
B=list(map(int,input().split()))
A=[0]*N
A[0]=B[0]
A[N-1]=B[N-2]
for i in range(1,N-1):
  A[i]=min(B[i-1],B[i])
print(sum(A))
n=int(input())
a=list(map(int, input().split()))
q=int(input())

S=sum(a)

table=[0]*(10**5)

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

for i in range(q):
    b, c=map(int, input().split())

    cnt=table[b]
    table[c]+=cnt
    ans=S+(cnt*(c-b))
    print(ans)
    table[b]=0
    S=ans

### FIXED CODE ###

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

S=sum(a)

table=[0]*(10**6)

for i in range(n):
    table[a[i]]+=1

for i in range(q):
    b, c=map(int, input().split())
    if table[b]!=0:
        cnt=table[b]
        table[c]+=cnt
        ans=S+(cnt*(c-b))

        print(ans)

        table[b]=0
        S=ans
    else:
        print(S)
from sys import exit
def groupby(a):
    a2=[[a[0],1]]
    for i in range(1,len(a)):
        if a2[-1][0]==a[i]:
            a2[-1][1]+=1
        else:
            a2.append([a[i],1])
    return a2

n,k=map(int,input().split())
s=list(input())
x=groupby(s)
l=len(x)
y=[x[i][1] for i in range(l)]

if x[0][0]=="0":
    r
    su=sum(y[:2*k])
    ans=su
    y.pop(0)
    l-=1
else:
    ans=0
su=sum(y[:2*k+1])
ans=max(ans,su)
l_sub=(l-(2*k+1))//2
if l_sub<=0:
    print(ans)
    exit()
for i in range(l_sub):
    su-=y[2*i]
    su-=y[2*i+1]
    su+=y[2*k+1+(2*i)]
    su+=y[2*k+1+(2*i+1)]
    ans=max(su,ans)
if 2*k+1+2*l_sub<l:
    su-=y[2*l_sub]
    su+=y[2*k+1+2*l_sub]
    ans=max(su,ans)
print(ans)


### FIXED CODE ###

from sys import exit
def groupby(a):
    a2=[[a[0],1]]
    for i in range(1,len(a)):
        if a2[-1][0]==a[i]:
            a2[-1][1]+=1
        else:
            a2.append([a[i],1])
    return a2

n,k=map(int,input().split())
s=list(input())
x=groupby(s)
l=len(x)
y=[x[i][1] for i in range(l)]

if x[0][0]=="0":
    su=sum(y[:2*k])
    ans=su
    y.pop(0)
    l-=1
else:
    ans=0
su=sum(y[:2*k+1])
ans=max(ans,su)
l_sub=(l-(2*k+1))//2
if l_sub<=0:
    print(ans)
    exit()
for i in range(l_sub):
    su-=y[2*i]
    su-=y[2*i+1]
    su+=y[2*k+1+(2*i)]
    su+=y[2*k+1+(2*i+1)]
    ans=max(su,ans)
#最後のところの判定っぽいな
if 2*k+1+2*l_sub<l:
    su-=y[2*l_sub]
    su-=y[2*l_sub+1]
    su+=y[2*k+1+2*l_sub]
    ans=max(su,ans)
print(ans)
s = input()
print(700　+ 100*int(s.count('o')))

### FIXED CODE ###

s=input()
print(700+int(s.count("o"))*100)
s=[int(input())]
i=0
while 1>0:
  if i%2>0:
    b=3*s[i]+1
  else:
    b=s[i]//2
  if b in s:
    print(i+1)
    break
  i+=1


### FIXED CODE ###

s=[int(input())]
i=0
while 1>0:
  if s[i]%2>0:
    b=3*s[i]+1
  else:
    b=s[i]//2
  if b in s:
    print(i+2)
    break
  i+=1
  s+=[b]
def solve():
  ar = raw_input().split(' ')
  A = int(ar[0])
  B = int(ar[1])
  C = int(ar[2])

  s = set([])
  sum = 0
  while True:
    sum = sum + A
    m = sum % B
    #print 'sum=',sum,'m=',m
    if (m == C): return 'Yes'
    if (m in s): return 'No'
    s.add(m)

if __name__ == '__main__' :
  print solve()

### FIXED CODE ###

def solve():
  ar = raw_input().split(' ')
  A = ar[0]
  B = ar[1]
  C = ar[2]
  if A[-1] == B[0] and B[-1] == C[0] : return 'YES'
  else: return 'NO'

if __name__ == '__main__' :
  print solve()
from itertools import product

N = int(input())

cnt = [0]*1000000000

for x in range(1,N):
    flag=0
    for y in range(1,N):
        if flag==1:
            break
        elif x*y>=10**4:
            break
        for z in range(1,N):
            if x*z>=10**4 or y*z>=10**4:
                flag=1
                break
            else:
                cnt[x**2 + y**2 + z**2 + x*y + y*z + z*x -1] += 1



for i in range(N):
    print(cnt[i])

### FIXED CODE ###

from itertools import product

N = int(input())

cnt = [0]*100000000

for x in range(1,N):
    flag=0
    for y in range(1,N):
        if x*y>=10**4:
            flag=1
            break
        for z in range(1,N):
            if flag==1:
                break
            elif x*z>=10**4 or y*z>=10**4:
                # flag=1
                break
            else:
                if x**2 + y**2 + z**2 + x*y + y*z + z*x <=10**4+1:
                    cnt[x**2 + y**2 + z**2 + x*y + y*z + z*x -1] += 1



for i in range(N):
    print(cnt[i])
N=int(input)
H=list(map(int,input().split()))
tmp=0
ans=0
for i in range(N-1):
  if H[i]>=H[i+1]:
    tmp+=1
    ans=max(ans,tmp)
  else:
    tmp=0
    break
print(ans)
    
  

### FIXED CODE ###

N=int(input())
H=list(map(int,input().split()))
tmp=0
ans=0
for i in range(N-1):
  if H[i]>=H[i+1]:
    tmp+=1
    ans=max(ans,tmp)
  else:
    tmp=0
    continue
print(ans)
a=input()
s=input()

if a>=3200: print(s)
else: print("red")

### FIXED CODE ###

a=int(input())
s=input()

if a>=3200: print(s)
else: print("red")
a,b = map(int,input().split())

for i in range(10**10):
  if (int(i*0.08)/int(i*0.1) == a/b):
    print(i)
    exit()

### FIXED CODE ###

import math
a,b = map(int,input().split())
sup = math.floor((a+1)/0.08)

for i in range(1,sup):
  if math.floor(i*0.08)== a and math.floor(i*0.1) == b:
    print(i)
    exit()
    
print(-1)
N, K, Q = map(int, input().split())
A = tuple([int(input()) for q in range(Q)])
# N人参加、初期状態で全員がKポイント
# 誰かが正解すると、それ以外の全員が1ポイント下がる
# i番目に正解したのはAi
counts = [0 for i in range(Q)]
for a in A:
  counts[a-1] += 1

for i in range(N):
  print('Yes' if (K - (Q - counts[i])) >= 1 else 'No')

### FIXED CODE ###

N, K, Q = map(int, input().split())
A = tuple([int(input()) for q in range(Q)])
# N人参加、初期状態で全員がKポイント
# 誰かが正解すると、それ以外の全員が1ポイント下がる
# i番目に正解したのはAi
counts = [0 for i in range(N)]
for a in A:
  counts[a-1] += 1

for i in range(N):
  print('Yes' if (K - (Q - counts[i])) >= 1 else 'No')
M=int(input())
s=[input() for _ in range(M)]
z=[]
for x in s:
    d=list(map(int, x.split()))
    for i in range(d[1]):
        z.append(d[0])
count = len(N)-1
while True:
    if sum(z)>9: 
        z=map(int, str(sum(z)))
        count += 1
    else:
        break
print(count)

### FIXED CODE ###

m = int(input())
d = [list(map(int, input().split())) for _ in range(m)]
print(sum([x[1] for x in d]) - 1 + (sum([x[0]*x[1] for x in d]) - 1) // 9)
from bisect import *
n, k = map(int, input().split())
a = list(map(int, input().split()))

posi = 0
nega = 0
zero = 0
p = []
m = []

for i in range(n):
    if a[i] > 0:
        p.append(a[i])
        posi += 1
    elif a[i] < 0:
        nega += 1
        m.append(-a[i])
    else:
        zero += 1

p.sort()
m.sort()

if k <= posi*nega:
    l = 0
    r = 10**18
    while r - l > 1:
        mid = l+(r-l)//2
        count = k
        for i in range(len(p)-1, -1, -1):
            count -= posi-bisect_left(m, (mid-1)//p[i]+1)
            if count <= 0:
                break
        if count <= 0:
            l = mid
        else:
            r = mid
        #print(r, l)

    print(-l)

elif k <= posi*nega+zero*(zero-1)//2+zero*(posi+nega):
    print(0)

else:
    o
    k -= posi*nega+zero*(zero-1)//2+zero*(posi+nega)
    l = 0
    r = 10**18
    while r - l > 1:
        mid = l+(r-l)//2
        count = k
        for i in range(len(p)):
            count -= max(bisect_right(p, (mid)//p[i])-i-1, 0)
            if count < 0:
                #continue
                break
        for i in range(len(m)):
            count -= max(bisect_right(m, (mid)//m[i])-i-1, 0)
            if count < 0:
                #continue
                break

        if count > 0:
            l = mid
        else:
            r = mid
    print(r)


### FIXED CODE ###

from bisect import *
n, k = map(int, input().split())
a = list(map(int, input().split()))

posi = 0
nega = 0
zero = 0
p = []
m = []

for i in range(n):
    if a[i] > 0:
        p.append(a[i])
        posi += 1
    elif a[i] < 0:
        nega += 1
        m.append(-a[i])
    else:
        zero += 1

p.sort()
m.sort()

if k <= posi*nega:
    l = 0
    r = 10**18
    while r - l > 1:
        mid = l+(r-l)//2
        count = k
        for i in range(len(p)-1, -1, -1):
            count -= nega-bisect_left(m, (mid-1)//p[i]+1)
            if count <= 0:
                break
        if count <= 0:
            l = mid
        else:
            r = mid
        #print(r, l)

    print(-l)

elif k <= posi*nega+zero*(zero-1)//2+zero*(posi+nega):
    print(0)

else:
    k -= posi*nega+zero*(zero-1)//2+zero*(posi+nega)
    l = 0
    r = 10**18
    while r - l > 1:
        mid = l+(r-l)//2
        count = k
        for i in range(len(p)):
            count -= max(bisect_right(p, (mid)//p[i])-i-1, 0)
            if count < 0:
                #continue
                break
        for i in range(len(m)):
            count -= max(bisect_right(m, (mid)//m[i])-i-1, 0)
            if count < 0:
                #continue
                break

        if count > 0:
            l = mid
        else:
            r = mid
    print(r)
a,b,k = map(int,input().split())
c = list(range(a,a+k))
d = list(range(b-k+1,b+1))
e = list(range(a,b+1))
if a>b or k == 0:
  print('')
elif a+k-1 < b-k+1:
  s = c+d
  ans_list = sorted(set(s))
else:
  ans_list = e
for num in ans_list:
  print(num)

### FIXED CODE ###

a,b,k = map(int,input().split())
if b+2 <= a+2*k:
  for i in range(a,b+1):
    print(i)
else:
  for i in range(a,a+k):
    print(i)
  for i in range(b+1-k,b+1):
    print(i)
A,B=map(int,input().split())
C=list(input())
count= 0
for i in range (B):
	count=count+int(C[i])
if count>=A:
	print("Yes")
else: print("No")

### FIXED CODE ###

import math
a, b = map(int, input().split()) 
print(math.ceil(a/b))
n = int(input())
testimony_table = [[] for _ in range(n)]

for i_witness in range(n):
    ai = int(input())
    for _ in range(ai):
        xij, yij= map(int, input().split())
        testimony_table[i_witness].append((xij-1,yij))

ans = 0
for i in range(2**n):
    isConflict = False

    for j_witness in range(n): # それぞれの桁について0か1かを判断したいので
        if (i >> j_witness) & 1 == 0: # j桁目が1かどうかをジャッジ
            continue


        for x_suspect, y_testimony in testimony_table[j_witness]:
            if ((i >> x_suspect) & 1) != y_testimony:
                isConflict = True
                break

        if isConflict:
            break
    if isConflict == False:
        ans = max(ans, bin(i).count("1"))

print(ans)




### FIXED CODE ###

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


def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

def mod_inv(a,mod):
    x = extgcd(a,mod)[0]
    return (mod+x%mod)%mod

ans = 0
MOD = 10**9 + 7

factorial = 1
for i in range(2,n):
    factorial = (factorial * i%MOD) %MOD

p = [0]*(n-1)
p[0] = 1 * factorial%MOD

for i in range(1,n-1):
    p[i] = p[i-1] + factorial*mod_inv(i+1,MOD)
    p[i] %= MOD

for i in range(n-1):
    ans += (x[i+1]-x[i])%MOD*p[i]
    ans %= MOD

print(int(ans))
n,*a=map(int,open(0).read().split())
s=1
if 0 in a:
    print(0)
    exit()
for i in a:
    s*=a
    if  s > 10**18:
        print(-1)
        exit()
print(s)

### FIXED CODE ###

n,*a=map(int,open(0).read().split())
s=1
if 0 in a:
    print(0)
    exit()
for i in a:
    s*=i
    if  s > 1e18:
        print(-1)
        exit()
print(s)
N=int(input())
lst=list(map(int,input().split()))
P=round(lst/N)
print(sum[(i-P)**2 for i in lst])

### FIXED CODE ###

N=int(input())
lst=list(map(int,input().split()))
P=round(sum(lst)/N)
print(sum([(i-P)**2 for i in lst]))
S=input()
T=input()
pront('YES' if S==T[::-1] else 'NO')

### FIXED CODE ###

S=input()
T=input()
print('YES' if S==T[::-1] else 'NO')
#151c
n,w=map(int,input().split())
ac=0
wa=0
wa_cnt=0
ac_flg=[0]*n
for i in range(w):
	p,s=input().split()
	p=int(p)-1
	if ac_flg[p]==1:
		continue
	else:
		if s=='AC':
			ac_flg[p]=1
			ac+=1
			wa[p] =wa_cnt
			wa_cnt=0
		else:
			wa_cnt+=1

wa_ans=0
for i in (n):
	wa_ans+=wa[i]
print(ac,wa)

### FIXED CODE ###

#151c
n,w=map(int,input().split())
ac=0
wa=[0]*n
wa_cnt=[0]*n
ac_flg=[0]*n
for i in range(w):
	p,s=input().split()
	p=int(p)-1
	if ac_flg[p]==1:
		continue
	else:
		if s=='AC':
			ac_flg[p]=1
			ac+=1
			wa[p] =wa_cnt[p]
			#wa_cnt=0
		else:
			wa_cnt[p]+=1

wa_ans=0
for i in range(n):
	wa_ans+=wa[i]

print(ac,wa_ans)
n=int(input())
if n%2==1:print(0);exit()
A=0
add=10
while n>=add:
    A +=n//add
    add *=5
print(sum(A))

### FIXED CODE ###

n=int(input())
if n%2==1:print(0);exit()
A=0
add=10
while n>=add:
    A +=n//add
    add *=5
print(A)
N, K = map(int, input().split())
num = list(map(int, input().split()))
 
# 各サイコロの期待値を出す
expect = []
for i in range(N):
  expect.append((1 + num[i]) / 2)
  print(expect)
 
# 累積和を作る
cs = [0]
for i in range(N):
    cs.append(cs[i]+expect[i])
    print(cs)

for i in range(K, N+1): # 配列0番目に初期値0が増えてるので1足す
  if max < cs[i] - cs[i-K]:
    max = cs[i] - cs[i - K]
print(max)

### FIXED CODE ###

N, K = map(int, input().split())
num = list(map(int, input().split()))
 
# 各サイコロの期待値を出す
expect = []
for i in range(N):
  expect.append((1 + num[i]) / 2)
 
# 累積和を作る
cs = [0]
for i in range(N):
    cs.append(cs[i]+expect[i])

max = 0
for i in range(K, N+1): # 配列0番目に初期値0が増えてるので1足す
  if max < cs[i] - cs[i-K]:
    max = cs[i] - cs[i - K]
print(max)