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

def main():

    from collections import Counter

    N = int(input())
    a = list(map(float, input().split()))

    dp = [[[0]*(N+1) for _ in range(N+1)] for _ in range(N+1)]
    c = Counter(a)
    c1 = c[1]
    c2 = c[2]
    c3 = c[3]

    # メモ化再帰ではpypy3でもTLEするのでforループを使う
    # j==k==0の場合を計算 → k==0の場合を計算 → 一般の場合を計算
    for k in range(c3+1):
        for j in range(c3+c2-k+1):
            for i in range(N-j-k+1):
                if i+j+k == 0:
                    continue
                else:
                    tmp = N
                    if i > 0: # IndexError防止
                        tmp += dp[i-1][j][k]*i
                    if j > 0:
                        tmp += dp[i+1][j-1][k]*j
                    if k > 0:
                        tmp += dp[i][j+1][k-1]*k
                    dp[i][j][k] = tmp/(i+j+k) # 割り算をまとめないとTLE

    print(dp[c1][c2][c3])

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    from collections import Counter

    N = int(input())
    a = list(map(float, input().split()))

    dp = [[[0]*(N+1) for _ in range(N+1)] for _ in range(N+1)]
    c = Counter(a)

    # メモ化再帰ではpypy3でもTLEするのでforループを使う
    # j==k==0の場合を計算 → k==0の場合を計算 → 一般の場合を計算
    for k in range(c[3]+1):
        for j in range(c[3]+c[2]-k+1):
            for i in range(N-j-k+1):
                if i+j+k == 0:
                    continue
                else:
                    tmp = N
                    if i > 0: # IndexError防止
                        tmp += dp[i-1][j][k]*i
                    if j > 0:
                        tmp += dp[i+1][j-1][k]*j
                    if k > 0:
                        tmp += dp[i][j+1][k-1]*k
                    dp[i][j][k] = tmp/(i+j+k) # 割り算をまとめないとTLE

    print(dp[c[1]][c[2]][c[3]])

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

N = int(input())
A = [list(map(lambda x: int(x) - 1, input().split()))[::-1] for _ in range(N)]

