Harryxun/GPT-100-sft-dataset huggingface dataset:
Problem p03451 (python)

Fixed submission:
N = int(input())
A = [list(map(int, input().split())) for i in range(2)]

ans = 0
for i in range(N):
    ans = max(ans, sum(A[0][:i+1])+sum(A[1][i:]))

print(ans)

Buggy submission (verdict: Runtime Error):
N, M = map(int, input().split())
LRD = [list(map(int, input().split())) for i in range(M)]
 
 
class WeightedUnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n + 1)
        self.weight = [0] * (n+1)
 
    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = self.find(self.par[x])
            return self.par[x]
 
    # 重さの検索
    def weighting(self, x):
        self.find(x)
        return self.weight[x]
 
    # 併合
    def union(self, x, y, w):
        w -= self.weighting(x)
        w += self.weighting(y)
        x = self.find(x)
        y = self.find(y)
 
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            w = -w
            self.weight[y] = w
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
 
    # 同じ集合に属するか
    def same(self, x, y):
        return self.find(x) == self.find(y)
 
    # 各頂点間の絶対距離
    def diff(self, x, y):
        return abs(self.weighting(x) - self.weighting(y))
 
 
wuf = WeightedUnionFind(N)
for l, r, d in LRD:
    if wuf.same(l, r):
        if wuf.diff(l, r) != d:
            print("No")
            break
    else:
        wuf.union(l, r, d)
else:
    print("Yes")
Problem p03469 (python)

Fixed submission:
S = input()
print("2018"+S[4::])

Buggy submission (verdict: Runtime Error):
N, Y = map(int, input().split())
# x:10000円, y;5000円, z:1000円
for x in range(N+1):
    for y in range(N-x+1):# 5000円の枚数をN-(10000円の枚数)までに制限
        for z in range(N-x-y-1):
            if 10000*x + 5000*y + 1000*z == Y:
                print(x, y, z)
                exit(0)
print(-1, -1, -1)
Problem p03471 (python)

Fixed submission:
N, Y = map(int, input().split())
flg = False
for x in range(N+1):
    for y in range(N+1):
        if ((10000*x + 5000*y + (N-x-y)*1000)==Y) & (x+y<=N):
            print(x,y,(N-x-y))
            flg = True
            break
    if flg:
        break
else:
    print(-1,-1,-1)

Buggy submission (verdict: Runtime Error):
N, Y = map(int, input().split())
# x:10000円, y;5000円, z:1000円
for x in range(N+1):
    for y in range(N-x+1):　# 5000円の枚数をN-(10000円の枚数)までに制限
        z = N - (x + y)
        if 10000*x + 5000*y + 1000*z == Y:
            print(x, y, z)
            exit(0)
print(-1, -1, -1)
Problem p03472 (python)

Fixed submission:
import math

N, H = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(N)]
zan = max(ab)
zan = zan[0]
ab.sort(reverse=True, key=lambda x:x[1])

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

ans = []

for i in range(len(bunnage)):
    Z = max(H - bunnage[i], 0)
    zan_num = math.ceil(Z/zan)
    ans.append(i+1+zan_num)

print(min(ans))

Buggy submission (verdict: Runtime Error):
import math
N, H = map(int, input().split())
A = []
B = []
for i in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

amax = max(A)
# 最強の振り刀より強い攻撃力を持つものを抽出
B = list(filter(lambda x: x > amax, B))
B.sort(reverse=True)

ans = 0
while H > 0:
    # まだ投げれる
    if not B == []:
        H -= B.pop(-1)
        del B[-1]
    # もう投げれない
    else:
        ans += math.ceil(H/amax)
        break
    ans += 1

print(ans)
Problem p03488 (python)

Fixed submission:
S = input()
N = len(S)
S = list(S.split("T"))
x, y = map(int, input().split())

X_command = sorted([len(i) for i in S[::2]], reverse=True)
Y_command = sorted([len(i) for i in S[1::2]], reverse=True)

nx = X_command.pop(-1)
ny = 0

for xi in X_command:
    if nx > x:
        nx -= xi
    else:
        nx += xi

for yi in Y_command:
    if ny > y:
        ny -= yi
    else:
        ny += yi

if nx == x and ny == y:
    print("Yes")
else:
    print("No")

Buggy submission (verdict: Runtime Error):
S = input()
N = len(S)
S = list(S.split("T"))
x, y = map(int, input().split())

