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

def gcd(x, y):
    if x < y:
        x, y = y, x
    while y > 0:
        r = x % y
        x = y
        y = r
    return x


def main():
    A, B, C, D = map(int, input().split())
    tmp = 0
    R = int(C * D / gcd(C, D))
    flag = True
    i = 1
    while flag:
        if C * i < A:
            i += 1
        elif C * i <= B:
            i += 1
            tmp += 1
        else:
            break

    flag = True
    i = 1
    while flag:
        if D * i < A:
            i += 1
        elif D * i <= B:
            i += 1
            tmp += 1
        else:
            break

    flag = True
    i = 1
    while flag:
        if R * i < A:
            i += 1
        elif R * i <= B:
            i += 1
            tmp -= 1
        else:
            break

    print(B-A+1-tmp)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def gcd(x, y):
    if x < y:
        x, y = y, x
    while y > 0:
        x, y = y, x % y
    return x


def main():
    A, B, C, D = map(int, input().split())
    R = int(C * D / gcd(C, D))

    tmp = B // C - (A-1) // C + B // D - (A-1) // D - B // R + (A-1) // R
    print(B-A+1-tmp)


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

from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


a, b, n = LI()
ans = -INF
if b - 1 > n:
    x = n
    ans = max(ans, a * x // b - a * (x // b))
else:
    x = b - 1
    while True:
        ans = max(ans, a * x // b - a * (x // b))
        x += b
        if x > n:
            break

print(ans)


### FIXED CODE ###

from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


a, b, n = LI()
if b - 1 <= n:
    x = b - 1
else:
    x = n
print(a * x // b - a * (x // b))
### BUGGY CODE ###

l, r = [int(x) for x in input().split()]
m = 2019
for i in range(l,r+1):
    for j in range(i+1,r+1):
        k = (i * j) % 2019
        m = min(m, k)
        if m == 0:
            break
print(m)

### FIXED CODE ###

l, r = [int(x) for x in input().split()]
m = 2019

ml = (l % 2019)
mr = (r % 2019)
t = l + 2019
if r > t:
    m = 0
else:
    if ml < mr:
        for i in range(ml, mr):
            for j in range(i+1, mr+1):
                m = min(m, (i * j) % 2019)
    else:
        m = 0
print(m)
### BUGGY CODE ###

def main():
    from heapq import heapify,heapreplace

    n,m = map(int,input().split())
    A = list(map(int,input().split()))
    BC = [list(map(int,input().split())) for _ in range(m)]

    heapify(A)

    BC = sorted(BC,key=lambda x:(x[1]),reverse=True)
    for b,c in BC:
        if c<A[0]:
            break
        for i in range(b):
            if A[0]>c:
                break
            heapreplace(A,c)
        
    #print(A)
    print(sum(A))
if __name__=='__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    n,m = map(int,input().split())
    A = list(map(int,input().split()))
    BC = [list(map(int,input().split())) for _ in range(m)]

    BC = sorted(BC,key=lambda x:(x[1]),reverse=True)
    append_list = []
    for b,c in BC:
        if len(append_list)>=n:
            break
        append_list+=[c]*b
    A+=append_list
    A.sort(reverse=True)
    print(sum(A[:n]))
if __name__=='__main__':
    main()
### BUGGY CODE ###

from math import gcd

n = int(input())
a = list(map(int,input().split()))
i,g = n-2,a[n-1]
pc = True
while i >= 0:
  res = gcd(g,a[i])
  if res != 1:
    pc = False
    break
  g *= a[i]
  i -= 1
if not pc:
  i,g = n-2,a[n-1]
  while i >= 0:
    g = gcd(g,a[i])
    i -= 1
  if g != 1:
    print("not coprime")
  else:
    print("setwise coprime")
else:
  print("pairwise coprime")

### FIXED CODE ###

from math import gcd
from collections import defaultdict

mxn = 10**6+1
spf = [i for i in range(mxn)]

for i in range(4,mxn,2):
  spf[i] = 2
i = 3
while i*i <= mxn:
  if spf[i] == i:
    for j in range(i*i,mxn,i):
      if spf[j] == j:
        spf[j] = i
  i += 1
ph = defaultdict(lambda:False)
pc = True
def getFactors(n):
  global pc
  while n != 1:
    temp = spf[n]
    if ph[temp] == True:
      pc = False
      break
    ph[temp] = True
    while n%temp == 0:
      n //= temp

n = int(input())
a = list(map(int,input().split()))
i,g = n-2,a[n-1]
while i >= 0:
  g = gcd(g,a[i])
  i -= 1
if g != 1:
  print("not coprime")
else:
  for i in a:
    if not pc:
      break
    getFactors(i)
  if not pc:
    print("setwise coprime")
  else:
    print("pairwise coprime")
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
from pprint import pprint

def solve(H: int, W: int, A: "List[str]"):
    used = [[False] * W for _ in range(H)]
    dx = [1, 0, -1, 0]
    dy = [0, -1, 0, 1]
    s = set()
    for i in range(H):
        for j in range(W):
            if A[i][j] == '#':
                s.add((i, j))
                used[i][j] = True

    ret = 0
    while True:
        nex = set()
        for x, y in s:
            for j in range(4):
                tx = x + dx[j]
                ty = y + dy[j]
                if 0 <= tx < H and 0 <= ty < W and not used[tx][ty]:
                    nex.add((tx, ty))
                    used[tx][ty] = True
        if len(nex) < 1:
            break
        s = nex
        ret += 1

    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [next(tokens) for _ in range(H) ]  # type: "List[str]"
    solve(H, W, A)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from pprint import pprint

def solve(H: int, W: int, A: "List[str]"):
    used = [[False] * W for _ in range(H)]
    dx = [1, 0, -1, 0]
    dy = [0, -1, 0, 1]
    s = set()
    for i in range(H):
        for j in range(W):
            if A[i][j] == '#':
                s.add((i, j))
                used[i][j] = True

    ret = 0
    while True:
        nex = set()
        for x, y in s:
            for j in range(4):
                tx = x + dx[j]
                ty = y + dy[j]
                if 0 <= tx < H and 0 <= ty < W and not used[tx][ty]:
                    nex.add((tx, ty))
                    used[tx][ty] = True
        if len(nex) < 1:
            break
        s = nex
        ret += 1

    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [next(tokens) for _ in range(H) ]  # type: "List[str]"
    solve(H, W, A)

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

import sys
sys.setrecursionlimit(10 ** 6)
N, M = map(int, sys.stdin.readline().split())
G = [[] for i in range(N)]
for i in range(M):
    l, r, d = map(int, sys.stdin.readline().split())
    l, r = l - 1, r - 1
    G[l].append((r, d))
    G[r].append((l, -d))

R = [None] * N


def dfs(u):
    global R, G
    for w, d in G[u]:
        if not R[w]:
            R[w] = R[u] + d
            if not dfs(w):
                return False
        else:
            if R[w] != R[u] + d:
                return False
    return True


flag = True
for i in range(N):
    if R[i] is None:
        R[i] = 0
        flag &= dfs(i)

if flag:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
N, M = map(int, sys.stdin.readline().split())
G = [[] for i in range(N)]
for i in range(M):
    l, r, q = map(int, sys.stdin.readline().split())
    G[l - 1].append((r - 1, q))
    G[r - 1].append((l - 1, -q))

R = [None] * N


def dfs(u):
    global R, G
    for w, d in G[u]:
        if R[w] is None:
            R[w] = R[u] + d
            if not dfs(w):
                return False
        else:
            if R[w] != R[u] + d:
                return False
    return True


flag = True
for i in range(N):
    if R[i] is None:
        R[i] = 0
        flag &= dfs(i)

if flag:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###


from collections import defaultdict

def submit():
    s = [int(c) for c in input()]
    modp = 2019

    curr = 0
    modp_count = defaultdict(int)
    modp_count[0] = 1
    ans = 0
    base = 1
    for c in reversed(s):
        curr += base * c
        curr_mod = curr % modp
        ans += modp_count[curr_mod]
        modp_count[curr_mod] += 1
        base *= 10
    
    print(ans)
    

submit()
    

### FIXED CODE ###


from collections import defaultdict

def submit():
    s = [int(c) for c in input()]
    modp = 2019

    curr = 0
    modp_count = defaultdict(int)
    modp_count[0] = 1
    ans = 0
    base = 1
    for c in reversed(s):
        curr += base * c
        curr_mod = curr % modp
        ans += modp_count[curr_mod]
        modp_count[curr_mod] += 1
        base *= 10
        base %= modp
    
    print(ans)
    

submit()
### BUGGY CODE ###

from sys import stdin
import math
import fractions
from collections import deque
from collections import Counter
import itertools

INF = 10 ** 10

import sys
sys.setrecursionlimit(100000)

# N <= 2*10^5
# Q <= 2*10^5
N, Q = [int(x) for x in stdin.readline().rstrip().split()]
#ab = [list(map(int, stdin.readline().rstrip().split())) for _ in range(N-1)]
#px = [list(map(int, stdin.readline().rstrip().split())) for _ in range(Q)]

ans = [0] * (N+1)
child = [[] for _ in range(N+1)]


def add(node, num):
    for x in child[node]:
        add(x, num)

    ans[node] += num

for a, b in [list(map(int, stdin.readline().rstrip().split())) for _ in range(N-1)]:
    child[a].append(b)

#print(child)

for p, x in [list(map(int, stdin.readline().rstrip().split())) for _ in range(Q)]:
    ii = p
    add(p, x)

print(*ans[1:], sep=" ")

### FIXED CODE ###

from sys import stdin
import math
import fractions
from collections import deque
from collections import Counter
import itertools

INF = 10 ** 10

# N <= 2*10^5
# Q <= 2*10^5
N, Q = [int(x) for x in stdin.readline().rstrip().split()]
ab = [list(map(int, stdin.readline().rstrip().split())) for _ in range(N-1)]
px = [list(map(int, stdin.readline().rstrip().split())) for _ in range(Q)]

node_value = [0] * (N+1)
parent = [-1] * (N+1)

for a, b in ab:
    parent[b] = a

for p, x in px:
    node_value[p] += x

#print(parent)

ans = [0] * (N+1)

for i in range(1, N+1):
    ans[i] = node_value[i]
    if parent[i] != -1:
        ans[i] += ans[parent[i]]

print(*ans[1:], sep=" ")
### BUGGY CODE ###

n = int(input())
ans = 0
for i in range(1,n+1):
    seven = 0
    five = 0
    three = 0
    while i > 0:
        if i % 10 == 7:
            seven = 1
        elif i % 10 == 3:
            three = 1
        elif i % 10 == 5:
            five = 1
        else:
            break
        i = i // 10
    if i == 0 and seven == 1 and five == 1 and three == 1:
        ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
ans = 0
def dfs(s):
    global ans
    if int(s) > n:
        return
    seven = 0
    five = 0
    three = 0
    for i in range(len(s)):
        if s[i] == "7":
            seven = 1
        elif s[i] == "5":
            five = 1
        elif s[i] == "3":
            three = 1
    if seven == 1 and five == 1 and three == 1:
        ans += 1

    dfs(s + "7")
    dfs(s + "5")
    dfs(s + "3")
    return
dfs("7")
dfs("5")
dfs("3")
print(ans)
### BUGGY CODE ###

n,m,k = map(int, input().split())

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

aa = [0]
bb = [0]

for i in range(n):
    aa.append(a[i] + aa[i])

for i in range(m):
    bb.append(b[i] + bb[i])

ans = 0
flag = 0
for i in range(n+1):
    if k - aa[i] < 0:
        flag = 1
        if ans < i-1:
            ans = i-1   
        break
    for j in range(m+1):
        if k - aa[i] - bb[j] < 0:
            flag = 1
            if ans < i + j - 1:
                ans = i + j - 1
            break

if flag == 0:
    print(n+m)
    exit()
print(ans)


### FIXED CODE ###

n,m,k = map(int, input().split())

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

aa = [0]
bb = [0]

for i in range(n):
    aa.append(a[i] + aa[i])

for i in range(m):
    bb.append(b[i] + bb[i])

ans = 0
mstart = m
for i in range(n+1):
    if k - aa[i] < 0:
        break
    for j in range(mstart,-1,-1):
        if k - aa[i] - bb[j] >= 0:
            mstart = j
            break
    if ans < i + j :
        ans = i + j 

print(ans)
### BUGGY CODE ###

import math

N = int(input())

result = 0

for a in range(1, N+1):
    for b in range(1, N+1):
        for c in range(1, N+1):
            result += math.gcd(math.gcd(a,b),c)

print(result)

### FIXED CODE ###

import math

N = int(input())

result = 0

for a in range(1, N+1):
    for b in range(1, N+1):
        if math.gcd(a,b) == 1:
            result += 1*N
        else:
            for c in range(1, N+1):
                result += math.gcd(math.gcd(a,b),c)

print(result)
### BUGGY CODE ###

from math import gcd
from functools import lru_cache
@lru_cache(maxsize = None)


def gcdx(x,y,z):
    return gcd(gcd(x,y),z)
n = int(input())
a = 0
longp = []

for i in range(1,n+1):
    for j in range(1,n+1):
        for p in range(1,n+1):
            a += gcdx(i,j,p)
           
print(a)

### FIXED CODE ###

from math import gcd

def gcdx(x,y,z):
    return gcd(gcd(x,y),z)
n = int(input())
a = 0
longp = []

for i in range(1,n+1):
    for j in range(1,n+1):
        for p in range(1,n+1):
            a += gcdx(i,j,p)
           
print(a)
### BUGGY CODE ###

n = int(input())
s = [input() for i in range(n)]

d = {}
for i in range(n):
    if s[i] in d:
        d[s[i]] += 1
    else:
        d[s[i]] = 1

d_s = sorted(d.items(), key=lambda x: x[1])

ma = [m[0] for m in d.items() if m[1] == max(d.values())]
print(*sorted(ma))

### FIXED CODE ###

from collections import Counter
n = int(input())
s = [input() for i in range(n)]

d = Counter(s).most_common()

s = d[0][1]
ans = []
for k, v in d:
    if s == v:
        ans.append(k)
    else:
        break
print(*sorted(ans), sep="\n")
### BUGGY CODE ###

import sys

n, m = [int(x) for x in sys.stdin.readline().split()]

s = []
d = []

for i in range(m):
	a, b = [int(x) for x in sys.stdin.readline().split()]
	if a == 1:
		s.append(b)
		if b in d:
			print('POSSIBLE')
			break
	if b == n:
		d.append(a)
		if a in s:
			print('POSSIBLE')
			break
else:
	print('IMPOSSIBLE')

### FIXED CODE ###

n, m = [int(x) for x in input().split()]

s = [0]*(n+1)
d = [0]*(n+1)

for i in range(m):
	a, b = [int(x) for x in input().split()]
	if a == 1:
		s[b] = 1
		if d[b] == 1:
			print('POSSIBLE')
			break
	elif b == n:
		d[a] = 1
		if s[a] == 1:
			print('POSSIBLE')
			break
else:
	print('IMPOSSIBLE')
### BUGGY CODE ###

n = int(input())
li = [list(map(int, input().split())) for i in range(n-1)]

for i in range(n-1):
    time = li[i][0] + li[i][1]
    for j in range(i+1, n-1):
        now = li[j][1]
        while time > now:
            now += li[j][2]
        time = now
        time += li[j][0]
    print(time)
print(0)

### FIXED CODE ###

n = int(input())
li = [list(map(int, input().split())) for i in range(n-1)]

for i in range(n-1):
	time = li[i][0] + li[i][1]
	for j in range(i+1, n-1):
		now = li[j][1]
		if now < time:
			now += li[j][2] * (-(-(time-now)//li[j][2]))
		time = now
		time += li[j][0]
	print(time)
print(0)
### BUGGY CODE ###

# E - Colorful Blocks

MOD = 998244353
N, M, K = map(int, input().split())

# 予め階乗を計算しておく
f = [1]
for i in range(N):
    f.append(f[i]*(i+1)%MOD)

# 組み合わせ関数
def comb_mod(n, r, p):
    return f[n] * pow(f[r], p-2, p) * pow(f[n-r], p-2, p)

ans = 0
for i in range(K+1):
    ans = (ans + (M*pow(M-1, N-1-i,MOD)) * comb_mod(N-1, i, MOD))%MOD

print(ans)


### FIXED CODE ###

# E - Colorful Blocks

MOD = 998244353
N, M, K = map(int, input().split())

# 予め階乗を計算しておく
f = [1]
for i in range(N):
    f.append(f[i]*(i+1)%MOD)

# 組み合わせ関数
def comb_mod(n, r, p):
    return f[n] * pow(f[r], p-2, p) * pow(f[n-r], p-2, p)

ans = 0
for i in range(K+1):
    ans = (ans + (M*pow(M-1, N-1-i,MOD)) * comb_mod(N-1, i, MOD))%MOD

print(ans)
### BUGGY CODE ###

# 木上の累積和

import sys
from collections import defaultdict
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))


def ints():
    return list(map(int, read().split()))


N, Q = ints()
tree = defaultdict(lambda: [])
for _ in range(N - 1):
    a, b = mina(*ints())
    tree[a].append(b)
    tree[b].append(a)
cnt = [0] * N
for _ in ra(Q):
    q, x = ints()
    cnt[q - 1] += x
cnt.append(0)  # -1アクセス用

# dfsでcntに木に沿った累積和をsetしていく


def dfs(u, p):  # uは現在のノード、pは親のノード
    cnt[u] += cnt[p]
    for nv in tree[u]:
        if nv == p:
            continue
        dfs(nv, u)


dfs(0, -1)

print(*cnt[:-1])


### FIXED CODE ###

# https://atcoder.jp/contests/abc138/tasks/abc138_d
# 下に数を最初に合計してから深さ優先探索なり、幅優先探索なりで下にカウンターを伝播させていけば良い。
# 累積和の木構造バージョン


import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


# 再帰の上限を緩和する(引数は適当)
import sys
sys.setrecursionlimit(1 << 25)
from collections import defaultdict

N, Q = read_ints()
child = defaultdict(lambda: [])  # ノード0は存在しない
score = [0] * (N + 1)
for _ in range(N - 1):
    a, b = read_ints()
    child[a].append(b)
    child[b].append(a)
for _ in range(Q):
    p, x = read_ints()
    score[p] += x

# 木を走査しながらscoreを合計していく
ans = [0] * (N + 1)


def dfs(p, u, s):  # ノードuの親pにおけるスコアs
    s += score[u]
    ans[u] = s
    for c in child[u]:
        if p == c:
            continue
        dfs(u, c, s)


dfs(-1, 1, 0)
print(*ans[1:])
### BUGGY CODE ###

import sys
# sys.stdin = open('input.txt')

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

a = [i for i in range(n+1)]
a_rev = sorted(a, reverse=True)

ans = 0
for i in range(k, n+2):
    first = 0
    last = 0
    for j in range(i):
        first += a[j]
        last += a_rev[j]
    ans += last - first + 1

print(ans)

### FIXED CODE ###

import sys
# sys.stdin = open('input.txt')

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

MOD = 10**9 + 7
a = [i for i in range(n+1)]

ans = 0
for i in range(k, n+2):
    first = i * (a[0] + a[i-1]) / 2
    last = i * (a[-i] + a[-1]) / 2
    ans += last - first + 1
print(int(ans%MOD))
### BUGGY CODE ###

import bisect

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

ans = 0
for i in range(n):
    a = A[i]
    for b in B[bisect.bisect_right(B, a):]:
        ans += len(C[bisect.bisect_right(C, b):])
print(ans)

### FIXED CODE ###

import bisect, itertools

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

c_num = [0]*n
for i in range(n):
    c_num[i] = n - bisect.bisect_right(C, B[i])
c_accum = [0] + list(itertools.accumulate(c_num))

ans = 0
for i in range(n):
    b_index = bisect.bisect_right(B, A[i])
    ans += (c_accum[-1] - c_accum[b_index])
print(ans)
### BUGGY CODE ###

# ボールAとボールBをN個の箱に入れる
# A,Bを1つずつ同じ箱に入れることがあってもよい。
# まずAをN個の箱に1つずつ入れる
# その上で、BをN個の箱に1つずつ入れる（すでにAが入っているかどうか、区別する必要がない）
# AとBの個数の組み合わせを列挙し、そのすべてについて(N C (Aの個数)) * (N C (Bの個数))を計算した和が答え

import sys
readline = sys.stdin.readline

N,A,B,K = map(int,readline().split())

DIV = 998244353
n = (10 ** 6) * 2 # PyPyじゃないと通らない。 * 5が限界くらい
g1 = [1] * 2 + [0] * (n - 2) # 元テーブル
g2 = [1] * 2 + [0] * (n - 2) #逆元テーブル
inverse = [0, 1] + [0] * (n - 2) #逆元テーブル計算用テーブル

for i in range(2, n):
  g1[i] = (g1[i - 1] * i) % DIV
  inverse[i] = (-inverse[DIV % i] * (DIV // i)) % DIV
  g2[i] = (g2[i - 1] * inverse[i]) % DIV

def nCr(n, r, DIV):
  if (r < 0 or r > n):
    return 0
  r = min(r, n-r)
  return g1[n] * g2[r] * g2[n-r] % DIV

# AとBを足してKになる組み合わせを探索する
ans = 0
for a in range(N + 1):
  b = K - a * A
  if b < 0:
    break # a * Aの時点で負の数。これ以上の探索も不要。
  if b % B != 0:
    continue # 組み合わせを作れない
  if (b // B) > N:
    continue # 箱に入れられない
  # この時点で、Aがa個とBがb個で作れることが確定する
  # (N C (Aの個数)) * (N C (Bの個数))
  ans += (nCr(N, a, DIV) * nCr(N, b // B, DIV)) % DIV
  ans %= DIV
  
print(ans)

### FIXED CODE ###

# ボールAとボールBをN個の箱に入れる
# A,Bを1つずつ同じ箱に入れることがあってもよい。
# まずAをN個の箱に1つずつ入れる
# その上で、BをN個の箱に1つずつ入れる（すでにAが入っているかどうか、区別する必要がない）
# AとBの個数の組み合わせを列挙し、そのすべてについて(N C (Aの個数)) * (N C (Bの個数))を計算した和が答え

import sys
readline = sys.stdin.readline

N,A,B,K = map(int,readline().split())

DIV = 998244353
n = (10 ** 6) * 2 # PyPyじゃないと通らない。 * 5が限界くらい
g1 = [1] * 2 + [0] * (n - 2) # 元テーブル
g2 = [1] * 2 + [0] * (n - 2) #逆元テーブル
inverse = [0, 1] + [0] * (n - 2) #逆元テーブル計算用テーブル

for i in range(2, n):
  g1[i] = (g1[i - 1] * i) % DIV
  inverse[i] = (-inverse[DIV % i] * (DIV // i)) % DIV
  g2[i] = (g2[i - 1] * inverse[i]) % DIV

def nCr(n, r, DIV):
  if (r < 0 or r > n):
    return 0
  r = min(r, n-r)
  return g1[n] * g2[r] * g2[n-r] % DIV

# AとBを足してKになる組み合わせを探索する
ans = 0
for a in range(N + 1):
  b = K - a * A
  if b < 0:
    break # a * Aの時点で負の数。これ以上の探索も不要。
  if b % B != 0:
    continue # 組み合わせを作れない
  if (b // B) > N:
    continue # 箱に入れられない
  # この時点で、Aがa個とBがb個で作れることが確定する
  # (N C (Aの個数)) * (N C (Bの個数))
  ans += (nCr(N, a, DIV) * nCr(N, b // B, DIV)) % DIV
  ans %= DIV
  
print(ans)
### BUGGY CODE ###

h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I:=h*w]*I
m+=d,
q=[a:=~w+a*w+b]
d[a]=1
for s in q:
 for x in range(4):
  for z in range(k):
   y=~z,0,z+1,0;i,j=s//w+y[x],s%w+y[x^1];t=i*w+j;p=d[s]+1
   if'.'!=m[i][j]or d[t]<p:break
   if d[t]>p:q+=t,;d[t]=p
print(d[~w+f*w+g]%I-1)

### FIXED CODE ###

I=9**9
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I]*h*w
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j
   if(h>i>-1<j<w)-1or'.'<m[i][j]or d[t]<=d[s]:break
   if d[t]==I:q+=t,;d[t]=d[s]+1
print(d[~w+f*w+g]%I-1)