import strutils, sequtils

iterator readInt(): int {.closure.} =
    while true:
        let line = stdin.readLine.split.map(parseInt)
        for x in line:
            yield x

const MOD = 998244353
func powMod(a, b, m: int): int =
    result = 1
    var 
        a = a mod m
        b = b
    while b > 0:
        if (b and 1) == 1:
            result = result * a mod m
        a = a * a mod m
        b = b shr 1

func findPrimitiveRoot(n: int): int =
    var phi = n - 1
    var factors = newSeq[int]()
    for i in 2..n:
        if i * i > phi:
            break
        if phi mod i == 0:
            factors.add(i)
            while phi mod i == 0:
                phi = phi div i
    if phi > 1:
        factors.add(phi)
    for res in 1..<n:
        var ok = true
        for factor in factors:
            if powMod(res, (n - 1) div factor, n) == 1:
                ok = false
                break
        if ok:
            return res
    -1

const primitiveRoot = findPrimitiveRoot(MOD)

proc ntt(a: var seq[int]) =
    let n = a.len
    var m = n
    while m > 1:
        let mh = m shr 1
        let wm = powMod(primitiveRoot, (MOD - 1) div m, MOD)
        var w = 1
        for i in 0..<mh:
            for j in countup(i, n - 1, m):
                let k = j + mh
                let
                    a0 = a[j]
                    a1 = a[k]
                a[j] = a0 + a1
                if a[j] >= MOD:
                    a[j] -= MOD
                a[k] = (a0 - a1 + MOD) * w mod MOD
            w = w * wm mod MOD
        m = mh
    
proc intt(a: var seq[int]) =
    let n = a.len
    var m = 2
    while m <= n:
        let mh = m shr 1
        let wm = powMod(primitiveRoot, MOD - 1 - (MOD - 1) div m, MOD)
        var w = 1
        for i in 0..<mh:
            for j in countup(i, n - 1, m):
                let k = j + mh
                let
                    a0 = a[j]
                    a1 = a[k] * w mod MOD
                a[j] = a0 + a1
                if a[j] >= MOD:
                    a[j] -= MOD
                a[k] = a0 - a1
                if a[k] < 0:
                    a[k] += MOD
            w = w * wm mod MOD
        m = m shl 1
    let inv = powMod(n, MOD - 2, MOD)
    for i in 0..<n:
        a[i] = a[i] * inv mod MOD

proc solve() =
    var input = readInt
    var n = input()
    let p = input()

    let q = findPrimitiveRoot(p)
    var indexTable = newSeq[int](p)
    indexTable[0] = 0
    var k = 1
    for i in 0..<p - 1:
        indexTable[k] = i
        k = k * q mod p
    var indexTableSum = newSeq[int](p)
    for i in 1..<p:
        indexTableSum[i] = indexTableSum[i - 1] + indexTable[i]
        if indexTableSum[i] >= p - 1:
            indexTableSum[i] -= p - 1
    
    func comb(a, b: int): int =
        (indexTableSum[a] - indexTableSum[b] - indexTableSum[a - b] + 2 * (p - 1)) mod (p - 1)

    var len = 1
    while len < (p - 1) * 2:
        len *= 2

    var count = newSeq[int](len)
    count[0] = 1
    while n > 0:
        let m = n mod p
        n = n div p

        var a = newSeq[int](len)
        for i in 0..m:
            a[comb(m, i)] += 1
        
        ntt(count)
        ntt(a)

        for i in 0..<len:
            count[i] = count[i] * a[i] mod MOD
        
        intt(count)

        for i in countdown(len - 1, p - 1):
            count[i - p + 1] += count[i]
            if count[i - p + 1] >= MOD:
                count[i - p + 1] -= MOD
            count[i] = 0
    
    var ans = 0
    k = 1
    for i in 0..<p - 1:
        ans = (ans + count[i] * k) mod MOD
        k = k * q mod p
    
    echo ans

solve()