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

# -*- coding: utf-8 -*-
# B - Sum of Three Integers
K, S = map(int, input().split())

count = 0
for x in range(K+1):
    for y in range(K+1):
        for z in range(S-x-y+1):
          if z > K or x + y + z != S:
            continue
          count += 1
            
# 出力
print(count)


### FIXED CODE ###

# -*- coding: utf-8 -*-
# B - Sum of Three Integers
K, S = map(int, input().split())

count = 0
for x in range(K+1):
    for y in range(K+1):
        z = S - x - y
        if z >= 0 and z <= K:
            count += 1

# 出力
print(count)
### BUGGY CODE ###

import sys,gc

    
A=[]
fp =0
bp =0

n=int(raw_input())
while n:
    s = raw_input()
    if s[0] == 'i':
        A.append(s[7:])
        fp += 1
    elif s[6] == ' ':
        i=-1
        try:
            while True:
                i = A[i+1:].index(s[7:])
        except:
            if i!=-1:
                del A[i]
                fp -=1
    elif s[6] == 'F':
        A.pop()
        fp -=1
    elif s[6] == 'L':
        A[bp]=-1
        bp +=1
    n -=1

for e in A[bp:fp+1][::-1]:
    if e!=-1:
        print int(e),

### FIXED CODE ###

import sys,gc
    
A=[]
fp =0
bp =0

n=int(raw_input())
while n:
    s = raw_input()
    if s[0] == 'i':
        A.append(int(s[7:]))
        fp += 1
    elif s[6] == ' ':
        try:
            i = A[::-1].index(int(s[7:]))
            if i!=-1:
                del A[-i-1]
                fp -=1
        except:
            pass
    elif s[6] == 'F':
        A.pop()
        fp -=1
    elif s[6] == 'L':
        bp +=1
    n -=1

for e in A[bp:fp+1][::-1]:
    print int(e),
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()
ac=[]
for i in range(n-1):
  if s[i:i+2]=="AC":
    ac.append(i)
for i in range(q):
  l,r=map(int,input().split())
  print(sum(1 for i in ac if l-1<=i<=r-2))

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
ac=[0]*n
for i in range(n-1):
  if s[i:i+2]=="AC":
    ac[i]=ac[i-1]+1
  else:
    ac[i]=ac[i-1]
for i in range(q):
  l,r=map(int,input().split())
  if l==1:
    print(ac[r-2])
  else:
    print(ac[r-2]-ac[l-2])
### BUGGY CODE ###

from collections import Counter


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors


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

c = Counter(A)
ans = 0
for a in A:
    # 同じ数が複数ある
    if c[a] >= 2:
        continue

    # 約数を取得
    divi = make_divisors(a)
    for d in divi:
        # チェック中と同じ値は無視
        if d == a:
            continue
        # 約数がハッシュにあるなら割り切れる数が1個はあるので性質を満たさない
        if d in c:
            break
    # 約数が1個もハッシュにない＝割り切れる数がないので性質を満たす
    else:
        ans += 1
print(ans)


### FIXED CODE ###

from collections import Counter

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

c = Counter(A)
p = [True]*(10**6+1)

for k, v in c.items():
    t = k*2
    while t <= 10**6:
        p[t] = False
        t += k

ans = 0
for a in A:
    if c[a] == 1 and p[a]:
        ans += 1
print(ans)
### BUGGY CODE ###

from numpy import*
n,*a=map(int,open(0).read().split())
l=[0]*n
for i,v in enumerate(a,1):
  l[v-1]=i
b=array([0,n+1])
c=0
for i,v in enumerate(l,1):
  j=searchsorted(b,v)
  c+=(b[j]-v)*(v-b[j-1])*i
  b=union1d(b,[v])
print(c)

### FIXED CODE ###

root=lambda x:x if par[x]==x else root(par[x])
same=lambda x,y:root(x)==root(y)
def unite(*z):
  x,y=map(root,z)
  if x!=y:
    if rank[x]<rank[y]:
      par[x]=y
      size[y]+=size[x]
    else:
      par[y]=x
      size[x]+=size[y]
      if rank[x]==rank[y]:rank[x]+=1
n,*a=map(int,open(0).read().split())
*par,=range(n)
rank=[1]*n
size=[1]*n
b=[0]*n
for i,t in enumerate(a):b[t-1]=i
c=0
for k in b[::-1]:
  l=r=1
  if k>0 and a[k-1]>a[k]:
    l+=size[root(k-1)]
    unite(k-1,k)
  if k+1<n and a[k+1]>a[k]:
    r+=size[root(k+1)]
    unite(k+1,k)
  c+=l*r*a[k]