X_command = sorted([len(i) for i in S[::2]], reverse=True)
Y_command = sorted([len(i) for i in S[1::2]], reverse=True)

dp_x = [[False] * (sum(X_command)+1) for i in range(len(X_command))]
dp_y = [[False] * (sum(Y_command)+1) for i in range(len(Y_command))]

if X_command:
    dp_x[0][X_command[0]] = True
    for i in range(1, len(X_command)):
        for xi in range(sum(X_command)):
            if xi + X_command[i] >= N-1:
                continue
            if xi-X_command[i] >= 0:
                dp_x[i][xi] = dp_x[i-1][xi-X_command[i]] or dp_x[i-1][xi+X_command[i]]
            else:
                dp_x[i][xi] = dp_x[i-1][xi+X_command[i]]

if Y_command:
    dp_y[0][Y_command[0]] = True
    for i in range(1, len(Y_command)):
        for yi in range(sum(Y_command)):
            if yi + Y_command[i] >= N-1:
                continue
            if yi-Y_command[i] >= 0:
                dp_y[i][yi] = dp_y[i-1][yi-Y_command[i]] or dp_y[i-1][yi+Y_command[i]]
            else:
                dp_y[i][yi] = dp_y[i-1][yi+Y_command[i]]


x, y = max(x, -x), max(y, -y)

if sum(X_command) < x or sum(Y_command) < y:
    print("No")
    exit()
if dp_x[len(X_command)-1][x] and dp_y[len(Y_command)-1][y]:
    print("Yes")
else:
    print("No")

Buggy submission (verdict: Runtime Error):
S = input()
N = len(S)
S = list(S.split("T"))
x, y = map(int, input().split())

X_command = sorted([len(i) for i in S[::2]], reverse=True)
Y_command = sorted([len(i) for i in S[1::2]], reverse=True)

dp_x = [[False] * N for i in range(N)]
dp_y = [[False] * N for i in range(N)]

if X_command:
    dp_x[0][X_command[0]] = True
    for i in range(1, len(X_command)):
        for xi in range(N):
            if xi + X_command[i] >= N:
                continue
            if xi-X_command[i] >= 0:
                dp_x[i][xi] = dp_x[i-1][xi-X_command[i]] or dp_x[i-1][xi+X_command[i]]
            else:
                dp_x[i][xi] = dp_x[i-1][xi+X_command[i]]

if Y_command:
    dp_y[0][Y_command[0]] = True
    for i in range(1, len(Y_command)):
        for yi in range(N):
            if yi + Y_command[i] >= N:
                continue
            if yi-Y_command[i] >= 0:
                dp_y[i][yi] = dp_y[i-1][yi-Y_command[i]] or dp_y[i-1][yi+Y_command[i]]
            else:
                dp_y[i][yi] = dp_y[i-1][yi+Y_command[i]]


x, y = max(x, -x), max(y, -y)

if dp_x[len(X_command)-1][x] and dp_y[len(Y_command)-1][y]:
    print("Yes")
else:
    print("No")
Problem p03496 (python)

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

key = 0
for a in A:
    if abs(a) > abs(key):
        key = a
key_i = A.index(key)

m = 0
ans = []
if key > 0:
    for i in range(N):
        if A[i] < 0:
            m += 1
            A[i] += key
            ans.append([key_i+1, i+1])

    for i in range(1, N):
        if A[i-1] > A[i]:
            A[i] += A[i-1]
            m += 1
            ans.append([i, i+1])

    print(m)
    for x, y in ans:
        print(x, y)

elif key < 0:
    for i in range(N):
        if A[i] > 0:
            m += 1
            A[i] += key
            ans.append([key_i+1, i+1])

    for i in range(N-1, 0, -1):
        if A[i-1] > A[i]:
            A[i-1] += A[i]
            m += 1
            ans.append([i+1, i])

    print(m)
    for x, y in ans:
        print(x, y)

else:
    print(0)

Buggy submission (verdict: Runtime Error):
N = int(input())
A = list(map(int, input().split()))
m = 0
ans = []
a = A.index(min(A))+1
b = A.index(max(A)+1)
for i in range(N-1,0,-1):
    while A[i] < A[i-1]:
        m += 1
        
        if abs(A[i]-min(A)) > abs(A[i]-max(A)):
            if min(A) > 0:
                A[i] += min(A)
                ans.append([a,i+1])
            else:
                A[i-1] += min(A)
                ans.append([a,i])

        else:
            if max(A) > 0:
                A[i] += max(A)
                ans.append([b,i+1])
            else:
                A[i-1] += max(A)
                ans.append([b,i])

