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

x, k, d = map(int, input().split())
ans = 1000000000000000
for i in range(k+1):
    ans = abs(min(ans, x+d*(2*i-k)))
    if ans < d:
        break
print(ans)

### FIXED CODE ###

x, k, d = map(int, input().split())
x = abs(x)
ans = 1000000000000000
m = x // d
if m > k:
    print(abs(x-k*d))
else:
    if (k%2==0 and m%2==1) or (k%2==1 and m%2==0):
        m += 1
    ans = min(ans,x-m*d)
    """
    if m+2 <= k:
        ans = min(ans,ans+2*d)
        ans = min(ans,ans-2*d)
        """
    print(abs(ans))
### BUGGY CODE ###

#coding:utf-8
n,m = map(int,input().split())
List = list(map(int,input().split()))

class Tree:
    def __init__(self,par):
        self.par = par

forest = [Tree(i) for i in range(n+1)]
rank = [0 for i in range(n+1)]

def unite(x,y):
    while forest[x].par != x:
        x = forest[x].par
    a = rank[x]
    
    while forest[y].par != y:
        y = forest[y].par
    b = rank[y]
    
    if a <= b:
        if a == b:
            rank[x] += 1
        forest[y].par = x
    else:
        forest[x].par = y


def Find(x,y):
    Q = []
    P = []
    while forest[x].par != x:
        x = forest[x].par
        Q.append(x)
            
    while forest[y].par != y:
        y = forest[y].par
        P.append(y)
    for xi in Q:
        forest[xi].par = x
        rank[xi] = 1
    for yi in P:
        forest[yi].par = y
        rank[yi] = 1
    if x == y:
        return 1
    else:
        return 0
    
cnt = 0
for i in range(m):
    x,y = map(int,input().split())
    unite(x,y)

for i in range(1,n+1):
    cnt += Find(i,List[i-1])
print(cnt)
    


### FIXED CODE ###

#coding:utf-8

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

class UnionFind3:
    def __init__(self, size):
        # 負の値はルート (集合の代表) で集合の個数
        # 正の値は次の要素を表す
        self.table = [-1 for i in range(size)]

    # 集合の代表を求める
    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            # 経路の圧縮
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    # 併合
    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                # 小さいほうが個数が多い
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return 1
        return 0


cnt = 0
tree = UnionFind3(n)
for i in range(m):
    x,y = map(int,input().split())
    tree.union(x-1,y-1)

for i in range(n):
    a = tree.find(i)
    b = tree.find(List[i]-1)
    if a == b:
        cnt += 1

print(cnt)
### BUGGY CODE ###

import itertools as it
N=input()
a_l=[int(i) for i in input().split()]

def xor(i,j):
    l=len(str(format(max(i,j),'b')))
    i2=str(format(i,'b').zfill(l))
    j2=str(format(j,'b').zfill(l))
    ans=0
    for k in range(l):
        if i2[k]!=j2[k]:
            ans+=2**(l-k-1)
    yield ans

sum1=0
for (i,j) in it.combinations(a_l, 2):
    for k in xor(i,j):
        sum1+=k
print(sum1%(7+10**9))

### FIXED CODE ###

n=int(input())
lis=list(map(lambda x:format(int(x),'b'),input().split()))
l=0
for i in range(n):
    l=max(l,len(lis[i]))

d0=[0]*60
d1=[0]*60

for i in range(n):
    lis[i]=lis[i].zfill(l)
    for j in range(l):
        if lis[i][-j-1]=='0':
            d0[j]+=1
        else:
            d1[j]+=1

ans=0
for i in range(60):
    ans+=(d0[i]*d1[i]*2**i)%(10**9+7)
print(ans%(10**9+7))
### BUGGY CODE ###

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

a = 0

for i in range(n):
  if s[i]=='R':
    for j in range(n):
      if s[j]=='G':
        for k in range(n):
          if s[k]=='B':
            if i<j<k:
              if (j-i)!=(k-j):
                a = a + 1
            elif i<k<j:
              if (k-i)!=(j-k):
                a = a + 1
            elif j<i<k:
              if (i-j)!=(k-i):
                a = a + 1
            elif j<k<i:
              if (k-j)!=(i-k):
                a = a + 1
            elif k<i<j:
              if (i-k)!=(j-i):
                a = a + 1
            elif k<j<i:
              if (j-k)!=(i-j):
                a = a + 1
          