print(c)
### BUGGY CODE ###

# https://atcoder.jp/contests/abc122/tasks/abc122_c

N, Q = [int(x) for x in input().split()]
S = input().strip()

for i in range(Q):
    l, r = [int(x) for x in input().split()]
    print(sum([S[i:i+2] == 'AC' for i in range(l - 1, r - 1)]))


### FIXED CODE ###

# https://atcoder.jp/contests/abc122/tasks/abc122_c

N, Q = [int(x) for x in input().split()]
S = input().strip()
m = [0] * N
for i in range(1, N):
    if S[i-1:i+1] == 'AC':
        m[i] = m[i-1] + 1
    else:
        m[i] = m[i-1]

for i in range(Q):
    l, r = [int(x) for x in input().split()]
    print(m[r - 1] - m[l - 1])
### BUGGY CODE ###

N=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]
count=0
if sum(A)<sum(B):
    print(-1)
else:
    dif=[A[i]-B[i] for i in range(N)]
    if min(dif)>=0:
        print(0)
    else:
        difsort=sorted(dif)
        pluslist=[i for i in difsort if i>=0]
        zero=difsort.index(pluslist[0])
        minum=len(difsort[:zero])
        maxsort=difsort[::-1]
        absum=abs(sum(difsort[:zero]))
        sumlist=[sum(maxsort[0:i+1]) for i in range(len(pluslist))]
        while sumlist[count]<absum:
            count+=1
        
        print(count+1+minum)

### FIXED CODE ###

N=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]
count=0
if sum(A)<sum(B):
    print(-1)
else:
    dif=[A[i]-B[i] for i in range(N)]
    if min(dif)>=0:
        print(0)
    else:
        difsort=sorted(dif)
        plist=[i for i in difsort if i>=0][::-1]
        mlist=[i for i in difsort if i<0]
        mnum=len(mlist)
        msum=sum(mlist)
        for i in range(len(plist)):
            if msum>=0:
                break
            msum+=plist[i]
            count+=1
            
        
        print(count+mnum)
### BUGGY CODE ###

import itertools


N, M = map(int, input().split())
lst = [list(map(int, input().rstrip().split())) for n in range(N)]
maximum = 0
for pickup in itertools.permutations(lst, M):
    for q in range(M):
        m = abs(sum([pickup[n][0] for n in range(M)])) + abs(sum([pickup[n][1] for n in range(M)])) + abs(sum([pickup[n][2] for n in range(M)]))
        if m >= maximum:
            maximum = m

print(maximum)


### FIXED CODE ###

N, M = map(int, input().split())
lst = [list(map(int, input().rstrip().split())) for n in range(N)]
maximum = -float("inf")
for i in [-1, 1]:
    for j in [-1, 1]:
        for k in [-1, 1]:
            sum_lst = []
            for n in range(N):
                num = lst[n][0] * i + lst[n][1] * j + lst[n][2] * k
                sum_lst.append(num)
            maximum = max(abs(sum(sorted(sum_lst)[:M])), maximum)
            
print(maximum)
### BUGGY CODE ###

import sys
import math

lines = sys.stdin.readlines()

N = int(lines[0])
X = set([])

for i in range(N):
  Si = str(lines[i+1].split('\n')[0])
  X = X | set([Si])

print(len(X))

### FIXED CODE ###

import sys
import math

lines = sys.stdin.readlines()
N = int(lines[0])
X = []

for i in range(N):
  Si = str(lines[i+1].split('\n')[0])
  X.append(Si)

X.sort()

z = 1
for i in range(N-1):
  if X[i] != X[i+1]:
    z +=1
print(z)
### BUGGY CODE ###

#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
from functools import reduce
import sys
import math
import bisect
import random
from functools import lru_cache
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return list(map(float, sys.stdin.readline().split()))
def LS():return sys.stdin.readline().split()
def SR(n): return [list(sys.stdin.readline())[:-1] for i in range(n)]
def IR(n): return [int(sys.stdin.readline()) for i in range(n)]
def LIR(n): return [list(map(int, sys.stdin.readline().split())) for i in range(n)]
def LSR(n): return [list(map(list, sys.stdin.readline().split())) for i in range(n)]
_gcd = lambda x, y: _gcd(y, x%y) if (x%y) else y
_lcm = lambda x, y: x*y // _gcd(x, y)
def gcd(*numbers):
    return reduce(_gcd, numbers)