print(m)
for x,y in ans:
    print(x, y)
Problem p03534 (python)

Fixed submission:
S = input()
C = {"a": 0, "b": 0, "c": 0}
for s in S:
    C[s] += 1
if abs(C["a"] - C["b"]) <= 1 and abs(C["b"] - C["c"]) <= 1 and abs(C["c"] - C["a"]) <= 1:
    print("YES")
else:
    print("NO")

Buggy submission (verdict: Runtime Error):
S = input()
C = {"a": 0, "b": 0, "c": 0}
for s in S:
    C["s"] += 1
if abs(C["a"] - C["b"]) <= 1 and abs(C["a"] - C["b"]) <= 1 and abs(C["a"] - C["b"]) <= 1:
    print("YES")
else:
    print("NO")
Problem p03569 (python)

Fixed submission:
S = input()
S2 = "".join([s for s in S if s != "x"])

if S2 != S2[::-1]:
    print(-1)
    exit()

A = []
cnt = 0
for s in S:
    if s != "x":
        A.append(cnt)
        cnt = 0
    else:
        cnt += 1
A.append(cnt)

ans = 0
for i in range(len(A) // 2):
    ans += abs(A[i] - A[-i-1])
print(ans)

Buggy submission (verdict: Runtime Error):
S = list(input())
i, j = 0, len(S) - 1
ans = 0

while i != j:
    if S[i] == S[j]:
        i += 1
        j -= 1

    elif S[i] == 'x':
        i += 1
        ans += 1

    elif S[j] == 'x':
        j -= 1
        ans += 1

    else:
        print('-1')
        break

else:
    print(ans)
Problem p03573 (python)

Fixed submission:

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

if (A==B) & (A!=C):
    print(C)
elif (A==C) & (A!=B):
    print(B)
else:
    print(A)

Buggy submission (verdict: Runtime Error):
N, K = map(int, input().split())
XY = []
YX = []
for i in range(N):
    x, y = map(int, input().split())
    XY.append([x, y, i])
    YX.append([y, x, i])
XY.sort()
YX.sort()

x_order = {}
for xo, p in enumerate(XY):
    x, y, i = p
    x_order[i] = xo

cums = [[0 for j in range(N+1)] for i in range(N+1)]
for i in range(N):
    y, x, pi = YX[i]
    xo = x_order[pi]
    for j in range(N + 1):
        cums[i + 1][j] = cums[i][j] + (1 if j > xo else 0)

ans = float('inf')

for i in range(N-1):
    for j in range(i+1, N):
        for k in range(N-1):
            for l in range(k+1, N):
                if cums[l+1][j+1] - cums[l+1][i] - cums[k][j+1] + cums[k][i] >= K:
                        ans = min(ans, (XY[j][0]-XY[i][0]) * (YX[l][0]-YX[k][0]))

print(ans)
Problem p03576 (python)

Fixed submission:
N, K = map(int, input().split())
XY = []
YX = []
for i in range(N):
    x, y = map(int, input().split())
    XY.append([x, y, i])
    YX.append([y, x, i])
XY.sort()
YX.sort()

x_order = {}
for xo, p in enumerate(XY):
    x, y, i = p
    x_order[i] = xo

cums = [[0 for j in range(N+1)] for i in range(N+1)]
for i in range(N):
    y, x, pi = YX[i]
    xo = x_order[pi]
    for j in range(N + 1):
        cums[i + 1][j] = cums[i][j] + (1 if j > xo else 0)

ans = float('inf')

for i in range(N-1):
    for j in range(i+1, N):
        for k in range(N-1):
            for l in range(k+1, N):
                if cums[l+1][j+1] - cums[l+1][i] - cums[k][j+1] + cums[k][i] >= K:
                        ans = min(ans, (XY[j][0]-XY[i][0]) * (YX[l][0]-YX[k][0]))

print(ans)

Buggy submission (verdict: Runtime Error):
def main():
    N, K = map(int, input().split())
    Points = []
    for i in range(N):
        x, y = map(int, input().split())
        Points.append([x, y])

    ans = float('inf')
    for u in range(N):
        for r in range(N):
            for d in range(N):
                for l in range(N):
                    x1, x2 = min(Points[l][0], Points[r][0]), max(Points[l][0], Points[r][0])
                    y1, y2 = min(Points[d][1], Points[u][1]), max(Points[d][1], Points[u][1])
                    tmp = 0
                    for x, y in Points:
                        if (x1 <= x <= x2) and (y1 <= y <= y2):
                            tmp += 1
                    if tmp >= K:
                        ans = min(ans,  (x2 - x1) * (y2 - y1))

    print(ans)


main()
Problem p03599 (python)

Fixed submission:

A, B, C, D, E, F = map(int, input().split())
# A:水を100Ag　B:水を100Bg C:砂糖をCg D:砂糖をDg E:100gあたりの溶ける最大量　F:入れられる物質の質量の限界

ans_mizu = 1
ans_sato = 0
pat = []
mizu = set()
for i in range(int(F/100)+1):
    for j in range(int(F/100)+1):
        if 100*A*i + 100*B*j <= F:
            mizu.add(100*A*i+100*B*j)

mizu.remove(0)

for m in mizu:
    howaryo = (m*E)//100
    for i in range(int(howaryo/C)+1):
        for j in range(int(howaryo/D)+1):
            sato = C*i + D*j
            if (m + sato <= F) & (sato <= howaryo):
                ans_sato = max(ans_sato,sato)
                
    pat.append([m+ans_sato,ans_sato])
    ans_mizu = 1
    ans_sato = 0
    
pat.sort(key = lambda x:x[1]/(x[0]+x[1]), reverse = True)
print(pat[0][0],pat[0][1])

Buggy submission (verdict: Runtime Error):
A, B, C, D, E, F = map(int, input().split())
# A:水を100Ag　B:水を100Bg C:砂糖をCg D:砂糖をDg E:100gあたりの溶ける最大量　F:入れられる物質の質量の限界

ans_mizu = 100
ans_sato = 0

mizu = set()
for i in range(int(F/(100*max(A,B)))+1):
    for j in range(int(F/(100*min(A,B)))+1):
        if 100*A*i + 100*B*j <= F:
            mizu.add(100*A*i+100*B*j)
            
for m in mizu:
    howaryo = (m*E)//100
    for i in range(int(howaryo//C)+1):
        for j in range(int(howaryo//D)+1):
            sato = C*i + D*j
            if (m + sato <= F) & (sato <= howaryo):
                if (ans_sato/(ans_mizu+ans_sato)) < (sato/(m+sato)):
                    ans_mizu = m
                    ans_sato = sato

print(ans_mizu+ans_sato,ans_sato)
Problem p03612 (python)

Fixed submission:
N = int(input())
p = list(map(int, input().split()))

ans = 0
bin_box = []

for i in range(len(p)):
    if i+1 == p[i]:
        bin_box.append(1)
    else:
        bin_box.append(0)

bin_box.append(0)

i = 0
while i < len(bin_box):
    if bin_box[i] == 1:
        ans += 1
        if bin_box[i+1] == 1:
            i += 1
    
    i += 1
    
print(ans)

Buggy submission (verdict: Runtime Error):
N = int(input())
P = list(map(int, input().split()))

ans = 0
for i in range(N):
    if P[i] == i+1:
        tmp = P[i]
        P[i] = P[i+1]
        P[i+1] = tmp
        ans += 1


for i in range(N):
    if P[i] == i+1:
        ans += 1

print(ans)
Problem p03645 (python)

Fixed submission:
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(M)]

toN = list(filter(lambda x: N in x, AB))
toN = set([flatten for inner in toN for flatten in inner])
frm_first = list(filter(lambda x: 1 in x, AB))
frm_first = set([flatten for inner in frm_first for flatten in inner])

if toN & frm_first:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Buggy submission (verdict: Runtime Error):
import sys

N , M = map(int , input().split())
voyages = []
for i in range(M):
    voyages.append(list(map(int , input().split())))

def search(goal, path):
    n = path[len(path) - 1]
    if n == goal - 1:
        if len(path) < 4:
            print("POSSIBLE")
        else:
            print("IMPOSSIBLE")
        sys.exit()
        
    else:
        if n < len(voyages):
            for x in voyages[n]:
                if x not in path:
                    path.append(x)
                    search(goal, path)
                    path.pop()
        else:
            print("IMPOSSIBLE")
            sys.exit()
            
search(N, [0])

Buggy submission (verdict: Runtime Error):
import sys

N , M = map(int , input().split())
voyages = []
for i in range(M):
    voyages.append(list(map(int , input().split())))

def search(goal, path):
    n = path[len(path) - 1]
    if n == goal - 1:
        if len(path) < 4:
            print("POSSIBLE")
        else:
            print("IMPOSSIBLE")
        sys.exit()
        
    else:
        if n <= len(voyages):
            for x in voyages[n]:
                if x not in path:
                    path.append(x)
                    search(goal, path)
                    path.pop()
        else:
            print("IMPOSSIBLE")
            sys.exit()
            

if len(voyages) == 1:
    if not (N in voyages[0]):
        print("IMPOSSIBLE")
else:
    search(N, [0])

Buggy submission (verdict: Runtime Error):
import sys

N , M = map(int , input().split())
voyages = []
for i in range(M):
    voyages.append(list(map(int , input().split())))

def search(goal, path):
    n = path[len(path) - 1]
    if n == goal - 1:
        if len(path) < 4:
            print("POSSIBLE")
        else:
            print("IMPOSSIBLE")
        sys.exit()
        
    else:
        for x in voyages[n]:
            if x not in path:
                path.append(x)
                search(goal, path)
                path.pop()

if len(voyages) == 1:
    if not (N in voyages[0]):
        print("IMPOSSIBLE")
else:
    search(N, [0])
Problem p03646 (python)

Fixed submission:
import numpy

K = int(input())
N = 50

ans = numpy.array([49]*50)
ans += K // N
for i in range(K % N):
    ans -= 1
    ans[i] += 50

# print(ans)
ans = list(map(str, ans))
print(N)
print(" ".join(ans))

# cnt = 0
# while not (all(map(lambda x: x <= 49, ans))):
#     cnt += 1
#     ans.sort()
#     ans[-1] -= 50
#     ans[:49] += 1
# 
# print(cnt)

Buggy submission (verdict: Runtime Error):
from math import ceil
import numpy

K = int(input())
N = 50
M = ceil(K / N) + 49
Y = 50 - K % 50

ans = numpy.array([M] * 50)
ans[:Y] -= (K % 50 + 1)

ans = list(map(str, ans))
print(N)
print(" ".join(ans))
# cnt = 0
# while not (all(map(lambda x: x <= 49, ans))):
#     cnt += 1
#     ans.sort()
#     ans[-1] -= 50
#     ans[:49] += 1
#
# print(cnt)
Problem p03657 (python)

Fixed submission:
A , B = map(int, input().split())
if A + B <  3:
    print("Impossible")
    
elif A%3 == 0 or B%3 == 0 or (A+B)%3 ==0 :
    print("Possible")

else:
    print("Impossible")

Buggy submission (verdict: Runtime Error):
N = int(input())
Roads = []
for i in range(N-1):
    Roads.append(input().split())
black = 0
black_list = []
white = 0
white_list = []

for i in Roads:
    if 1 in i and N not in i:
        black += 1
    if N in i and 1 not in i:
        white += 1


if black > white :
    print("Fennec")
else:
    print("Snuke")
Problem p03699 (python)

Fixed submission:
import sys

N = int(input())
scores = []
box = []
cnt = 0
for i in range(N):
    scores.append(int(input()))

scores.sort()
gokei = sum(scores)

if gokei % 10 == 0:
    for i in range(N):
        aaa = gokei - scores[i]
        if aaa % 10 != 0:
            box.append(aaa)

else:
    print(gokei)
    sys.exit()
    
if box != []:
    print(max(box))
else:
    print(0)

Buggy submission (verdict: Runtime Error):
N = int(input())
scores = []
cnt = 0
for i in range(N):
    scores.append(int(input()))

scores.sort()
gokei = sum(scores)

while True:
    if gokei % 10 == 0:
        gokei -= scores[cnt]
        cnt += 1
        if cnt > len(scores):
            print(0)
            break
    else:
        print(gokei)
        break

Buggy submission (verdict: Runtime Error):
N = int(input())
scores = []
cnt = 0
for i in range(N):
    scores.append(int(input()))

scores.sort()
gokei = sum(scores)

while True:
    if gokei % 10 == 0:
        gokei -= scores[cnt]
        cnt += 1
        if cnt < len(scores):
            print(0)
            break
    else:
        print(gokei)
        break
Problem p03782 (python)

Fixed submission:
N, K = map(int, input().split())
A = list(map(int, input().split()))

A = sorted([a for a in A if a < K])
N = len(A)
S = sum(A)

# あああああああああああああああああああ＼(＾o＾)／
if S < K:
    print(N)
    exit()
elif S - A[0] < N:
    print(0)
    exit()

l, r = -1, N
while r - l > 1:
    m = (l + r) // 2
    B = A[:m] + A[m + 1:]

    if S - A[m] < K - A[m]:
        l = m
        continue

    dp = [False] * (K + 1)
    dp[0] = True
    flg= False

    for i in range(N - 1):
        for j in range(K + 1)[::-1]:
            if B[i] > j:
                continue
            else:
                dp[j] = dp[j - B[i]]

            if dp[j] and K-A[m] <= j < K:
                r = m
                flg = True
                break
        if flg:
            flg = False
            break
    else:
        l = m

print(r)

Buggy submission (verdict: Runtime Error):
N, K = map(int, input().split())
A = list(map(int, input().split()))

A = sorted([a for a in A if a < K])
N = len(A)
S = sum(A)

# あああああああああああああああああああ＼(＾o＾)／
if S - A[0] < K:
    print(0)
    exit()

l, r = -1, N
while r - l > 1:
    m = (l + r) // 2
    B = A[:m] + A[m + 1:]

    if S - A[m] < K - A[m]:
        l = m
        continue

    dp = [False] * (K + 1)
    dp[0] = True
    flg= False

    for i in range(N - 1):
        for j in range(K + 1)[::-1]:
            if B[i] > j:
                continue
            else:
                dp[j] = dp[j - B[i]]

            if dp[j] and K-A[m] <= j < K:
                r = m
                flg = True
                break
        if flg:
            flg = False
            break
    else:
        l = m

print(r)
Problem p03832 (python)

Fixed submission:
N, A, B, C, D = map(int, raw_input().split())
mod = 10 ** 9 + 7

# 階乗 & 逆元計算
factorial = [1]
inverse = [1]
for i in xrange(1, N + 2):
    factorial.append(factorial[-1] * i % mod)
    inverse.append(pow(factorial[-1], mod - 2, mod))


# 組み合わせ計算
def nCr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % mod


# n人いたときに、k人組を、x個つくる場合の数
def f(n, k, x):
    return nCr(n, k * x) * factorial[k * x] * pow(pow(factorial[k], x, mod), mod-2, mod) * inverse[x] % mod


dp = [0] * (N + 1)
dp[0] = 1

for k in xrange(A, B + 1):  # k人からなるグループをこれから作りますよ
    for n in range(1, N + 1)[::-1]:  # すでにn人は使っちゃってますよ
        X = xrange(C, D + 1)
        for x in X:
            if n - k * x < 0:  # はみ出る段階で打ち切りますよ
                break
            dp[n] += f(n, k, x) * dp[n - k * x] % mod

print(dp[N] % mod)

Buggy submission (verdict: Runtime Error):
N, A, B, C, D = map(int, input().split())
mod = 10 ** 9 + 7

# 階乗 & 逆元計算
factorial = [1]
inverse = [1]
for i in range(1, N + 2):
    factorial.append(factorial[-1] * i % mod)
    inverse.append(pow(factorial[-1], mod - 2, mod))


# 組み合わせ計算
def nCr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % mod


# n人いたときに、k人組を、x個つくる場合の数
def f(n, k, x):
    return nCr(n, k * x) * factorial[k * x] * pow(pow(factorial[k], x, mod), mod-2, mod) * inverse[x] % mod


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

for k in range(A, B+1):  # k人からなるグループをこれから作りますよ
    for n in range(N + 1):  # すでにn人は使っちゃってますよ
        cnt = 0
        X = [0] + list(range(C, D + 1))
        for x in X:
            if n - k * x < 0:  # はみ出る段階で打ち切りますよ
                break
            if k % 2 == 1:
                cnt += f(n, k, x) * dp[0][n - k * x] % mod
            else:
                cnt += f(n, k, x) * dp[1][n - k * x] % mod

        if k % 2 == 1:
            dp[1][n] = cnt
        else:
            dp[0][n] = cnt

if N % 2 == 1:
    print dp[1][N]
else:
    print dp[0][N]