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

i = int(input())
p = 1
m = (10 **9)+7 
for ii in range(1,i+1):
	ii %= m
	p *= ii

print(p % m)
          

### FIXED CODE ###

i = int(input())
p = 1
M = 10 **9+7 
for ii in range(1,i+1):
	ii %= M
	p *= ii
	p %= M
print(p)
### BUGGY CODE ###

import heapq
import sys
sys.setrecursionlimit(10 ** 7)

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

event=[]
for _ in range(n):
    s,t,x=map(int,input().split())
    event.append([s-x,1,x])
    event.append([t-x,-1,x])

for i in range(q):
    event.append([int(input()),2,i])
event.sort()

ans=[0]*q

stop=set()
hq=[]
for e in event:
    t,op,x=map(lambda x:x,e)
    if op==1:
        heapq.heappush(hq,x)
        stop.add(x)
    elif op==-1:
        stop.remove(x)

    else:
        while hq and hq[0] not in stop:
            heapq.heappop(hq) 
        ans[x]=hq[0] if hq else -1
    
for x in ans:
    print(x)

### FIXED CODE ###

def main():
    from heapq import heappush, heappop
    import sys
    sys.setrecursionlimit(10 ** 7)

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

    event=[]
    for _ in range(n):
        s,t,x=map(int,input().split())
        event.append((s-x,1,x))
        event.append((t-x,-1,x))

    for i in range(q):
        event.append((int(input()),2,i))
    event.sort()

    ans=[0]*q

    stop=set()
    hq=[]
    for t,op,x in event:
        if op==1:
            heappush(hq,x)
            stop.add(x)
        elif op==-1:
            stop.remove(x)

        else:
            while hq and hq[0] not in stop:
                heappop(hq) 
            ans[x]=hq[0] if hq else -1
        
    for x in ans:
        print(x)

main()
### BUGGY CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
S = sum(A)
MOD = 998244353

dp1 = [[0] * (N + 1) for _ in range(S + 1)]
dp1[0][0] = 1

for t in range(1, N + 1):
    for r in range(S + 1):
        dp1[r][t] += dp1[r][t - 1] * 2
        dp1[r][t] += dp1[r - A[t - 1]][t - 1] if r - A[t - 1] >= 0 else 0
        dp1[r][t] %= MOD

dp2 = [[0] * (N + 1) for _ in range(S + 1)]
dp2[0][0] = 1

for t in range(1, N + 1):
    for r in range(S + 1):
        dp2[r][t] += dp2[r][t - 1]
        dp2[r][t] += dp2[r - A[t - 1]][t - 1] if r - A[t - 1] >= 0 else 0
        dp2[r][t] %= MOD