def lcm(*numbers):
    return reduce(_lcm, numbers)
sys.setrecursionlimit(1000000)
INF = float('inf')
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]


def main():
    N = I()
    A = LI()
    t = [0, 0, 0]
    for a in A:
        t[a-1] += 1
    A, B, C = t

    dp = [[[0]*(C+1) for i in range(B+C+1)] for j in range(A+B+C+1)]

    for k in range(C+1):
        for j in range(B+C+1):
            for i in range(A+B+C+1):
                if (i==0) and (j==0) and (k==0):
                    continue
                dp[i][j][k] += N/(i+j+k)
                d = dp[i][j][k]
                if (i<A+B+C):
                    dp[i+1][j][k] += (i+1)*d/(i+1+j+k)
                if (i>0) and (j<B+C):
                    dp[i-1][j+1][k] += (j+1)*d/(i+j+k)
                if (j>0) and (k<C):
                    dp[i][j-1][k+1] += (k+1)*d/(i+j+k)

    print(dp[A][B][C])

main()


### FIXED CODE ###

import sys

def I(): return int(sys.stdin.readline())
def LI(): return list(map(int, sys.stdin.readline().split()))

def main():
    N = I()
    a = LI()
    t = [0, 0, 0]
    for ai in a:
        t[ai-1] += 1
    A, B, C = t
    E = B+C

    dp = [[0 if (i+j==0) else N/(i+j) for j in range(E+1)] for i in range(N+1)]

    for k in range(C+1):
        for i in range(N+1):
            dp[i][E] = 0 if (i+E+k==0) else N/(i+E+k)
        for j in range(E+1):
            for i in range(N+1):
                z = i+j+k
                if (not z):
                    continue
                d = dp[i][j]
                if (i<N):
                    dp[i+1][j] += (i+1)*d/(z+1)
                if (i>0) and (j<E):
                    dp[i-1][j+1] += (j+1)*d/z
                if (j>0) and (k<C):
                    dp[i][j-1] = (k+1)*d/z + N/z

    print(dp[A][B])

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

import sys
input = sys.stdin.readline
input = sys.stdin.buffer.readline

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
def TI(): return tuple(map(int,input().split()))
def RN(N): return [input().strip() for i in range(N)]