print(a)	


### FIXED CODE ###

n = int(input())
s = input()
 
count = {"R":0,"G":0,"B":0}
for c in s:
    count[c] += 1
 
r,g,b = count.values()
ans = r*g*b
for i in range(1,(n-1)//2+1): #1から
    for rgb in zip(s,s[i:],s[i*2:]):  #rgbに連続した三つのリストの要素を入れ込む
        if len(set(rgb)) == 3:  #リストrgbをセットにまとめ、長さが
            ans -=1
print(ans)
### BUGGY CODE ###

import sys
readline = sys.stdin.buffer.readline
from collections import deque
INF = float('inf')


def main():
    H, W, K = map(int, readline().split())
    # いつものパターンと問題文のi,jが逆なので、
    # 問題文のxを変数yに、問題文のyを変数xに代入している
    sy, sx, gy, gx = map(int, readline().split())
    sy -= 1
    sx -= 1
    gx -= 1
    gy -=1
    lake = [list(readline().decode('utf-8').strip()) for _ in range(H)]
    dist = [[INF] * (W+2) for _ in range(H+2)]
    dxy = ((1, 0), (0, 1), (-1, 0), (0, -1))
    Q = deque()
    Q.append((sy, sx, 0))
    dist[sy][sx] = 0
    while Q:
        y,x,d = Q.popleft()
        if y == gy and x == gx:
            print(d)
            sys.exit()
        for dx,dy in dxy:
            n_y = y
            n_x = x
            for _ in range(K):
                n_y +=dy
                n_x +=dx

                if 0<=n_x<W and 0<=n_y<H and lake[n_y][n_x] != '@':
                    if 0<=dist[n_y][n_x]<d:
                        break
                    elif dist[n_y][n_x] == INF:
                        dist[n_y][n_x] = d + 1
                        Q.append((n_y,n_x,d+1))
                    else:
                        continue

                else:
                    break
    print('-1')

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
from collections import deque
 
H, W, K = map(int,readline().split())
x1, y1, x2, y2 = map(int,readline().split())
x1 -= 1; y1 -= 1; x2 -= 1; y2 -= 1
C = read().split()

dist = [[-1]*W for i in range(H)]
dist[x1][y1] = 0
d = deque([[x1, y1]])
dxy= [[1, 0], [0, 1], [-1, 0], [0, -1]]
while d:
  x, y = d.popleft()
  if (x, y) == (x2, y2):
    print(dist[x][y])
    quit()
  for dx, dy in dxy:
    xx = x; yy = y
    for i in range(K):
      xx += dx; yy += dy
      if 0<=xx<H and 0<=yy<W and C[xx][yy]!='@':
        if 0 <= dist[xx][yy] <= dist[x][y]:
          break
        if dist[xx][yy] == -1:
           d.append([xx, yy])
        dist[xx][yy] = dist[x][y] + 1
      else:
        break

print(-1)
### BUGGY CODE ###

n,k=map(int,input().split())
h=sorted([int(input()) for _ in range(n)])
a=10**9
for i in range(n-k+1):
    h1=h[i:i+k]
    a1=h1[-1]-h1[0]
    a=min(a,a1)
print(a)

### FIXED CODE ###

n,k=map(int,input().split())
h=sorted([int(input()) for _ in range(n)])
a=10**9
for i in range(n-k+1):
    a1=h[i+k-1]-h[i]
    a=min(a,a1)
print(a)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

n, q = map(int, input().split())
tree = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
ans = [0] * n
for _ in range(q):
    p, x = map(int, input().split())
    ans[p-1] += x
def dfs(c, parent):
    for child in tree[c]:
        if child == parent:
            continue
        else:
            ans[child] += ans[c]
            dfs(child, c)
dfs(0, 0)
print(*ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline #for input speed
sys.setrecursionlimit(10**6) #for deep recursion
n, q = map(int, input().split())

tree_index = [[] for _ in range(n)]
for i in range(n-1):
  a,b = map(int, input().split())
  a -= 1
  b -= 1
  tree_index[a].append(b) # a<bとは限らないため、双方向にする
  tree_index[b].append(a)
ans = [0] * n
for i in range(q):
  p, x = map(int, input().split())
  ans[p-1] += x
def dfs(cur, par):
    for chl in tree_index[cur]:
      if chl == par: #parentとchildが等しい時はスキップ
        continue
      ans[chl] += ans[cur] 
      dfs(chl, cur)
dfs(0, -1)
print(*ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
cnt = 0
a.sort();b.sort();c.sort()
for i in range(n):
    for j in range(n):
        if a[i] < b[j]:
            for k in range(n):
                if b[j] < c[k]:
                    cnt += n-k
                    break
print(cnt)

### FIXED CODE ###

import bisect
import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
cnt = 0
a.sort()
c.sort()
for i in range(n):
    cnt += (bisect.bisect_left(a, b[i])) * (n-bisect.bisect_right(c, b[i]))
print(cnt)
### BUGGY CODE ###

import itertools
n = int(input())
a = list(map(int,input().split()))
ans = 0
m = 10**9 + 7
for item in itertools.combinations(a, 2):
    ans += item[0] * item[1]
print(ans % m)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
c = 10 ** 9 + 7
ans = 0
s = 0
for i in range(n-1, -1, -1):
    ans += s * a[i]
    s += a[i]
print(ans % c)
### BUGGY CODE ###

N = int(input())
S = input()
cnt = 0

for i in range(1000):
    target = str(i).zfill(3)
    j = 0
    for s in S:
        if s == target[j]:
            j += 1
        if j==3:
            cnt += 1
            break
print(cnt)

### FIXED CODE ###

N = int(input())
S = input()
cnt = 0

for i in range(100):
    num_set = set()
    target = str(i).zfill(2)
    j = 0
    for s in S:
        if j<2 and s == target[j]:
            j += 1
        elif j==2:
            num_set.add(s)
    cnt += len(num_set)
print(cnt)
### BUGGY CODE ###

import math

n, m =map(int,input().split()) 
a =list(map(int, input().split()))
b =[math.ceil(i/2) for i in a]

otoku = 0

while m >0:
    otoku =b.index(max(b))
    a[otoku] = a[otoku]-b[otoku]
    b[otoku] = math.ceil(a[otoku]/2)

    m = m-1
    if sum(a)==0:
        break
print(sum(a))

### FIXED CODE ###

import math
import heapq

n, m =map(int,input().split()) 
a =list(map(int, input().split()))
h =[]
for i in a:
    heapq.heappush(h, i*(-1))


while m >0:
    heru = math.ceil((heapq.heappop(h))/2)
    heapq.heappush(h,heru)
    m = m-1
print((-1)*sum(h))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
for i in range(N):
  print(A.count(i+1))

### FIXED CODE ###

def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    ans = [0]*N
    for i in A:
        ans[i-1] += 1
    for j in ans:
        print(j)
resolve()
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
B=sorted(A)
for b in B:
    if b == len(B):
        print(A.index(b)+1)
    else:
        print(A.index(b)+1,end=" ")


### FIXED CODE ###

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

d=[0 for n in range(N)]
for n in range(N):
    d[A[n]-1] = str(n+1)

print(" ".join(d))
### BUGGY CODE ###

from functools import reduce
import math

def main():
    # 文字列の2進数を数値にする
    # '101' → '5'
    # 文字列の頭に'0b'をつけてint()にわたす
    # binary = int('0b'+'101',0)

    # 2進数で立っているbitを数える
    # 101(0x5) → 2
    # cnt_bit = bin(5).count('1')
    
    # N! を求める
    # f = math.factorial(N)
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    INF = float("inf")
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    N = input().rstrip()
    a = list(int(_) for _ in input().split())
    b = []
    for i in range(len(a)):
        b.append(a[i])
        b = b[::-1]
    print(' '.join(str(_) for _ in b))
    
if __name__ == '__main__':
    main()


### FIXED CODE ###

from functools import reduce
import math

def main():
    # 文字列の2進数を数値にする
    # '101' → '5'
    # 文字列の頭に'0b'をつけてint()にわたす
    # binary = int('0b'+'101',0)

    # 2進数で立っているbitを数える
    # 101(0x5) → 2
    # cnt_bit = bin(5).count('1')
    
    # N! を求める
    # f = math.factorial(N)
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    INF = float("inf")
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    N = int(input().rstrip())
    a = list(int(_) for _ in input().split())
    b = []
    for i in range(N):
        if((N-1)-i*2>0):
            b.append(a[(N-1)-i*2])
        else:
            b.append(a[max(0,i*2-N)])
    print(' '.join(str(_) for _ in b))
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline

from heapq import heappush, heappop

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

A = sorted(A)
F = sorted(F)[::-1]

h = []
for i in range(N):
  a, f = A[i], F[i]
  heappush(h, (- a * f, a, f))
  
while K > 0:
  x, y, z = heappop(h)
  if x == 0:
    break
  else:
    heappush(h, (- (y - 1) * z, (y - 1), z))
    K -= 1
    
x, y, z = heappop(h)
print(-x)

### FIXED CODE ###

import sys
read=sys.stdin.buffer.read
readline=sys.stdin.buffer.readline
readlines=sys.stdin.buffer.readlines

N,K=map(int,readline().split())
A=list(map(int,readline().split()))
F=list(map(int,readline().split()))
#print(N,K)
#print("A:",A)
#print(F)

A.sort()
F.sort(reverse=True)
#print("A:",A)
#print("F:",F)

left=-1
right=10**18
#right=10**3

while left+1<right:
  mid=(left+right)//2
  tmp=[0]*(N)
  for i in range(N):
    tmp[i]=max(A[i]-mid//F[i],0)
    
  if sum(tmp)<=K:
    right=mid
  else:
    left=mid
  #print("mid:",mid,",tmp:",tmp)
#print("left:",left,",mid:",mid,",right:",right)
print(right)
### BUGGY CODE ###

import numpy as np

MOD = 10 ** 9 + 7

H, W = map(int, input().split())
count = np.ones((H, W), dtype=np.int)

row = input()
for w in range(1, W):
  if row[w] == '#':
    count[0, w:] = 0
    break

flag = True
for h in range(1, H):
  row = input()
  count[h] = count[h-1]
  if flag and row[0] == '#':
    count[h:, 0] = 0
    flag = False
  period = 0
  for w in range(1, W):
    if row[w] == '#':
      count[h, period : w] = count[h, period : w].cumsum() % MOD
      count[h, w] = 0
      period = w + 1
  count[h, period:] = count[h, period:].cumsum() % MOD
print(count[-1, -1])

### FIXED CODE ###

MOD = 10 ** 9 + 7

H, W = map(int, input().split())
count = [0] * W

row = input()
for w in range(W):
  if row[w] == '#':
    break
  else:
    count[w] = 1

for h in range(1, H):
  row = input()
  if row[0] == '#':
    count[0] = 0
  for w in range(1, W):
    if row[w] == '#':
      count[w] = 0
    else:
      count[w] = (count[w-1] + count[w]) % MOD
print(count[-1])
### BUGGY CODE ###

import heapq
Q = int(input())
Query = [[int(_) for _ in input().split()] for _ in range(Q)]
H1 = []
H2 = []
a = b = 0
for query in Query:
    if query[0] == 1:
        m0 = query[1]
        if len(H1) == len(H2):
            if len(H2):
                m1 = heapq.heappop(H2)
                m0, m1 = sorted([m0, m1])
                heapq.heappush(H1, -m0)
                heapq.heappush(H2, m1)
            else:
                heapq.heappush(H1, -m0)
        else:
            m1 = -heapq.heappop(H1)
            m0, m1 = sorted([m0, m1])
            heapq.heappush(H1, -m0)
            heapq.heappush(H2, m1)
        b += query[2]
    else:
        x = -H1[0]
        print(x, x * len(H1) + sum(H1) + sum(H2) - x * len(H2) + b)


### FIXED CODE ###

import heapq
import sys
input = sys.stdin.readline
Q = int(input())
Query = [[int(_) for _ in input().split()] for _ in range(Q)]
H1 = []
H2 = []
a = b = sum1 = sum2 = 0
for query in Query:
    if query[0] == 1:
        m0 = query[1]
        if len(H1) == len(H2):
            if len(H2):
                m1 = heapq.heappop(H2)
                sum2 -= m1
                m0, m1 = sorted([m0, m1])
                heapq.heappush(H1, -m0)
                heapq.heappush(H2, m1)
                sum1 -= m0
                sum2 += m1
            else:
                heapq.heappush(H1, -m0)
                sum1 -= m0
        else:
            m1 = -heapq.heappop(H1)
            sum1 += m1
            m0, m1 = sorted([m0, m1])
            heapq.heappush(H1, -m0)
            heapq.heappush(H2, m1)
            sum1 -= m0
            sum2 += m1
        b += query[2]
    else:
        x = -H1[0]
        print(x, x * len(H1) + sum1 + sum2 - x * len(H2) + b)
### BUGGY CODE ###


if __name__ == "__main__":
    H, W = map(int, input().split(" "))
    if (W % 3 == 0) or (H % 3 == 0):
        print("0")
        exit()
    else:
        Ans = H*W
        for x in range(1, W):
            for y in range(1, H):
                # |--
                S1 = H*x
                S2 = (W - x) * y
                S3 = H*W - (S1 + S2)
                Ans1 = max(S1, S2, S3) - min(S1, S2, S3)

                # ---
                #  |
                S1 = y*W
                S2 = (H - y) * x
                S3 = H*W - (S1 + S2)
                Ans2 = max(S1, S2, S3) - min(S1, S2, S3)


                # | |
                S1 = x*H
                S2 = (W - x) // 2 * H
                S3 = H*W - (S1 + S2)
                Ans3 = max(S1, S2, S3) - min(S1, S2, S3)

                # --
                # --
                S1 = y*W
                S2 = (H - y) // 2 * W
                S3 = H*W - (S1 + S2)
                Ans4 = max(S1, S2, S3) - min(S1, S2, S3)

                # 最小値を更新
                Ans = min(Ans, Ans1, Ans2, Ans3, Ans4)

                # print("debug:(x, y) => (", x, y, ")")
                # print(Ans)
        print(Ans)
        exit()


### FIXED CODE ###


def getMinSDiff(H, W):
    Ans = H*W
    for x in range(1, W):
        # |--
        S1 = H*x
        S2 = (W - x) * (H // 2)
        S3 = H*W - (S1 + S2)
        Ans1 = max(S1, S2, S3) - min(S1, S2, S3)

        # | |
        S1 = x*H
        S2 = (W - x) // 2 * H
        S3 = H*W - (S1 + S2)
        Ans2 = max(S1, S2, S3) - min(S1, S2, S3)

        # 最小値を更新
        Ans = min(Ans, Ans1, Ans2)
    return Ans

if __name__ == "__main__":
    H, W = map(int, input().split(" "))
    if (W % 3 == 0) or (H % 3 == 0):
        print("0")
        exit()
    else:
        Ans = min(getMinSDiff(H, W), getMinSDiff(W, H))
        print(Ans)
        exit()
### BUGGY CODE ###

import sys
from collections import deque  # 双方向キュー
from collections import defaultdict  # 初期化済み辞書
from heapq import heapify, heappush, heappop, heappushpop  # プライオリティキュー
from bisect import bisect_left, bisect_right  # 二分探索
#import numpy as np  # 1.8.2
#import scipy  # 0.13.3

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))
MOD = int(1e+9) + 7

def main():
    N, M = i2nn()
    S = i2nn()
    T = i2nn()

    rui = [[0] * (M + 1) for _ in range(N + 1)]
    cnt = [[0] * (M) for _ in range(N)]

    for i, s in enumerate(S):
        for j, t in enumerate(T):
            c = 0
            if s == t:
                c += rui[i][j] + 1
            cnt[i][j] = c
            rui[i+1][j+1] = rui[i+1][j] + rui[i][j+1] - rui[i][j] + c

    n = 1
    for v in cnt:
        n = (n + sum(v)) % MOD

    #print(rui)
    #print(cnt)
    print(n)

main()


### FIXED CODE ###

import sys
from collections import deque  # 双方向キュー
from collections import defaultdict  # 初期化済み辞書
from heapq import heapify, heappush, heappop, heappushpop  # プライオリティキュー
from bisect import bisect_left, bisect_right  # 二分探索
#import numpy as np  # 1.8.2
#import scipy  # 0.13.3

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))
MOD = int(1e+9) + 7

def main():
    N, M = i2nn()
    S = i2nn()
    T = i2nn()

    rui = [[0] * (M + 1) for _ in range(N + 1)]
    #cnt = [[0] * (M) for _ in range(N)]

    n = 1
    for i, s in enumerate(S):
        for j, t in enumerate(T):
            c = 0
            if s == t:
                c += rui[i][j] + 1
            #cnt[i][j] = c
            rui[i+1][j+1] = (rui[i+1][j] + rui[i][j+1] - rui[i][j] + c) % MOD
            n = (n + c) % MOD

    #for v in cnt:
    #    n = (n + sum(v)) % MOD

    #print(rui)
    #print(cnt)
    print(n)

main()
### BUGGY CODE ###

h,w = list(map(int, input().split()))
b = [input() for i in range(h)]
a =[]
for i in range(h):
    a.append(list(b[i]))

yoko = [0]*w
a.insert(0,yoko)
a.append(yoko)
for i in range(h+2):
    a[i].insert(0,0)
    a[i].append(0)
ans = 0
flag = 0
while flag!=h*w:
    flag = 0
    tmp= [[0]*w for k in range(h)]
    for i in range(1,h+1):
        for j in range(1,w+1):
            if a[i][j]=='#':
                tmp[i-1][j-1]=1
                flag += 1
    if flag != h*w:
        for i in range(h):
           for j in range(w):
               if tmp[i][j]==1:
                   a[i+1][j]='#'
                   a[i+1][j+2]='#'
                   a[i][j+1]='#'
                   a[i+2][j+1]='#'
        ans += 1
print(ans)    

### FIXED CODE ###

r, c = map(int, input().split())

cc = [input() for i in range(r)]

from collections import deque


# 縦がｙ 横がx　だから座標はy,xて書く
st=[]
for i in range(r):
    for j in range(c):
        if cc[i][j]=="#":
            st.append([i,j])

# 保留スタックtodoにスタートの位置情報を入れる
todo=deque(st)
# 検知済みリストseenを-1で初期化 (何も検知してないてこと)
seen=[[-1 for i in range(c)] for j in range(r)]

# seenにはどんだけの手数でそこに到達できるかを入れる
# 例えばスタート地点は手数0でいけるから0を入れる
for i in range(len(st)):
    seen[st[i][0]][st[i][1]]=0

# 4方向の移動リスト これ使って移動していく
ido=[[1,0],[0,1],[-1,0],[0,-1]]
m=0
# 保留リストtodoが空になるまでやる
while todo:
    y, x=todo.popleft() # 現在地は保留からの先頭とりだす
    for i in range(4): # 現在地から4方向を見る
        ny, nx=y+ido[i][0], x+ido[i][1] # 現在地から隣の座標
        # 隣の座標が区画をはみ出さないかつ、検知してないときに
        if 0<=ny<r and 0<=nx<c and seen[ny][nx]==-1 and cc[ny][nx]!="#":
            # 隣に行けるということなので検知してその手数を格納
            seen[ny][nx]=seen[y][x]+1 # 手数＝前の地点の手数+1
            todo.append([ny,nx]) # 保留リストにも入れとく
            if seen[ny][nx]>=m:
                m=seen[ny][nx]
       

print(m)
### BUGGY CODE ###

N,M = map(int, input().split())
arr = [int(input()) for _ in range(0,M)]

arr = [-1]+arr+[N+1]

from operator import mul
from functools import reduce

def factorial(n):
    return reduce(mul, range(n, 0, -1), 1)
  
count = 0

for i in range(0,len(arr)-1):
    start,end = arr[i],arr[i+1]
    span = end - start - 2 # the first step is taken by a certain step (with no choice)
    if span < 0:
        count = 0 # impossible
        break 
    nptn = int(span/2)
    regional_count = 0

    for k in range(0,nptn+1):
        regional_count += factorial(span-k) // factorial(k) // factorial(span-2*k)
    
    if count == 0:
        count += regional_count
    else:
        count *= regional_count
print(count % 1000000007)

### FIXED CODE ###

N,M = map(int, input().split())
arr = [int(input()) for _ in range(0,M)]
MOD = 10**9 + 7
stairs = [True for _ in range(0,N+1)]
for x in arr:
    stairs[x] = False

dp = [0 for _ in range(0,N+1)]

dp[0] = 1 if 0 not in arr else 0
dp[1] = 1 if 1 not in arr else 0

for i in range(2,N+1):
    if dp[i-1] == 0 and dp[i-2] == 0:
        break
    if stairs[i-1]: dp[i] += dp[i-1]
    if stairs[i-2]: dp[i] += dp[i-2]

    dp[i] %= MOD

print(dp[-1] % MOD)