スコアを巡回置換のサイズの最小公倍数から求めるところまでの考察は公式解説（ https://atcoder.jp/contests/abc226/editorial/2878 ）と同じです。

ここで、ありえるスコアの種類を考えます。例えば素因数2であれば、2個のループを25個作る時が最大で25個、素因数3は最大で16個、となり、また2の個数と3の個数がそれぞれ最大付近は同時には実現しません。また、25より大きい素因数については高々1 個しか含まれないことなどから、スコアの種類はあまり大きくないことが予想されます。この問題では\(N=50\)の時まで計算すれば良いので、スコアの種類がどれくらい増えるか実際に計算してみます。これは次のように求められます。

import math
import functools

def lcm(a, b):
    return a * b // math.gcd(a, b)

@functools.lru_cache(None)
def calc(N: int):
    if N == 1:
        return {1}
    ans = {N}
    for k in range(1, N):
        for score in calc(N - k):
            ans.add(lcm(k, score))
    return ans

for n in range(1, 51):
    print(n, len(calc(n)))

実行すると、\(N=50\)の時スコアの種類は\(1056\)であることがわかります。このことから、それぞれのスコアをとる順列の個数をすべて保持していっても十分間に合いそうです。

実際、上記のアルゴリズムを少し拡張して、\(k\)を要素1を含む巡回置換に含まれる要素数として捉えると、その巡回置換の取り方が\((N-1)!/(N-k)!\)となり、残りの要素数が\(N-k\)となります。残りの要素でありえるスコア\(s\)と個数\(c\)のそれぞれについて、スコア\(\mathrm{LCM}(s, k)\)、個数\(c*(N-1)!/(N-k)!\)を足していくdpを考えることができます。これの計算量は\(N\)までのスコアの種類を\(f(N)\)として\(O(Nf(N))\)となり十分間に合います。

あとはそれぞれのスコアを\(K\)乗して足し合わせれば良いです。

提出例： https://atcoder.jp/contests/abc226/submissions/27120542

import functools
import math

MOD = 998244353  # type: int

@functools.lru_cache(None)
def npermk(n, k):
    ans = 1
    for i in range(k):
        ans *= n - i
        ans %= MOD
    return ans

@functools.lru_cache(None)
def calc(N: int):
    if N == 0:
        return {1: 1}
    ans = {}  # {score: count}
    for k in range(1, N+1):
        # k: length of loop including 1
        factor = npermk(N-1, k-1)
        for s, c in calc(N-k).items():
            score = s * k // math.gcd(s, k)
            count = c * factor
            if score not in ans:
                ans[score] = 0
            ans[score] += count
            ans[score] %= MOD
    return ans

def solve(N: int, K: int):
    ans = 0
    for s, c in calc(N).items():
        ans += c * pow(s, K, MOD) % MOD
        ans %= MOD
    print(ans)
    return

N, K = map(int, input().split())
solve(N, K)