for day in range(N * (N - 1) // 2):
    did_play = [0] * N
    for i in range(N):
        if did_play[i] or A[i] == []:
            continue
        opponent = A[i][-1]
        if A[opponent][-1] == i and not did_play[opponent]:
            A[i].pop()
            A[opponent].pop()
            did_play[i] = 1
            did_play[opponent] = 1
    if all(a == [] for a in A):
        print(day + 1)
        break
else:
    print(-1)


### FIXED CODE ###

from sys import setrecursionlimit


def encode(i, j):
    if i < j:
        i, j = j, i
    return i * (i - 1) // 2 + j + 1


def dfs(v):
    if visited[v] == 2:
        return dp[v]
    visited[v] = 1
    for nv in g[v]:
        if visited[nv] == 1:
            print(-1)
            exit()
        dp[v] = max(dp[v], dfs(nv) + 1)
    visited[v] = 2
    return dp[v]


setrecursionlimit(10 ** 6)
N = int(input())
GAMES_CNT = N * (N - 1) // 2
g = [[] for _ in range(GAMES_CNT + 1)]
for i in range(N):
    orig = 0
    for j in map(lambda x: int(x) - 1, input().split()):
        dest = encode(i, j)
        g[orig].append(dest)
        orig = dest
dp = [0] * (GAMES_CNT + 1)
visited = [0] * (GAMES_CNT + 1)
print(dfs(0))
### BUGGY CODE ###

def main():
    import sys
    from itertools import accumulate
    input=sys.stdin.buffer.readline
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    for _ in range(k):
        b=[0]*n
        for i,t in enumerate(a):
            if(j:=i-t)<0:j=0
            b[j]+=1
            if(j:=i-~t)<n:b[j]-=1
        a=list(accumulate(b))
        if min(a)==n:break
    print(' '.join(map(str,a)))
main()

### FIXED CODE ###

def main():
    n,k,*a=map(int,open(0).read().split())
    for _ in range(k):
        b=[0]*n
        m=10**18
        for i,t in enumerate(a):
            if t<m:m=t
            b[max(0,i-t)]+=1
            if i-~t<n:b[i-~t]-=1
        if m>=n:break
        for i in range(n-1):b[i+1]+=b[i]
        a=b
    print(' '.join(map(str,a)))
main()
### BUGGY CODE ###

class SegmentTreeMax():
  def __init__(self,n,init):
    self.offset=2**((n-1).bit_length())
    self.tree=[init]*(2*self.offset)
    self.init=init
  def update(self,pos,val):
    pos+=self.offset
    self.tree[pos]=val
    while pos>1:
      pos=pos//2
      self.tree[pos]=max(self.tree[2*pos],self.tree[2*pos+1])
  def query(self,l,r):
    l+=self.offset
    r+=self.offset
    ret=self.init
    while l<=r:
      ret=max(ret,self.tree[r])
      r=(r-1)//2
      ret=max(ret,self.tree[l])
      l=(l+1)//2
    return ret

n=int(input())
h=list(map(int,input().split()))
a=list(map(int,input().split()))
st=SegmentTreeMax(max(h)+1,0)
for i in range(n):
  val=a[i]+st.query(0,h[i]-1)
  st.update(h[i],val)
print(max(st.tree))

### FIXED CODE ###

class SegmentTreeMax():
  def __init__(self,n,init):
    self.offset=2**((n-1).bit_length())
    self.tree=[init]*(2*self.offset)
    self.init=init
  def update(self,pos,val):
    pos+=self.offset
    self.tree[pos]=val
    while pos>1:
      pos=pos//2
      self.tree[pos]=max(self.tree[2*pos],self.tree[2*pos+1])
  def query(self,l,r):
    l+=self.offset
    r+=self.offset
    ret=self.init
    while l<=r:
      ret=max(ret,self.tree[r])
      r=(r-1)//2
      ret=max(ret,self.tree[l])
      l=(l+1)//2
    return ret

n=int(input())
h=list(map(int,input().split()))
a=list(map(int,input().split()))
st=SegmentTreeMax(max(h)+1,0)
for i in range(n):
  val=a[i]+st.query(0,h[i]-1)
  st.update(h[i],val)
print(max(st.tree))
### BUGGY CODE ###


n = int(input())
l = list(map(int,input().split()))
#print(n)
#print(l)

ans = 0
for i in range(n):
    for j in range(n):
        if i != j:
            if l[i] % l[j] == 0:
                break
    else:
        ans += 1

print(ans)


### FIXED CODE ###

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

num = max(l)+1
rcd = [0 for _ in range(num)]

for v in l:
    rcd[v] += 1

unq = []
for w in range(num):
    if rcd[w] == 1:
        unq.append(w)
#print(unq)

rcd = [0 for _ in range(num)]
l = set(l)
for x in l:
    for y in range(2*x, num, x):
        rcd[y] = 1
#print(rcd)

ans = 0
for z in unq:
    if rcd[z] == 0:
        ans += 1
print(ans)
### BUGGY CODE ###

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

inputs = input().split(' ')
N = int(inputs[0])
M = int(inputs[1])
cards = input().split(' ')
cards = [int(x) for x in cards]
cards.sort()

for _ in range(M):
    inputs = input().split(' ')
    B = int(inputs[0])
    C = int(inputs[1])
    for i in range(B):
        if cards[i] >= C:
            break
        else:
            cards[i] = C
    cards.sort()

print(sum(cards))

### FIXED CODE ###

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

inputs = input().split(' ')
N = int(inputs[0])
M = int(inputs[1])
cards = input().split(' ')
cards = [int(x) for x in cards]
cards.sort()

BC = []
for _ in range(M):
    inputs = input().split(' ')
    inputs = [int(x) for x in inputs]
    BC.append({'B': inputs[0], 'C': inputs[1]})

idx = 0
BC.sort(key=lambda x: x['C'], reverse=True)
for bc in BC:
    if idx >= N:
        break
    for _ in range(bc['B']):
        c = bc['C']
        if cards[idx] >= c:
            break
        else:
            cards[idx] = c
            idx += 1
            if idx >= N:
                break

print(sum(cards))
### BUGGY CODE ###

class UnionFind():
	def __init__(self, N):
		self.N = N # データ数
		self.d = [-1]*N # 親の番号，根の場合は，-(集合の要素数)

	def find(self, x):
		if self.d[x]<0:
			return x
		else:
			self.d[x] = self.find(self.d[x])
			return self.d[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x==y: return False
		if self.d[x] > self.d[y]: x,y = y,x
		self.d[x] += self.d[y]
		self.d[y] = x
		return True

	def same(self, x, y):
		return self.find(x)==self.find(y)

	def size(self, x):
		return -self.d[self.find(x)]


n,m,k = map(int, input().split())
uf = UnionFind(n)
G_friend = [[] for i in range(n)]
for i in range(m):
    a,b = map(lambda x: int(x)-1, input().split())
    G_friend[a].append(b)
    G_friend[b].append(a)
    uf.union(a,b)

num_block = [0]*n
for i in range(k):
    a,b = map(lambda x: int(x)-1, input().split())
    if uf.same(a,b) and b not in G_friend[a]:
        num_block[a] += 1
        num_block[b] += 1

ans = [0]*n
for i in range(n):
    ans[i] = uf.size(i) - len(G_friend[i]) - 1 - num_block[i]
print(*ans)

### FIXED CODE ###

class UnionFind():
	def __init__(self, N):
		self.N = N # データ数
		self.d = [-1]*N # 親の番号，根の場合は，-(集合の要素数)

	def find(self, x):
		if self.d[x]<0:
			return x
		else:
			self.d[x] = self.find(self.d[x])
			return self.d[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x==y: return False
		if self.d[x] > self.d[y]: x,y = y,x
		self.d[x] += self.d[y]
		self.d[y] = x
		return True

	def same(self, x, y):
		return self.find(x)==self.find(y)

	def size(self, x):
		return -self.d[self.find(x)]


n,m,k = map(int, input().split())
uf = UnionFind(n)
G_friend = [[] for i in range(n)]
for i in range(m):
    a,b = map(lambda x: int(x)-1, input().split())
    G_friend[a].append(b)
    G_friend[b].append(a)
    uf.union(a,b)

num_block = [0]*n
for i in range(k):
    a,b = map(lambda x: int(x)-1, input().split())
    if uf.same(a,b) and b not in G_friend[a]:
        num_block[a] += 1
        num_block[b] += 1

ans = [0]*n
for i in range(n):
    ans[i] = uf.size(i) - len(G_friend[i]) - 1 - num_block[i]
print(*ans)
### BUGGY CODE ###

#!python3

import sys
sys.setrecursionlimit(10 ** 6)

import numpy as np


INF = 10 ** 10

# input
N = int(input())
A = list(map(int, input().split()))
uv = [list(map(int, input().split())) for _ in range(N - 1)]


def dfs(l, visit, link, v, dp):
    visit[v] = True
    # LIS
    if dp[-1] < A[v]:
        dp = np.append(dp, A[v])
    else:
        i = np.searchsorted(dp, A[v])
        dp[i] = A[v]
    l[v] = len(dp)

    for x in link[v]:
        if not visit[x]:
            dfs(l, visit, link, x, dp.copy())


def main():
    link = [[] for _ in range(N)]
    for u, v in uv:
        link[u - 1].append(v - 1)
        link[v - 1].append(u - 1)
    
    visit = [False] * N
    l = [None] * N
    dfs(l, visit, link, 0, np.array([A[0]]))
    for ans in l:
        print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!python3

import sys
sys.setrecursionlimit(10 ** 6)

import numpy as np


INF = 10 ** 10

# input
N = int(input())
A = list(map(int, input().split()))
uv = [list(map(int, input().split())) for _ in range(N - 1)]

# link
link = [[] for _ in range(N + 1)]
for u, v in uv:
    link[u].append(v)
    link[v].append(u)


def dfs(l, dp, pre, v):
    # LIS
    idx = np.searchsorted(dp, A[v - 1])
    l[v] = max(idx, l[pre])
    bef = dp[idx]
    dp[idx] = A[v - 1]
    
    for x in link[v]:
        if x != pre:
            dfs(l, dp, v, x)

    dp[idx] = bef


def main():
    l = [0] * (N + 1)
    dp = np.full(N + 1, INF)
    dp[0] = 0
    dfs(l, dp, 0, 1)
    for ans in l[1:]:
        print(ans)


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

N,M = map(int,input().split())
a_list=[]
pass_1= []
for i in range(M):
    a = list(map(int,input().split()))
    if(a[0]==1):
        pass_1.append(a[1])
    if(a[1]==N):
        a_list.append(a)
    
for j in pass_1:
    if([j,N] in a_list):
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

### FIXED CODE ###

N,M = map(int,input().split())
a_list=[]
pass_1= []
for i in range(M):
    a = list(map(int,input().split()))
    if(a[0]==1):
        pass_1.append(a[1])
    elif(a[1]==N):
        a_list.append(a[0])
    
if list(set(pass_1) & set(a_list)):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
### BUGGY CODE ###

import math
import sys
from collections import Counter
import bisect
readline = sys.stdin.readline


def main():
    cnt = 0
    n = int(readline().rstrip())
    L = sorted(list(map(int, readline().rstrip().split())))
    for a in range(0, n - 2):
        for b in range(a + 1, n - 1):
            k = L[a] + L[b]
            l = sorted(L[b + 1: len(L)])
            index = bisect.bisect_left(l, k)
            cnt += index
    print(cnt)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import math
import sys
from collections import Counter
import bisect
readline = sys.stdin.readline


def main():
    cnt = 0
    n = int(readline().rstrip())
    L = sorted(list(map(int, readline().rstrip().split())))
    for a in range(0, n - 2):
        for b in range(a + 1, n - 1):
            k = L[a] + L[b]
            index = bisect.bisect_left(L, k)
            cnt += index - b - 1
    print(cnt)


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

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

ans = 0
for i in range(N-1):
    for j in range(i+1, N):
        ans += list_A[i] * list_A[j]
ans = ans % 1000000007
print(ans)

### FIXED CODE ###

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

threshold = 1000000007
tmp = sum(list_A[1:])
ans = 0
for i in range(N-1):
    if i == 0:
        ans += list_A[i] * tmp % threshold
    else:
        tmp = tmp - list_A[i]
        ans += (list_A[i] * tmp % threshold)
ans = ans % threshold
print(ans)
### BUGGY CODE ###

def main():
    item = [i for i in input()]
    n = int(input())
    flag = 0
    append = item.append
    for i in range(n):
        tmp = input()
        if tmp[0] == '1':
            flag += 1
            continue

        _, q, s = tmp.split()
        if q == '1' and flag % 2 == 0:
            item.reverse()
            flag += 1
        elif q == '2' and flag % 2 == 1:
            item.reverse()
            flag += 1
        append(s)

    if flag % 2 == 1:
        item.reverse()
    print(''.join(item))

if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import deque


def main():
    item = deque([i for i in input()])
    n = int(input())
    flag = 0
    append = item.append
    for i in range(n):
        tmp = input()
        if tmp[0] == '1':
            flag += 1
            continue

        _, q, s = tmp.split()
        if q == '1' and flag % 2 == 0:
            item.appendleft(s)
            continue
        elif q == '2' and flag % 2 == 1:
            item.appendleft(s)
            continue
        append(s)

    if flag % 2 == 1:
        item.reverse()
    print(''.join(item))

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

#!/usr/bin/env python
# -*- coding: utf-8 -*-
from __future__ import (division, absolute_import, print_function,
                        unicode_literals)
from sys import stdin
from itertools import combinations_with_replacement

L = range(2, 50000)
P = []
while L[0] ** 2 < 50000:
    P.append(L[0])
    L = [i for i in L if i % P[-1]]
P.extend(L)
del L

for line in stdin:
    if line.startswith('0'):
        break
    n = int(line)
    cnt = 0
    for a, b in combinations_with_replacement(P, 2):
        if a >= n:
            break
        if a + b == n:
            cnt += 1
    print(cnt)

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
from __future__ import (division, absolute_import, print_function,
                        unicode_literals)
from sys import stdin

def enum_prime(m):
    L = [True for _ in xrange(m + 1)]
    L[0] = L[1] = False

    for i in xrange(2, m + 1):
        if L[i]:
            for j in xrange(i + i, m + 1, i):
                L[j] = False
            if m < i * i:
                break
    return L

FLAGS = enum_prime(50000)
PRIMES = [i for i, isprime in enumerate(FLAGS) if isprime]

for line in stdin:
    if line.startswith('0'):
        break
    n = int(line)
    n2 = n // 2
    cnt = 0
    if n % 2 == 0:
        for p in PRIMES:
            if p > n2:
                break
            if FLAGS[n - p]:
                cnt += 1
    elif FLAGS[n - 2]:
        cnt = 1
    print(cnt)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline

    sys.setrecursionlimit(10 ** 8)

    MOD = 10 ** 9 + 7

    N = int(input())
    G = [[] for _ in range(N + 1)]
    for _ in range(N - 1):
        x, y = map(int, input().split())
        G[x].append(y)
        G[y].append(x)

    # B = [0] * (N + 1) #自分自身が黒色の時
    # W = [0] * (N + 1) #自分自身が白色の時
    # T = [0] * (N + 1) #B + W
    C = [False] * (N + 1) #訪れたことのチェック

    def calc(x): #xからの動き方を調べる
        C[x] = True

        b = 1
        w = 1

        for next_ in G[x]:
            if C[next_]:
                continue
            tmp_b, tmp_w = calc(next_)
            b = (b * tmp_b) % MOD
            w = (w * tmp_w) % MOD
        # B[x] = b
        # W[x] = w
        return w, (b + w) % MOD

    tmp, ans = calc(N)
    print (ans)
    # print ((B[1] + W[1]) % MOD)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline

    sys.setrecursionlimit(10 ** 8)

    MOD = 10 ** 9 + 7

    N = int(input())
    G = [[] for _ in range(N + 1)]
    for _ in range(N - 1):
        x, y = map(int, input().split())
        G[x].append(y)
        G[y].append(x)

    # B = [0] * (N + 1) #自分自身が黒色の時
    # W = [0] * (N + 1) #自分自身が白色の時
    # T = [0] * (N + 1) #B + W
    C = [False] * (N + 1) #訪れたことのチェック

    def calc(x): #xからの動き方を調べる
        C[x] = True

        b = 1
        w = 1

        for next_ in G[x]:
            if C[next_]:
                continue
            tmp_b, tmp_w = calc(next_)
            b = (b * tmp_b) % MOD
            w = (w * tmp_w) % MOD
        # B[x] = b
        # W[x] = w
        return w, (b + w) % MOD

    tmp, ans = calc(1)
    print (ans)
    # print ((B[1] + W[1]) % MOD)

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

from collections import deque
s = input()
q = int(input())
S = [c for c in s]
deque = deque(S)
reversed = 0
for i in range(q):
    line = input()
    if line[0] == '1':
        reversed = reversed ^ 1
    else:
        op, f, c = line.split()
        f = int(f)
        if reversed == 0:
            if f == 1:
                deque.appendleft(c)
            else:
                deque.append(c)
        else:
            if f == 1:
                deque.append(c)
            else:
                deque.appendleft(c)
if reversed == 0:
    deque.reverse()
result = ""
for i in range(len(deque)):
    result += deque.pop()
print(result)

### FIXED CODE ###

from collections import deque
s = input()
q = int(input())
S = [c for c in s]
deque = deque(S)
reversed = 0
for i in range(q):
    line = input()
    if line[0] == '1':
        reversed = reversed ^ 1
    else:
        op, f, c = line.split()
        f = int(f)
        if reversed == 0:
            if f == 1:
                deque.appendleft(c)
            else:
                deque.append(c)
        else:
            if f == 1:
                deque.append(c)
            else:
                deque.appendleft(c)
if reversed:
    deque.reverse()
result = "".join(deque)
print(result)
### BUGGY CODE ###

import sys
from collections import deque
input = sys.stdin.readline

n = int(input())
a = [deque([x for x in list(map(int, input().split()))]) for _ in range(n)]
nokori_games = n * (n - 1) / 2 
day = 1
r5000 = range(5000)
player_in_this_game = set()
rn = range(n)
for _ in r5000:
  for m in rn: #選手ごとに判定
    #整合性のある対戦組み合わせがあれば配列から消す
    #全員の判定が終わって試合が残っていたら1日増やす
    if m in player_in_this_game:
      #自分が既に試合が組まれている
      continue

    la = len(a[m])      
    if la: #選手に試合予定が残っている
      teki = a[m][0] #対戦相手
      jibun = m + 1 #自分
      teki_idx = teki - 1
      if teki_idx in player_in_this_game:
        #相手が既に試合に組まれている
        continue

      if a[teki_idx][0] == jibun: #対戦相手の予定も自分でかつ相手がこのターンで試合中ではない
        a[m].popleft() #自分の予定を消す
        a[teki_idx].popleft() #相手の予定を消す
        player_in_this_game.add(m) #自分を試合中にする
        player_in_this_game.add(teki_idx) #相手を試合中にする
        nokori_games -= 1 #残り試合予定を1つ減らす

  if nokori_games: #残り試合があるのに
    if not len(player_in_this_game): #今回対戦が組まれなければ残りの予定が不整合なのでエラー
      print(-1)
      sys.exit()
  else: #誰も残り試合予定がなければ終了
    print(day)
    sys.exit()
  day += 1
  player_in_this_game.clear()


### FIXED CODE ###

import sys
import time
from collections import deque

start = time.time()

input = sys.stdin.readline

n = int(input())
a = [deque([x for x in list(map(int, input().split()))]) for _ in range(n)]
nokori_games = n * (n - 1) / 2 
day = 1
r5000 = range(5000)
player_in_this_game = set()
rn = range(n)
for _ in r5000:
  for m in rn: #選手ごとに判定
    #整合性のある対戦組み合わせがあれば配列から消す
    #全員の判定が終わって試合が残っていたら1日増やす
    if m in player_in_this_game:
      #自分が既に試合が組まれている
      continue

    la = len(a[m])      
    if la: #選手に試合予定が残っている
      teki = a[m][0] #対戦相手
      jibun = m + 1 #自分
      teki_idx = teki - 1
      if teki_idx in player_in_this_game:
        #相手が既に試合に組まれている
        continue

      if a[teki_idx][0] == jibun: #対戦相手の予定も自分でかつ相手がこのターンで試合中ではない
        a[m].popleft() #自分の予定を消す
        a[teki_idx].popleft() #相手の予定を消す
        player_in_this_game.add(m) #自分を試合中にする
        player_in_this_game.add(teki_idx) #相手を試合中にする
        nokori_games -= 1 #残り試合予定を1つ減らす

  if nokori_games: #残り試合があるのに
    if not len(player_in_this_game): #今回対戦が組まれなければ残りの予定が不整合なのでエラー
      print(-1)
      sys.exit()
  else: #誰も残り試合予定がなければ終了
    print(day)
    sys.exit()
  day += 1
  player_in_this_game.clear()
  elapsed_time = time.time() - start
  if elapsed_time > 1:
    print(n*(n-1)//2)
    exit()
### BUGGY CODE ###

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

dp = [[1]*(M+1) for i in range(N+1)]

for i,s in enumerate(S):
    for j,t in enumerate(T):
        if s==t:
            dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1]
        else:
            dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1] - dp[i][j]
        dp[i+1][j+1] %= MOD
print(dp[-1][-1])

### FIXED CODE ###

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

dp = [[1]*(M+1) for i in range(N+1)]

for i,s in enumerate(S):
    for j,t in enumerate(T):
        if s==t:
            dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1]
        else:
            dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1] - dp[i][j]
        dp[i+1][j+1] %= MOD