cnt = 0
for r in range((S + 1) // 2, S + 1):
    cnt += dp1[r][N]

ans = 3 ** N - 3 * cnt + (3 * (dp2[S // 2][N]) if S % 2 == 0 else 0)
ans %= MOD

print(ans)


### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
S = sum(A)
MOD = 998244353

# dp1 = [[0] * (N + 1) for _ in range(S + 1)]
dp1 = [[0] * (S + 1) for _ in range(N + 1)]
dp1[0][0] = 1

for t in range(1, N + 1):
    for r in range(S + 1):
        dp1[t][r] += dp1[t - 1][r] * 2
        dp1[t][r] += dp1[t - 1][r - A[t - 1]] if r - A[t - 1] >= 0 else 0
        dp1[t][r] %= MOD

dp2 = [[0] * (S + 1) for _ in range(N + 1)]
dp2[0][0] = 1

for t in range(1, N + 1):
    for r in range(S + 1):
        dp2[t][r] += dp2[t - 1][r]
        dp2[t][r] += dp2[t - 1][r - A[t - 1]] if r - A[t - 1] >= 0 else 0
        dp2[t][r] %= MOD

cnt = 0
for r in range((S + 1) // 2, S + 1):
    cnt += dp1[N][r]

ans = 3 ** N - 3 * cnt + (3 * (dp2[N][S // 2]) if S % 2 == 0 else 0)
ans %= MOD

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

def euclid(m,n):
    while m%n>0:
        m,n=n,m%n
    else:
        return n

def isprime_euclid2(N):
    if N<1:
        print 'N>2'
    elif N==2:
        return True
        
    euclid_list=[]
    for k in range(1,int(round(math.sqrt(N)))+1):
        euclid_list.append(euclid(N,k))
    temp=set(euclid_list)
    if len(temp)==1:
        return True
    else:
        return False  
           
import math
while True:
    try:
        n = int(raw_input())
        total = 0
        for k in range(n):
            if isprime_euclid2(int(raw_input())):
                total +=1
        print total
    except EOFError:
        break    

### FIXED CODE ###

import math
def is_prime(n):
    if n % 2 == 0 and n > 2: 
        return False
    return all(n % i for i in range(3, int(math.sqrt(n)) + 1, 2))
                      
while True:
    try:
        n = int(raw_input())
        total = 0
        for k in range(n):
            if is_prime(int(raw_input())):
                total +=1
        print total
    except EOFError:
        break
### BUGGY CODE ###

import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

n,k = nm()
l = nl()
f = list(filter(lambda x:x>0, l))
g = list(filter(lambda x:x<0, l))
f.sort(); g.sort(reverse=True)
pl = len(f); mi = len(g)
ze = n - pl - mi
tomi = pl*mi
if tomi >= k:
    def jud(z):
        ret = 0
        i = mi
        for x in f:
            while i and x*g[i-1] <= z: i -= 1
            ret += mi - i
        return ret
    ok,ng = 0,max(f)*min(g)-1
    while ok - ng > 1:
        mid = (ok+ng)//2
        if jud(mid) < k:
            ng = mid
        else:
            ok = mid
    print(ok)
    exit(0)

tomi += ze*(n-ze) + (ze-1)*ze//2
if tomi >= k:
    print(0); exit(0)

else:
    k -= tomi
    def jud2(z):
        ret = 0
        i = pl
        for e,x in enumerate(f):
            while i and f[i-1]*x > z: i -= 1
            ret += i - (e<=i-1)
        i = mi
        for e,x in enumerate(g):
            while i and g[i-1]*x > z: i -= 1
            ret += i - (e<=i-1)
        return ret//2
    ok,ng = 0,max(max(f+[0])**2, min(g+[0])**2)
    while ng - ok > 1:
        mid = (ok+ng)//2
        if jud2(mid) < k:
            ok = mid
        else:
            ng = mid
    print(ng)


### FIXED CODE ###

import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

n,k = nm()
l = nl()
f = list(filter(lambda x:x>0, l))
g = list(filter(lambda x:x<0, l))
f.sort(); g.sort(reverse=True)
pl = len(f); mi = len(g)
ze = n - pl - mi
tomi = pl*mi
if tomi >= k:
    def jud(z):
        ret = 0
        i = mi
        for x in f:
            while i and x*g[i-1] <= z: i -= 1
            ret += mi - i
        return ret
    ok,ng = 0,max(f)*min(g)-1
    while ok - ng > 1:
        mid = (ok+ng)//2
        if jud(mid) < k:
            ng = mid
        else:
            ok = mid
    print(ok)
    exit(0)

tomi += ze*(n-ze) + (ze-1)*ze//2
if tomi >= k:
    print(0); exit(0)

else:
    k -= tomi
    def jud2(z):
        ret = 0
        i = pl
        for e,x in enumerate(f):
            while i and f[i-1]*x > z: i -= 1
            ret += i - (e<=i-1)
        i = mi
        for e,x in enumerate(g):
            while i and g[i-1]*x > z: i -= 1
            ret += i - (e<=i-1)
        return ret//2
    ok,ng = 0,max(max(f+[0])**2, min(g+[0])**2)
    while ng - ok > 1:
        mid = (ok+ng)//2
        if jud2(mid) < k:
            ok = mid
        else:
            ng = mid
    print(ng)
### BUGGY CODE ###

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

ans = 0
mod = {}
last_mod = {}
for a in A:
    mod = {}
    # print(mod, last_mod)
    m = a % M
    for key in last_mod:
        mod[(key + m) % M] = last_mod[key]
    mod[m] = mod.get(m, 0) + 1

    # print(mod, last_mod)
    ans += mod.get(0, 0)

    last_mod = mod

print(ans)

### FIXED CODE ###

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

ans = 0
mod = 0
mod_dic = {0: 1}
for a in A:
    mod = (mod + a) % M
    mod_dic[mod] = mod_dic.get(mod, 0) + 1

for v in mod_dic.values():
    ans += v * (v - 1) // 2

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

# AtCoder Beginner Contest 157
# E - Simple String Queries
# https://atcoder.jp/contests/abc157/tasks/abc157_e
from bisect import bisect_left, insort_left
import sys
input = sys.stdin.readline
OFS = ord('a')
_ = input()
S = list(input()[:-1])

D = [[] for _ in [0]*26]
for i, s in enumerate(S):
    D[ord(s)-OFS].append(i)

for _ in [0]*int(input()):
    Q = input()[:-1].split()
    if Q[0] == '1':
        i, c = int(Q[1])-1, Q[2]

        s = ord(S[i])-OFS
        deli = bisect_left(D[s], i)
        del D[s][deli]
        insort_left(D[ord(c)-OFS], i)
        S[i] = c

    else:
        l, r = int(Q[1])-1, int(Q[2])-1

        cnt = 0
        for L in D:
            i = bisect_left(L, l)
            if i < len(L) and L[i] <= r:
                cnt += 1

        print(cnt)


### FIXED CODE ###

# AtCoder Beginner Contest 157
# E - Simple String Queries
# https://atcoder.jp/contests/abc157/tasks/abc157_e
from bisect import bisect_left, insort_left
import sys
input = sys.stdin.readline
OFS = ord('a')
_ = input()
S = list(input()[:-1])

D = [[] for _ in [0]*26]
for i, s in enumerate(S):
    D[ord(s)-OFS].append(i)

for _ in [0]*int(input()):
    Q = input()[:-1].split()
    if Q[0] == '1':
        i, c = int(Q[1])-1, Q[2]

        if S[i] != c:
            s = ord(S[i])-OFS
            D[s].pop(bisect_left(D[s], i))
            insort_left(D[ord(c)-OFS], i)
            S[i] = c

    else:
        l, r = int(Q[1])-1, int(Q[2])-1

        cnt = 0
        for L in D:
            i = bisect_left(L, l)
            if i < len(L) and L[i] <= r:
                cnt += 1

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

class SegTree:

    def __init__(self, N):
        self.N = N
        self.data = [0 for _ in range(2 * N)]

    def update(self, i, x):
        index = self.N + i - 1
        self.data[index] = x
        while index > 0:
            index = (index - 1) // 2  # parent
            self.data[index] = max(self.data[2 * index + 1], self.data[2 * index + 2])

    def _query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return 0
        if a <= l and r <= b:
            return self.data[k]
        else:
            vl = self._query(a, b, 2 * k + 1, l, (l + r) // 2)
            vr = self._query(a, b, 2 * k + 2, (l + r) // 2, r)
            return max(vl, vr)

    def query(self, a, b):
        return self._query(a, b, 0, 0, self.N)


def main():
    chars = [chr(ord('a') + i) for i in range(26)]
    N = int(input())
    pw2 = 1
    while pw2 < N:
        pw2 *= 2
    S = input()
    Q = int(input())
    query_list = [input().split(' ') for _ in range(Q)]
    trees = dict()
    for c in chars:
        trees[c] = SegTree(pw2)
    for i, c in enumerate(S):
        trees[c].update(i, 1)
    for query in query_list:
        if query[0] == '1':
            # type 1 query
            i = int(query[1]) - 1
            new_c = query[2]
            for c in chars:
                x = (1 if c == new_c else 0)
                trees[c].update(i, x)
        else:
            # type 2 query
            left = int(query[1]) - 1
            right = int(query[2]) - 1
            kinds = sum([trees[c].query(left, right + 1) for c in chars])
            print(kinds)


if __name__ == '__main__':
    main()

### FIXED CODE ###

class BIT:

    def __init__(self, N):
        # NOTE: 1-indexed
        self.N = N
        self.data = [0] * (N + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & (- i)
        return s

    def update(self, i, x):
        while i <= self.N:
            self.data[i] += x
            i += i & (- i)


def c2n(c):
    return ord(c) - ord('a')


def main():
    N = int(input())
    S = input()
    char_list = list(S)
    trees = [BIT(N) for _ in range(26)]
    for i, c in enumerate(S):
        trees[c2n(c)].update(i + 1, 1)
    Q = int(input())
    ans = list()
    for _ in range(Q):
        query = input().split()
        if query[0] == '1':
            _, i, c = query
            i = int(i) - 1
            before_c = char_list[i]
            char_list[i] = c
            trees[c2n(before_c)].update(i + 1, - 1)
            trees[c2n(c)].update(i + 1, 1)
        else:  # type '2'
            _, left, right = query
            left, right = int(left) - 1, int(right) - 1
            cnt = 0
            for i in range(26):
                n = trees[i].sum(right + 1) - trees[i].sum(left)
                if n > 0:
                    cnt += 1
            ans.append(cnt)
    for a in ans:
        print(a)


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

x = int(input())
 
for d in range(1, int(x**0.5)+1):
    if x % d == 0:
        for a in range(0,x+1):
            b = a - d
            if a**5 - b**5 == x:
                print(a, b)
                exit()

### FIXED CODE ###

x = int(input())
for a in range(-118,120):
    for b in range(-119, 119):
        if a**5 - b**5 == x:
            print(a,b)
            exit()
### BUGGY CODE ###

import sys

n, *inp = map(int, sys.stdin.buffer.read().split())
vvv = [0] + inp[0:n * 2:2]
www = [0] + inp[1:n * 2:2]
mp = iter(inp[n * 2 + 1:])
queries = []
required = [-1] * (n + 1)
for q in zip(mp, mp):
    queries.append(q)
    v, l = q
    while v > 0:
        if required[v] >= l:
            break
        required[v] = l
        v >>= 1

cache = [None] * (n + 1)
cache[0] = {0: 0}
for u in range(1, n + 1):
    r = required[u]
    if r == -1:
        continue
    par = cache[u >> 1]
    dp = par.copy()
    v = vvv[u]
    w = www[u]
    for cw, cv in par.items():
        nw = cw + w
        if nw > r:
            continue
        nv = cv + v
        if nw not in dp or dp[nw] < nv:
            dp[nw] = nv
    cache[u] = dp

buf = []
for u, l in queries:
    buf.append(max((v for w, v in cache[u].items() if w <= l), default=0))
print('\n'.join(map(str, buf)))


### FIXED CODE ###

import sys

n, *inp = map(int, sys.stdin.buffer.read().split())
vvv = [0] + inp[0:n * 2:2]
www = [0] + inp[1:n * 2:2]

weight_limit = 10 ** 5
precalc_limit = min(1 << 10, n + 1)
precalc = [[0] * (weight_limit + 1)]

for u in range(1, precalc_limit):
    v = vvv[u]
    w = www[u]
    dp = precalc[u >> 1][:]
    for x in range(weight_limit, w - 1, -1):
        nv = dp[x - w] + v
        if dp[x] < nv:
            dp[x] = nv
    precalc.append(dp)

buf = []
mp = iter(inp[n * 2 + 1:])
for u, l in zip(mp, mp):
    if u < precalc_limit:
        buf.append(precalc[u][l])
        continue
    dp_w = [0]
    dp_v = [0]
    while u >= precalc_limit:
        v = vvv[u]
        w = www[u]
        for i in range(len(dp_w)):
            nw = dp_w[i] + w
            if nw > l:
                continue
            nv = dp_v[i] + v
            dp_w.append(nw)
            dp_v.append(nv)
        u >>= 1
    ans = 0
    for w, v in zip(dp_w, dp_v):
        nv = v + precalc[u][l - w]
        if ans < nv:
            ans = nv
    buf.append(ans)

print('\n'.join(map(str, buf)))
### BUGGY CODE ###

from collections import deque
import copy
N,K = map(int, input().split())
p = list(map(int, input().split()))
que = deque([0]* K)
Max = deque([0]* K)
sumM = 0
sumq = 0
E = 0.0

for i in range(N):
    sumq -= que.popleft()
    sumq += p[i]
    que.append(p[i])
    if sumM < sumq:
        Max = copy.deepcopy(que)
        sumM = sumq
for num in Max:
    E += (num+1)* num //2/num
print(E)

### FIXED CODE ###

from collections import deque
import copy
N,K = map(int, input().split())
p = list([(i+1)* i/2/i for i in map(int, input().split())])
que = deque([0]* K)
sumM = 0
sumq = 0
E = 0.0

for i in range(N):
    sumq -= que.popleft()
    sumq += p[i]
    que.append(p[i])
    if E < sumq:
        E = sumq
print(E)
### BUGGY CODE ###

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

ans=[]

for i in range(1,N+1):
    a=Ai.index(i)+1
    ans.append(str(a))

print(' '.join(ans))

### FIXED CODE ###

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

# ans=[]
ans=[0]*N

# for i in range(1,N+1):
    # a=Ai.index(i)+1
    # ans.append(str(a))
for i in range (N):
    ans[Ai[i]-1]=str(i+1)

print(' '.join(ans))
### BUGGY CODE ###

def z_algo(S):
    N = len(S)
    A = [0]*N
    A[0] = N
    i, j = 1, 0
    while i < N:
        while i+j < N and S[j] == S[i+j]:
            j += 1
        A[i] = j
        if not j:
            i += 1
            continue
        k = 1
        while i+k < N and k+A[k] < j:
            A[i+k] = A[k]
            k += 1
        i += k
        j -= k
    return A

n = int(input())
s = input()
ans = 0
for i in range(n):
  A = z_algo(s[i:])
  for j in range(1, n-i):
    m = min(j, A[j])
    ans = max(m, ans)
print(ans)


### FIXED CODE ###

def z_algo(S):
    N = len(S)
    A = [0]*N
    A[0] = N
    i, j = 1, 0
    while i < N:
        while i+j < N and S[j] == S[i+j]:
            j += 1
        A[i] = j
        if not j:
            i += 1
            continue
        k = 1
        while i+k < N and k+A[k] < j:
            A[i+k] = A[k]
            k += 1
        i += k
        j -= k
    return A

n = int(input())
s = input()
ans = 0
for i in range(n):
  A = z_algo(s[i:])
  for j in range(1, n-i):
    m = min(j, A[j])
    ans = max(m, ans)
print(ans)
### BUGGY CODE ###

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

for i in range(m):
    a.sort(reverse = True)
    a[0] = a[0] // 2

print(sum(a))

### FIXED CODE ###

import heapq

n, m = map(int, input().split())
a = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(a)  # aを優先度付きキューに

for _ in range(m):
    tmp_min = heapq.heappop(a)
    heapq.heappush(a, (-1)*(-tmp_min//2))  # 計算誤差の関係で-1を2回かけてます
print(-sum(a))
### BUGGY CODE ###

from bisect import bisect,bisect_left
import sys
import itertools
input=sys.stdin.readline

def main():
    n,q=map(int,input().split())
    xst=[]
    for i in range(n):
        s,t,x=map(int,input().split())
        xst.append([x,s,t])
    xst.sort()
    d=[None]*q
    for i in range(q):
        d[i]=[int(input()),i]
    ans=[-1]*q
    for u in xst:
        x,s,t=u
        left=s-x
        right=t-x-1
        a=bisect(d,[left])
        b=bisect(d,[right,q+1])
        for u in d[a:b]:
            ans[u[1]]=x
        d=list(itertools.chain(d[:a],d[b:]))
    for u in ans:
        print(u)

if __name__=="__main__":
    main()

### FIXED CODE ###

from bisect import bisect,bisect_left
import sys
input=sys.stdin.readline

def main():
    n,q=map(int,input().split())
    xst=[]
    for i in range(n):
        s,t,x=map(int,input().split())
        xst.append([x,s-x,t-x])
    xst.sort()
    d=[None]*q
    for i in range(q):
        d[i]=int(input())
    ans=[-1]*q
    skip=[-1]*q
    for u in xst:
        x ,left ,right = u
        a=bisect_left(d,left)
        b=bisect_left(d,right)
        while a < b:
            if skip[a] == -1:
                ans[a]=x
                skip[a]=b
                a+=1
            else:
                a=skip[a]
    for u in ans:
        print(u)

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

import sys
sys.setrecursionlimit(100000)
q = int(input())

l = []
x = ""
y = ""
def lcs(yIndex, xIndex):
    global l, x, y
    if xIndex < 0 or yIndex < 0:
        return 0
    elif x[xIndex] == y[yIndex]:
        return 1 + lcs(yIndex - 1, xIndex - 1)
    else:
        return max(lcs(yIndex, xIndex - 1), lcs(yIndex - 1, xIndex))

for i in range(q):
    x = input()
    y = input()

    print(lcs(len(y) - 1, len(x) - 1))


### FIXED CODE ###

q = int(input())

for i in range(q):
    x = input()
    y = input()
 
    l = []
    for j, s in enumerate(x):
        l.append([])
        l[j].append(-1)
        if j == 0:
            endPos = y.find(s)
            if endPos != -1: 
                l[j].append(endPos)
        else:
            for k, t in enumerate(l[j - 1][:-1]):
                endPos = y.find(s, t + 1)
                if endPos != -1:
                    l[j].append(min(endPos, l[j - 1][k + 1]))
                else:
                    l[j].append(l[j - 1][k + 1])
            endPos = y.find(s, l[j - 1][-1] + 1)
            if endPos != -1:
                l[j].append(endPos)

    print(len(l[-1]) - 1)
### BUGGY CODE ###

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

arrow = [0]*(N-1)
list1 = [1]
list_total = [1]
s = 0
for j in range(N):
  if s == N-1:
    break
  
  list2 = []
  for x in list1:
    for i in range(M):
      if route[i][0] == x and route[i][1] not in list_total:
        arrow[route[i][1]-2] = x
        list2.append(route[i][1])
        list_total.append(route[i][1])
        s = s+1
      if route[i][1] == x and route[i][0] not in list_total:
        arrow[route[i][0]-2] = x
        list2.append(route[i][0])
        list_total.append(route[i][0])
        s = s+1
      
  list1 = list2
print('Yes')
for y in arrow:
  print(y)



### FIXED CODE ###

from collections import deque

n, m = map(int, input().split())
a = [[] for _ in range(n)]
for i in range(m):
    x, y = map(int, input().split())
    a[x - 1].append(y - 1)
    a[y - 1].append(x - 1)
c = [0] * n
que = deque([])
que.append(0)
while len(que) > 0:
    e = que.popleft()
    for i in a[e]:
        if c[i] > 0:
            continue
        c[i] = e + 1
        que.append(i)
print("Yes")
for i in range(1, n):
    print(c[i])
### BUGGY CODE ###

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

sum = 0
for i in range(0,n-1):
    k=i+1
    for j in range(k,n):
        sum += a[i]^a[j]
        sum = sum%(10**9+7)
print(sum%(10**9+7))

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
ans = 0
for j in range(61):
  ones = 0
  for i in A:
    if i>>j & 1:
      ones += 1
  ans += 2**j*((n-ones)*ones)
print(ans%(10**9+7))
### BUGGY CODE ###

import math

def f(x,y,z):
    # x,y,z = A,x,B
    return math.floor(x*y/z) - x*math.floor(y/z)

a,b,n = map(int,input().split())
if n<b:
    print(math.floor(a*n/b))
else:
    k = n%b
    ret = f(a, b-1, b)
    for j in range(1, k+1):
        ret = max(ret, f(a, b*k-1, b))
    print(ret)

### FIXED CODE ###

import math
def f(x,y,z):
    # x,y,z = A,x,B
    return math.floor(x*y/z) - x*math.floor(y/z)
a,b,n = map(int,input().split())
if n<b:
    print(math.floor(a*n/b))
else:
    print(f(a, b-1, b))
### BUGGY CODE ###

import collections, sys

n = int(input())
s = []
for _ in range(0,n):
  s.append(input())

if len(set(s)) == 1:
  print(s[0])
  sys.exit()  

c = collections.Counter(s)
max = c.most_common()[0][1]

l = []
l.append(c.most_common()[0][0])
for i in range(0,len(s)):
  if c.most_common()[i][1] == max:
    l.append(c.most_common()[i][0])
  else:
    break
ll = sorted(set(l))
for ls in ll:
  print(ls)

### FIXED CODE ###

import collections, sys

n = sys.stdin.readline()
s = []
for _ in range(0,int(n)):
  s.append(sys.stdin.readline().replace('\n',''))

c = collections.Counter(s)
max = c.most_common()[0][1]
l = sorted(list(dict(filter(lambda x: x[1]==max, c.items())).keys()))
for k in l:
  print(k)
### BUGGY CODE ###

import copy

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

N = 13
MOD = 10 ** 9 + 7

s = input()
rs = reversed(s)

dp = [0 for i in range(N)]
dp[0] = 1
zeros = [0 for i in range(N)]

for i, si in enumerate(rs):
    nextdp = zeros[:]

    for j in range(10):
        c = 0
        if si == "?":
            c = (j * 10 ** i) % N
        elif j == 0:
            c = (int(si) * 10 ** i) % N
        else:
            break

        for k in range(N):
            nextdp[(k + c) % N] = (nextdp[(k + c) % N] + dp[k]) % MOD

    dp = nextdp

print(dp[5])


### FIXED CODE ###

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

N = 13
MOD = 10 ** 9 + 7

s = input()[::-1]

dp = [0 for i in range(N)]
nextdp = [0 for i in range(N)]
zeros = [0 for i in range(N)]
dp[0] = 1

r = 1
for i, si in enumerate(s):
    nextdp = zeros[:]

    for j in range(10):
        jj = j
        if si == "?":
            pass
            # c = (j * 10 ** i) % N
        elif j == 0:
            jj = int(si)
        else:
            break

        for k in range(N):
            l = (k + r * jj) % N
            nextdp[l] = (nextdp[l] + dp[k]) % MOD

    dp = nextdp
    r = r * 10 % N

print(dp[5])
### BUGGY CODE ###

a,b,x=map(int,input().split())
c=0

for i in range(a,b+1):
    if i%x==0:
        c+=1
        
print(c)

### FIXED CODE ###

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

print(b//x-(a-1)//x)