def a(A,B,x): return (A*x//B)-A*(x//B)

def main():
    A,B,N = MI()
    max = 0
    for x in range(0, N+1):
        if max < a(A,B,x):
            max = a(A,B,x)
    
    print(max)



    


if __name__ == "__main__":
	main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
input = sys.stdin.buffer.readline

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
def TI(): return tuple(map(int,input().split()))
def RN(N): return [input().strip() for i in range(N)]

def a(A,B,x): return (A*x//B)-A*(x//B)

def main():
    A,B,N = MI()
    """
    max = 0
    m = 0
    for x in range(0, N+1):
        ai = a(A,B,x)
        if max < ai :
            max = ai
        elif ai<0 and m == 0:
            max = ai
            m +=1

        print(x,a(A,B,x))
    """
    if N >= B:
        x = (N//B)*B-1
    elif N == B:
        x = N-1
    elif N < B:
        x = N
    print(a(A,B,x))

    



    


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

from collections import deque
N,M = map(int, input().split())
AB_s = sorted([sorted(list(map(int, input().split()))) for _ in range(M)])

answer = [0] * N
queue = deque([1])
answer[0] = N

while len(queue) > 0:
    P = queue.popleft()
    POPS = []
    for i, AB in enumerate(AB_s):
        # P の含まれるパスだったら
        if P in AB:
            # P じゃない方が Q
            Q = AB[0] if AB[1] == P else AB[1]
            # 到達してなかったら道標を置く
            if answer[Q-1] == 0:
                answer[Q-1] = P
                queue.append(Q)
            POPS.append(i)
    for i, POP in enumerate(POPS[::-1]):
        AB_s.pop(POP)

if min(answer) == 0:
    print("No")
else:
    print("Yes")
    for i in range(1,N):
        print(answer[i])


### FIXED CODE ###

from collections import deque
N,M = map(int, input().split())
AB_s = [list(map(int, input().split())) for _ in range(M)]

MAP = [[] for _ in range(N)]
for AB in AB_s:
    A, B = map(int, AB)
    MAP[A-1].append(B)
    MAP[B-1].append(A)
answer = [0] * N
queue = deque([1])
answer[0] = N
while len(queue) > 0:
    P = queue.popleft()
    if True:
        for Q in MAP[P-1]:
            if answer[Q-1] == 0:
                answer[Q-1] = P
                queue.append(Q)
if min(answer) == 0:
    print("No")
else:
    print("Yes")
    for i in range(1,N):
        print(answer[i])
### BUGGY CODE ###

n,m = map(int,input().split())
a = [list(map(int,input().split())) for _ in range(m)]
a = sorted(a,key=lambda x:x[1])
ans = [0]
for a_ in a:
    for i,k in enumerate(ans):
        if a_[0]<k and a_[1]>=k:
            break
        elif i==len(ans)-1:
            ans.append(a_[1])
            break
print(len(ans)-1)

### FIXED CODE ###

n,m = map(int,input().split())
a = [list(map(int,input().split())) for _ in range(m)]
a = sorted(a,key=lambda x:x[1])
ans = [0]
for a_ in a:
    for i,k in enumerate(ans):
        if a_[0]<k and a_[1]>=k:
            break
        elif i==len(ans)-1:
            ans.append(a_[1])
            break
print(len(ans)-1)
### BUGGY CODE ###

n=int(input())
a=list(map(str,input().split()))
s=[0]*n

for i in range(1,n):
  s[i-1]=a.count(str(i))
  continue
  
for i in s:
  print(i)
  
  
  

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
s=[0]*n

for i in a:
  s[i-1]+=1

for i in s:
  print(i)
### BUGGY CODE ###

def main():
  n,k=map(int,input().split())
  p=list(map(int,input().split()))
  c=list(map(int,input().split()))
  ans=-10**18
  for i in range(n):
    start,count=i,1
    val=c[start]
    while p[start]-1!=i: #ループ部分
      start=p[start]-1
      count+=1
      val+=c[start]
    start=i
    if val>0:
      a=(k//count-1)*val #一周目はループのどの部分から始めるのが最適かわからないので
      ans=max(a,ans)
      num=count+k%count
    else:
      a=0
      num=min(k,count)
    for _ in range(num):
      start=p[start]-1
      a+=c[start]
      ans=max(a,ans)
  print(ans)
main()

### FIXED CODE ###

from numba import jit
@jit
def main():
  n,k=map(int,input().split())
  p=list(map(int,input().split()))
  c=list(map(int,input().split()))
  ans=-10**18
  for i in range(n):
    start,count=i,1
    val=c[start]
    while p[start]-1!=i: #ループ部分
      start=p[start]-1
      count+=1
      val+=c[start]
    start=i
    if val>0:
      a=(k//count-1)*val #一周目はループのどの部分から始めるのが最適かわからないので
      ans=max(a,ans)
      num=count+k%count
    else:
      a=0
      num=min(k,count)
    for _ in range(num):
      start=p[start]-1
      a+=c[start]
      ans=max(a,ans)
  print(ans)
main()
### BUGGY CODE ###

import sys
N = int(input())
A = list(map(int, input().split()))
A_max = max(A)
if A_max == 1:
    print("pairwise coprime")
    sys.exit()
dp = [0]*(A_max+10)
p = 0
s = 0
for i in range(2, A_max+1):
    c = 0
    if dp[i] == 0:
        dp[i] = 1
        for j in range(i, A_max+1, i):
            dp[j] = 1
        dp[A_max] = 0
        for j in range(N):
            if A[j] % i == 0:
                c += 1
        if c >= 2:
            p = 1
        if c == N:
            s = 1
if p == 0:
    print("pairwise coprime")
elif s == 0:
    print("setwise coprime")
else:
    print("not coprime")

### FIXED CODE ###

import sys
N = int(input())
A = list(map(int, input().split()))
A_max = max(A)
if A_max == 1:
    print("pairwise coprime")
    sys.exit()
dp = [0]*(A_max+10)
K = [0]*(A_max+10)
p = 0
s = 0
for i in range(N):
    K[A[i]] += 1
for i in range(2, A_max+1):
    c = 0
    if dp[i] == 0:
        dp[i] = 1
        for j in range(i, A_max+1, i):
            dp[j] = 1
            c += K[j]
        if c >= 2:
            p = 1
        if c == N:
            s = 1
if p == 0:
    print("pairwise coprime")
elif s == 0:
    print("setwise coprime")
else:
    print("not coprime")
### BUGGY CODE ###

def resolve():
    import sys
    sys.setrecursionlimit(100000)
    H = int(input())

    def battle(n):
        if n == 1:
            return 1
        return battle(n / 2) * 2 + 1

    print(battle(H))

    return
  
resolve()

### FIXED CODE ###

def resolve():
    import sys
    sys.setrecursionlimit(1000000)
    H = int(input())

    def battle(n):
        if n == 1:
            return 1
        return battle(n // 2) * 2 + 1

    print(battle(H))

    return


resolve()
### BUGGY CODE ###

N = int(input())
A = (list(map(int, input().split(' '))))
D = [0]*(pow(10,6)+1)
ans = 0
for i in A:
    D[i] += 1
for i in A:
    flg = True
    if D[i] > 1:
        continue
    for j in range(1,int(pow(i,0.5))+2):
        if not i%j:
            if D[j] and i != j:
                flg = False
                break
            if j != i//j and D[i//j] and i//j != i:
                    flg = False
                    break
    if flg:
        ans += 1
print(ans)

### FIXED CODE ###

from collections import Counter
N = int(input())
A = Counter(list(map(int,input().split(' '))))
ans = 0
m = max(A.keys())
L = [1]*(10**6+1)
for i in sorted(A.keys()):
    if not L[i]:
        continue
    if A[i] == 1:
        ans += 1
    for j in range(i,m+1,i):
        L[j] = 0
print(ans)
### BUGGY CODE ###

n = int(input())
li_a = list(map(int, input().split()))
q = int(input())
li_bc = list()

for i in range(q):
    li_bc.append(tuple(map(int, input().split())))

for l in li_bc:
    li_a = [a if a != l[0] else l[1] for a in li_a]
    print(sum(li_a))

### FIXED CODE ###

n = int(input())
li_a = list(map(int, input().split()))
dic_a = {}

for a in li_a:
    dic_a[a] = dic_a.get(a, 0) + 1

q = int(input())
li_bc = list()

for i in range(q):
    li_bc.append(tuple(map(int, input().split())))


answer = sum(li_a)
for l in li_bc:
    b = l[0]
    c = l[1]

    diff = (c - b) * dic_a.get(b, 0)
    if b in dic_a.keys():
        dic_a[c] = dic_a.get(c, 0) + dic_a.get(b, 0)
        dic_a[b] = 0
        answer += diff
    else:
        pass
    print(answer)
### BUGGY CODE ###

n = int(input())

An = list(map(int, input().split()))

ans = 1

for i in range(n):
    ans *= An[i]

if ans <= 10 ** 18:
    print(ans)
else :
    print('-1')


### FIXED CODE ###


n = int(input())
An = [int(x) for x in input().split()]
An.sort(reverse=True)

if 0 in An:
    print(0)
    exit()

j = 10 ** 18
ans = 1
for i in range(n):
    if ans > j:
        print(-1)
        quit()
    ans *= An[i]

if ans > j :
    print(-1)
    
else :
    print(ans)
### BUGGY CODE ###

S = int(input())
Smod = [0]*2019
for i in range(len(str(S))+1):
  Smod[(S%(10**i))%2019] += 1

ans = 0
for j in range(2019):
  ans += Smod[j] * (Smod[j]-1) // 2
print(ans)

### FIXED CODE ###

S = input()
Sliststr = list(S)
Slist = [int(s) for s in Sliststr]
Smod = [0]
mod10 = [1]
count = [0]*2019
ans = 0
for i in range(len(S)-1):
  mod10.append(mod10[i]*10%2019)
for i in range(len(S)):
  Smod.append((Smod[i]+Slist[-i-1]*mod10[i])%2019)
for i in range(len(Smod)):
  count[Smod[i]] += 1
for i in range(2019):
  ans += count[i] * (count[i]-1) // 2
print(ans)
### BUGGY CODE ###

N = int(input())
S = [input() for i in range(N)]

gacha_list = []
for i in S:
    if i not in gacha_list:
        gacha_list.append(i)

print(len(gacha_list))

### FIXED CODE ###

N = int(input())
S = sorted([input() for i in range(N)])

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

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

n = int(input())
A = list(map(int,input().split()))
mod = (10**9) + 7
t = 0
for i in range(n-1):
    for j in range(i+1,n):
        t += (A[i]%mod) * (A[j]%mod)
    s = t%mod
print(s)

### FIXED CODE ###

n = int(input())
A = list(map(int,input().split()))
mod = (10**9) + 7
t = 0
sum = 0
for i in range(1,n):
    sum += A[i]
for i in range(n-1):
    t += (A[i]*sum)%mod
    sum -=  A[i+1]
t = t%mod
print(t)
### BUGGY CODE ###

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

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

for j in range(1, N+1):
    for k in range(N+1):
        for s in range((N+1)*(L+1)):
            if s < X[j-1]:
                dp[j][k][s] = dp[j-1][k][s]
            if k >= 1 and s >= X[j-1]:
                dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-X[j-1]]
ans = 0
for k in range(1, N+1):
    ans += dp[N][k][k*A]
print(ans)

### FIXED CODE ###

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

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

for j in range(1, N+1):
    for k in range(N+1):
        for s in range((N+1)*(L+1)):
            if s < X[j-1]:
                dp[j][k][s] = dp[j-1][k][s]
            if k >= 1 and s >= X[j-1]:
                dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-X[j-1]]
ans = 0
for k in range(1, N+1):
    ans += dp[N][k][k*A]
print(ans)
### BUGGY CODE ###

import sys

input = sys.stdin.buffer.readline

n, x, mod = map(int, input().split())
ans = 0
temp = x
num = 1
while temp < mod:
    temp *= x
    num += 1


A = [0] * (mod + 1)

if temp == mod:
    A[1] = x % mod
    ans += A[1]
    for i in range(2, num + 1):
        A[i] = A[i - 1] * A[i - 1] % mod
        ans += A[i]
        # print(ans)
    print(ans)
    exit()

kouho = {}
if n < mod:
    A[1] = x % mod
    ans += A[1]
    for i in range(2, n + 1):
        A[i] = A[i - 1] * A[i - 1] % mod
        ans += A[i]
        # print(ans)
else:
    A[1] = x
    ans += A[1]
    kouho[A[1]] = 1
    temp = A[1]
    for i in range(2, mod + 1):
        A[i] = temp * temp % mod
        if A[i] in kouho:
            migi = i
            break
        kouho[A[i]] = i
        temp = A[i]
    saisho = 0
    hidari = kouho[A[i]]
    saisho = sum(A[1:hidari])
    # for i in range(1, hidari):
    #     saisho += A[i]
    cycle_val = sum(A[hidari:migi])
    # cycle_val = 0
    # for i in range(hidari, migi):
    #     cycle_val += A[i]

    cycle = migi - hidari
    kaisu = n // cycle
    amari = n % cycle - (hidari - 1)
    amari %= cycle
    kaisu = (n - (amari + hidari - 1)) // cycle
    amari_val = sum(A[hidari : hidari + amari])
    # amari_val = 0
    # for i in range(hidari, hidari + amari):
    #     amari_val += A[i]
    ans = saisho + cycle_val * kaisu + amari_val
print(ans)



### FIXED CODE ###

import sys

input = sys.stdin.buffer.readline

n, x, mod = map(int, input().split())
ans = 0
temp = x
num = 1
# while temp < mod:
#     temp *= x
#     num += 1


A = [0] * (mod + 1)

kouho = {}
if n < mod:
    A[1] = x % mod
    ans += A[1]
    for i in range(2, n + 1):
        A[i] = A[i - 1] * A[i - 1] % mod
        ans += A[i]
        # print(ans)
else:
    A[1] = x
    ans += A[1]
    kouho[A[1]] = 1
    temp = A[1]
    i = 1
    migi = 1
    for i in range(2, mod + 1):
        A[i] = temp * temp % mod
        if A[i] in kouho:
            migi = i
            break
        kouho[A[i]] = i
        temp = A[i]
    saisho = 0
    hidari = kouho[A[i]]
    saisho = sum(A[1:hidari])
    # for i in range(1, hidari):
    #     saisho += A[i]
    cycle_val = sum(A[hidari:migi])
    # cycle_val = 0
    # for i in range(hidari, migi):
    #     cycle_val += A[i]
    cycle = migi - hidari
    if cycle >= 2:

        kaisu = n // cycle
        amari = n % cycle - (hidari - 1)
        amari %= cycle
        kaisu = (n - (amari + hidari - 1)) // cycle
        amari_val = sum(A[hidari : hidari + amari])
        # amari_val = 0
        # for i in range(hidari, hidari + amari):
        #     amari_val += A[i]
        ans = saisho + cycle_val * kaisu + amari_val
    else:
        ans = 0
        if cycle == 0:
            for j in range(1, i + 1):
                ans += A[j]
        else:
            for j in range(1, i + 1):
                ans += A[j]
            ans += (n - i) * A[j]
print(ans)