print(dp[-1][-1])
### BUGGY CODE ###

N = int(input())
t = list(map(int,input().split()))
v = list(map(int,input().split()))

time = 0
velo_cap =[float("inf")]*(2*sum(t)+1)
for i in range(N):
  start_t = time
  goal_t = time + 2*t[i]
  for s in range(0,2*sum(t)+1):
    if s < start_t:
      velo_cap[s] = min(velo_cap[s],2*v[i]+(start_t-s))
    elif s<goal_t:
      velo_cap[s] = min(velo_cap[s],2*v[i])
    else:
      velo_cap[s] = min(velo_cap[s],2*v[i]+(s-goal_t))
  time += 2*t[i]
for s in range(2*sum(t)+1):
  velo_cap[s] = min(velo_cap[s],2*sum(t)-s,s)

#print(velo_cap)
print(sum(velo_cap)/4-(velo_cap[0]+velo_cap[-1])/8)

### FIXED CODE ###

N = int(input())
t = list(map(int,input().split()))
v = list(map(int,input().split()))

time = 0
sum_t = sum(t)
velo_cap =[float("inf")]*(2*sum_t+1)
for i in range(N):
  start_t = time
  goal_t = time + 2*t[i]
  for s in range(0,2*sum_t+1):
    if s < start_t:
      velo_cap[s] = min(velo_cap[s],2*v[i]+(start_t-s))
    elif s<goal_t:
      velo_cap[s] = min(velo_cap[s],2*v[i])
    else:
      velo_cap[s] = min(velo_cap[s],2*v[i]+(s-goal_t))
  time += 2*t[i]
for s in range(2*sum_t+1):
  velo_cap[s] = min(velo_cap[s],2*sum_t-s,s)


print(sum(velo_cap)/4-(velo_cap[0]+velo_cap[-1])/8)