Problem:


Score : 500 points

Problem Statement

There are N blocks arranged in a row. Let us paint these blocks.

We will consider two ways to paint the blocks different if and only if there is a block painted in different colors in those two ways.

Find the number of ways to paint the blocks under the following conditions:

For each block, use one of the M colors, Color 1 through Color M, to paint it. It is not mandatory to use all the colors.

There may be at most K pairs of adjacent blocks that are painted in the same color.

Since the count may be enormous, print it modulo 998244353.

Constraints

All values in input are integers.

1 \leq N, M \leq 2 \times 10^5

0 \leq K \leq N - 1

Input

Input is given from Standard Input in the following format:

N M K

Output

Print the answer.

Sample Input 1

3 2 1

Sample Output 1

6

The following ways to paint the blocks satisfy the conditions: 112, 121, 122, 211, 212, and 221. Here, digits represent the colors of the blocks.

Sample Input 2

100 100 0

Sample Output 2

73074801

Sample Input 3

60522 114575 7559

Sample Output 3

479519525



Sample input:
3 2 1


Sample output:
6

Submission status: Runtime Error

Solution code:
import itertools

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


def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p


p = 998244353
N = n   # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

ans = 0

l2 = m*(m-1)**(n-k-2)
for _k in range(k, -1, -1):
    # print(_k)

    l2 %= p
    l2 *= (m - 1)

    ncr = cmb(n - 1, _k, p)
    ans += ncr * l2
    ans %= p


print(ans)

Submission status: Runtime Error

Solution code:
n, m, k = map(int, input().split())
z = 998244353
if n <= k+1:
    a = 1
    for i in range(n):
        a = a*m%z
    print(a)
else:
    d = m
    for i in range(n-1):
        d = d*(m-1)%z
    a = [d]
    b = [1]
    c = 0
    for i in range(k):
        b.append(int(b[-1]*(n-i-2)/(i+1)%z))
    for i in range(k):
        a.append(int((a[-1]*b[i+1]%z)/b[i]/(m-1)))
    for i in range(k+1):
        c = (c+a[i])%z
    print(c)

Submission status: Runtime Error

Solution code:
import itertools

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


def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p


p = 998244353
N = n   # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

ans = 0

l2 = m*(m-1)**(n-k-2)
for _k in range(k, -1, -1):
    # print(_k)
    l2 *= (m - 1)
    l2 %= p
    ncr = cmb(n - 1, _k, p)
    ans += ncr * l2
    ans %= p


print(ans)

Submission status: Runtime Error

Solution code:
n,m,k = map(int, input().split())
#ncr
mod = 998244353
class Combination:
    def __init__(self, N):
        self.fac = [1] * (N + 1)
        for i in range(1, N + 1):
            self.fac[i] = (self.fac[i - 1] * i) % mod
        self.invmod = [1] * (N + 1)
        self.invmod[N] = pow(self.fac[N], mod - 2, mod)
        for i in range(N, 0, -1):
            self.invmod[i - 1] = (self.invmod[i] * i) % mod 
    def ncr(self, n, k):  # nCk
        return self.fac[n] * self.invmod[k] % mod * self.invmod[n - k] % mod 
cmb = Combination(n)
ans = 0
for i in range(k+1):
  a = m*(m-1)**(n-i-1)%p
  a *= cmb.ncr(n,i)
  ans += a%p
print(ans%p)

Submission status: Runtime Error

Solution code:
n, m, k = map(int, input().split())
z = 998244353
if n <= k+1:
    a = 1
    for i in range(n):
        a = a*m%z
    print(a)
else:
    d = m
    for i in range(n-1):
        d = d*(m-1)%z
    a = [d]
    b = [1]
    c = 0
    for i in range(k):
        b.append(int(b[-1]/(i+1)*(n-i-1)%z))
    for i in range(k):
        a.append(int((a[-1]*b[i+1]%z)/b[i]/(m-1)))
    for i in range(k+1):
        c = (c+a[i])%z
    print(c)

Submission status: Runtime Error

Solution code:
n, m, k = map(int, input().split())
z = 998244353
if n <= k+1:
    a = 1
    for i in range(n):
        a = a*m%z
    print(a)
else:
    a = [m*((m-1)**(n-1))]
    b = [1]
    c = 0
    for i in range(k):
        b.append(int(b[-1]/(i+1)*(n-i-1)%z))
    for i in range(k):
        a.append(int((a[-1]*b[i+1]%z)/b[i]/(m-1)))
    for i in range(k+1):
        c = (c+a[i])%z
    print(c)

Submission status: Runtime Error

Solution code:
n, m, k = map(int, input().split())
z = 998244353
if n <= k+1:
    a = 1
    for i in range(n):
        a = a*m%z
    print(a)
else:
    a = [m*((m-1)**(n-1))]
    b = [1]
    c = 0
    for i in range(k):
        b.append(int(b[-1]/(i+1)*(n-i-1)%z))
    for i in range(k):
        a.append(int((a[-1]*b[i+1]%z)/b[i]/(m-1)))
    for i in range(k+1):
        c += a[i]
    print(c%z)

Submission status: Runtime Error

Solution code:
n, m, k = map(int, input().split())
if n <= k+1:
    print(m**n)
else:
    a = [m*((m-1)**(n-1))]
    b = [1]
    c = 0
    for i in range(k):
        b.append(int(b[-1]/(i+1)*(n-i-1)))
    for i in range(k):
        a.append(int((a[-1]*b[i+1])/b[i]/(m-1)))
    for i in range(k+1):
        c += a[i]
    print(c%998244353)

Submission status: Runtime Error

Solution code:
n, m, k = map(int, input().split())
if n <= k+1:
    print(m**n)
else:
    a = [m*((m-1)**(n-1))]
    b = [1]
    c = 0
    for i in range(k):
        b.append(int(b[-1]/(i+1)*(n-i-1)))
    for i in range(k):
        a.append(int((a[-1]*b[i+1])/b[i]/(m-1))
    for i in range(k+1):
        c += a[i]
    print(c%998244353)

Submission status: Runtime Error

Solution code:
n, m, k = map(int, input().split())
if n <= k+1:
    print(m**n)
else:
    a = [m*((m-1)**(n-1))]
    b = [1]
    c = 0
    for i in range(k):
        b.append(int(b[-1]/(i+1)*(n-i-1))%998244353)
    for i in range(k):
        a.append(int(((a[-1]*b[i+1])%998244353)/b[i]/(m-1))%998244353)
    for i in range(k+1):
        c += a[i]
    print(c%998244353)

Submission status: Runtime Error

Solution code:
N,M,K= list(map(int, input().split()))
mod = 998244353

def cmbinit(n):
    fac = [0]*n
    finv = [0]*n
    inv = [0]*n
    fac[0]=fac[1] = 1
    finv[0]=finv[1] = 1
    inv[1] = 1
    for i in range(2,n):
        fac[i] = fac[i-1]*i %mod
        inv[i] = mod - inv[mod%i] * (mod//i) %mod
        finv[i] = finv[i-1] * inv[i]%mod
    
    return fac,finv

def cmb(n,r,fac,finv):
    if n < r:
        return 0
    if n < 0 or r < 0:
        return 0
        
    return fac[n] * (finv[r] * finv[n - r] % mod) %mod




ans = 0
fac,finv = cmbinit(N)
for k in range(K+1):
    ans += (M * pow(M-1, N-k-1, mod) * cmb(N-1,k,fac,finv))%mod


print(ans%mod)

Submission status: Runtime Error

Solution code:
n, m, k = map(int, input().split())
if n <= k+1:
    print(n**m)
else:
    a = [m*((m-1)**(n-1))]
    b = [1]
    c = 0
    for i in range(k):
        b.append(int(b[i]/(i+1)*(n-i-1))%998244353)
    for i in range(k):
        a.append(int(((a[i]*b[i+1])%998244353)/b[i]/(m-1))%998244353)
    for i in range(k+1):
        c += a[i]
    print(c%998244353)

Submission status: Runtime Error

Solution code:
n,m,k=map(int,input().split())
mod=998244353
if m==1:print(0 if k!=n-1 else 1);exit()
fact=[1]*(n-1+1)
inv=[1]*(n-1+1)
for i in range(2,n-1+1):
    fact[i]=i*fact[i-1]%mod
inv[-1]=pow(fact[-1],mod-2,mod)
for i in range(n-1,1,-1):
    inv[i-1]=inv[i]*i%mod
def comb(x,y):return fact[x]*inv[y]%mod*inv[x-y]%mod
ans=0
po=pow(m-1,n-1,mod)*m%mod
ue=fact[n-1]
iii=pow(m-1,mod-2,mod)%mod
for i in range(k+1):
    ans+=comb(n-1,i)po%mod
    po*=iii
    po%=mod
print(ans%mod)

Submission status: Runtime Error

Solution code:
N,M,K= list(map(int, input().split()))
mod = 998244353

def cmbinit(n):
    fac = [0]*n
    finv = [0]*n
    inv = [0]*n
    fac[0]=fac[1] = 1
    finv[0]=finv[1] = 1
    inv[1] = 1
    for i in range(2,n):
        fac[i] = fac[i-1]*i %mod
        inv[i] = mod - inv[mod%i] * (mod//i) %mod
        finv[i] = finv[i-1] * inv[i]%mod
    
    return fac,finv

def cmb(n,r,fac,finv):
    if n < r:
        return 0
    if n < 0 or r < 0:
        return 0
    else:
        return fac[n] * (finv[r] * finv[n - r] % mod) %mod




ans = 0
fac,finv = cmbinit(N)
for k in range(K+1):
    ans += (M * pow(M-1, N-k-1, mod) * cmb(N-1,k,fac,finv))%mod


print(ans%mod)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(2000)

from math import factorial
N,M,K= list(map(int, input().split()))
mod = 998244353

def cmbinit(n):
    fac = [0]*n
    finv = [0]*n
    inv = [0]*n
    fac[0]=fac[1] = 1
    finv[0]=finv[1] = 1
    inv[1] = 1
    for i in range(2,n):
        fac[i] = fac[i-1]*i %mod
        inv[i] = mod - inv[mod%i] * (mod//i) %mod
        finv[i] = finv[i-1] * inv[i]%mod
    
    return fac,finv

def cmb(n,r,fac,finv):
    if n < r:
        return 0
    if n < 0 or r < 0:
        return 0
    else:
        return fac[n] * (finv[r] * finv[n - r] % mod) %mod




ans = 0
fac,finv = cmbinit(N)
for k in range(K+1):
    ans += (M * pow(M-1, N-k-1, mod) * cmb(N-1,k,fac,finv))%mod


print(ans%mod)

Submission status: Runtime Error

Solution code:
import math

N,M,K = (int(x) for x in input().split())

x=0
for i in range(K+1):
    x = x + (M * ((M - 1)**(N-i-1)) * int(math.factorial(N-1) / (math.factorial(i) * math.factorial(N-i-1))))
    x = x % 998244353
print(x)

Submission status: Runtime Error

Solution code:
n, m, k = map(int, input().split())
MOD = 998244353

def modpow(a, n, p):
  if n == 1:
    return a % p 
  elif n % 2 == 1:
    return a * modpow(a, n-1, p) % p
  else:
    return modpow(a, n//2, p) **2 % p
dp = [0]*(k+1)
dp[0] = m* modpow(m-1, n-1, MOD) % MOD
for j in range(1, k+1):
  bunsi = 1
  for i in range(n-1-j+1, n):
    bunsi = bunsi * i % MOD

  bunbo = 1
  for i in range(1, j+1):
    bunbo = bunbo * i % MOD

  comb = bunsi * modpow(bunbo, MOD-2, MOD) % MOD
  dp[j] = (m * modpow(m-1, n-1-j, MOD)*comb % MOD + dp[j-1]) % MOD
print(dp[k])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

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

table = [0]
inv_table = [0]
M_table = []

tmp = pow(M - 1, N - 1, mod)
for i in range(K + 1):
    if i > 0:
        tmp *= pow(M - 1, mod - 2, mod)
        tmp %= mod
    M_table.append(tmp)

tmp = 1
for i in range(1, N + 1):
    tmp *= i
    tmp %= mod
    table.append(tmp)

tmp = 1
for i in range(1, N + 1):
    tmp *= pow(i, mod - 2, mod)
    tmp %= mod
    inv_table.append(tmp)

def cmb(n, r):
    if r == 0:
        return 1
    if n == r:
        return 1
    return table[n] * inv_table[r] * inv_table[n - r]

if M == 1:
    if K >= cmb(N, 2):
        print(1)
    else:
        print(0)

ans = 0
for i in range(K + 1):
    ans += M * M_table[i] * cmb(N - 1, i)
    ans %= mod

print(ans)

Submission status: Runtime Error

Solution code:
n, m, k = map(int, input().split())
MOD = 998244353

def modpow(a, n, p):
  if n == 1:
    return a % p 
  elif n % 2 == 1:
    return a * modpow(a, n-1, p) % p
  else:
    return modpow(a, n//2, p) **2 % p

bunsi = 1
for i in range(n-1-k+1, n):
  bunsi = bunsi * i % MOD

bunbo = 1
for i in range(1, k+1):
  bunbo = bunbo * i % MOD

comb = bunsi * modpow(bunbo, MOD-2, MOD) % MOD
print(m * modpow(m-1, n-1-k, MOD)*modpow(m, k, MOD)*comb % MOD)

Submission status: Runtime Error

Solution code:
N,M,K=map(int,input().split(' '))
mod = 998244353
ans =0
fac=[0]*N
inv=[0]*N
finv=[0]*N
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2,N):
    fac[i] = fac[i-1]*i%mod
    inv[i] = mod-inv[mod%i]*(mod//i)%mod
    finv[i] = finv[i-1]*inv[i]%mod
def COM(n,k):
    if (n < k):
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n]*(finv[k]*finv[n-k]%mod)%mod
for i in range(K+1):
    #print(M*pow(M-1,N-1-i,mod),COM(N-1,i))
    ans += M*pow(M-1,N-1-i,mod)*COM(N-1,i)
    ans %=mod
print(ans)

Submission status: Runtime Error

Solution code:
#------------------------------warmup----------------------------
import os
import sys
from io import BytesIO, IOBase
 
BUFSIZE = 8192
 
 
class FastIO(IOBase):
    newlines = 0
 
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
 
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
 
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
 
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
 
#-------------------game starts now-----------------------------------------------------

def modfun(val, mod):
  while(val>=mod) val-=mod
  return val

n,m,k=map(int,input().split())
a=[0]*(k+1)
a[0]=1
for i in range(1,k+1):
    a[i]=(a[i-1]*(n-i))//(i)
e=[0]*(k+1)
mod=998244353
e[0]=pow(m-1,n-1-k,mod)
for i in range(1,k+1):
    e[i]=modfun((e[i-1])*((m-1) , mod))
ans=0
for i in range(k+1):
    ans=modfun(ans + modfun(modfun((e[-1-i])*(a[i]), mod), mod), mod)
    
m=modfun(m, mod)
print((ans*m)%mod)

Submission status: Runtime Error

Solution code:
N, M, K = map(int, input().split())
ans = 0
fn = 1
fk = 1
a = M * (M-1)**N
for k in range(K+1):
    n = N - k
    a //= M-1
    if k == 0:
        b = 1
    else:
        fn *= N-k
        fk *= k
        b = fn // fk
    ans += a * b
    ans %= 998244353
print(ans)

Submission status: Runtime Error

Solution code:
a,b,K=map(int,input().split())
C=998244353
fac=[0]*a #階乗 fac[i]=i!
finv=[0]*a# i!の逆元
inv=[0]*a
N=a-1
def com_init():
	fac[0],fac[1],finv[0],finv[1]=1,1,1,1
	inv[1]=1
	for i in range(2,N+1):
		fac[i]=fac[i-1]*i%C
		inv[i]=C-inv[C%i]*(C//i)%C#ある数の逆元
		finv[i]=finv[i-1]*inv[i]%C
def com(m,k):
	if m<k: return 0
	elif m<0 or k<0:return 0
	else:
		return fac[m]*(finv[k]*finv[m-k]%C)%C
com_init()
bfac=[0]*a
bfac[0]=1
for i in range(1,a):
  bfac[i]=bfac[i-1]*(b-1) %C
ans=0

for i in range(K+1):
  ans+= com(a-1,i)*bfac[a-1-i]%C
print(ans*b%C)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

N, K = [int(i) for i in input().split()]
A_list = [int(i) for i in input().split()]

dp = defaultdict(lambda: None)

city = 1
loop_len = 0
ans = 0
for i in range(N):
    if dp[city] is not None or i >= K:
        ans = city
        loop_len = i - dp[city]
        break

    dp[city] = i
    city = A_list[city - 1]

if K >= dp[city]:
    index = (K - dp[city]) % loop_len
    ans = list(dp)[dp[city]:][index]

print(ans)

Submission status: Runtime Error

Solution code:
import math
N, M, K = map(int, input().split())
ans = 0
fk = 1
a = M * (M-1)**N
for k in range(K+1):
    n = N - k
    a //= M-1
    if k == 0:
        b = 1
    else:
        fk *= k
        b = n**k // fk
    ans += a * b
    ans %= 998244353
print(ans)

Submission status: Runtime Error

Solution code:
// 5/10 リアルタイム参加
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
using Graph = vector<vector<int>>;

const int mod = 998244353;
// const int mod = 1000000007;

struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
 
  // for prime mod
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};
 
mint f(int n) {
  if (n == 0) return 1;
  mint x = f(n/2);
  x *= x;
  if (n%2 == 1) x *= 2;
  return x;
}
 
mint choose(int n, int a) {
  mint x = 1, y = 1;
  rep(i,a) {
    x *= n-i;
    y *= i+1;
  }
  return x / y;
}

int main() {
    ll N, M, K;
    cin >> N >> M >> K;

    // ll ans = 100;
    // rep(i, 99) {
    //     ans = (ans * 99) % MOD;
    //     // cout << ans << endl;
    // }

    // cout << (ll)(100.0 * pow(99.0, 99.0)) % 998244353 << endl;
    // cout << ans << endl;

    mint ans(0);
    mint m(M);

    ans += m * (m - 1).pow(N - 1);

    for (int i = 1; i <=K; i++) {
        ans += m * choose(N - 1, i) * (m - 1).pow(N - i - 1);
    }
    
    // rep(i, K) {

    // }

    // cout << m.x << endl;
    // cout << (m - 1).x << endl;
    cout << ans.x << endl;
}

Submission status: Runtime Error

Solution code:
def main():
    n = int(input())
    S = [input() for _ in [0]*n]
    s2 = []
    s3 = []
    for s in S:
        temp = [0, 0]
        m = 0
        now = 0
        for i in s:
            if i == "(":
                now += 1
            else:
                now -= 1
            m = min(m, now)
        temp[0] = m
        temp[1] = (s.count("(")-s.count(")"))
        if temp[1] >= 0:
            s2.append(temp)
        else:
            s3.append(temp)
    s2.sort(key=lambda x: (-x[0]))
    s3.sort(key=lambda x: (x[1]))
    cnt = 0
    # print(s2)
    # print(s3)
    for i, j in s2:
        if cnt+i < 0:
            print("No")
            return
        cnt += j
    for i, j in s3:
        if cnt+i < 0:
            print("No")
            return
        cnt += j
    if cnt != 0:
        print("No")
        return
    print("Yes")


main()

Submission status: Runtime Error

Solution code:
N,M,K = map(int,input().split())
# dp = [[0]*(K+2) for _ in range(2)]

# print (1)
# dp[0][0] = M
# MOD = 998244353
# for n in range(N-1):
#     n = n % 2
#     a = (n+1) % 2
#     dp[a] = [0]*(K+2) 
#     for k in range(K+1):
        
        
        
#         dp[a][k] += dp[n][k] * (M-1)
#         dp[a][k+1] += dp[n][k]
#         dp[a][k] %= MOD
#         dp[a][k+1] %= MOD
# #print (dp)
# print(sum(dp[(N+1)%2][:-1]))
import numpy as np
old = np.zeros(K+1).astype(np.int)
MOD = 998244353
old[0] = M
for n in range(N-1):
    new = old*(M-1)
    new[1:] += old[:K]
    new %= MOD
    old = new
print (sum(new)%MOD)

Submission status: Runtime Error

Solution code:
from scipy.special import comb
a = comb(n, r, exact=True)
N, M, K = map(int, input().split())
ans = 0
for i in range(K+1):
  ans += M*(M-1)**(N-1-i)*comb((N-1-i), i)
print(ans)

Submission status: Runtime Error

Solution code:
def power_func(a,n,p):
  bi=str(format(n,"b"))#2進表現に
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 998244353
N = 10 ** 6
fact = [1, 1] + [0] * (N-2)
factinv = [1, 1] + [0] * (N-2)
inv = [0, 1] + [0] * (N-2)

for i in range(2, N + 1):
    fact[i] = (fact[i-1] * i) % p
    inv[i] = (-inv[p % i] * (p // i)) % p
    factinv[i] = (factinv[i-1] * inv[i-1]) % p

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

ret = 0
for i in range(k+1):
  ret += ((cmb(n-1, i, p) * m % p) * (power_func(m-1, n-1-i, p))) % p
print(ret % p)

Submission status: Runtime Error

Solution code:
def power_func(a,n,p):
  bi=str(format(n,"b"))#2進表現に
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 998244353
N = 10 ** 6
fact = [1, 1] + [0] * (N-2)
factinv = [1, 1] + [0] * (N-2)
inv = [0, 1] + [0] * (N-2)

for i in range(2, N + 1):
    fact[i] = (fact[-1] * i) % p
    inv[i] = (-inv[p % i] * (p // i)) % p
    factinv[i] = (factinv[-1] * inv[-1]) % p

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

ret = 0
for i in range(k+1):
  ret += ((cmb(n-1, i, p) * m % p) * (power_func(m-1, n-1-i, p))) % p
print(ret % p)

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
cnt=[]
for i in range(n):
	s=input().rstrip()
	l=s.count("(")
	r=s.count(")")
	minus=0
	now=0
	for j in range(len(s)):
		if s[j]=="(":
			now+=1
		else:
			now-=1
			minus=min(minus,now)
	cnt.append((l,r,s,minus))
cnt.sort(key=lambda x:x[1]-x[0])
plus=[]
minus=[]
for x in cnt:
	if x[0]-x[1]>=0:
		plus.append(x)
	else:
		minus.append(x)
plus.sort(key=lambda x:-x[3])
minus.sort(key=lambda x:-(x[0]-x[1])-x[3])
l=r=0
for x in plus:
	for i in range(len(x[2])):
		if x[2][i]=="(":
			l+=1
		else:
			r+=1
		if l<r:
			print("No")
			exit()
for x in minus:
	for i in range(len(x[2])):
		if x[2][i]=="(":
			l+=1
		else:
			r+=1
		if l<r:
			print("No")
			exit()
if l==r:
	print("Yes")
else:
	print("No")

Submission status: Runtime Error

Solution code:
n,m,k=map(int,input().split())
dp=[[0]*(n-1) for _ in range(n)]
dp[0][0]=m
for i in range(1,n):
    dp[i][0]=dp[i-1][0]*(m-1)
for i in range(n-1):
  for j in range(n-2):
    dp[i+1][j+1]=dp[i][j]+(m-1)*dp[i][j+1]
print(sum(dp[n-1][:k+1])% 998244353)

Submission status: Runtime Error

Solution code:
N, M, K = map(int, input().split())
mod = 998244353
# 全て異なる色で塗った場合のリストを作る
d = [0] * (N+1)
d[0] = M
for i in range(N):
    d[i+1] = d[i] * (M-1) % mod

def createFacArr(n, mod):
    '''
    二項係数計算用の配列の作成

    Parameters
    n : int
        配列のサイズ
    mod : int
        あまり

    Returns
    fac : list
        階乗のリスト
    finv : list
        modの逆元のリスト
    ivn : list
    '''
    fac = [0] * n
    finv = [0] * n
    inv = [0] * n
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 1, 1
    inv[1] = 1
    for i in range(2, n):
        fac[i] = fac[i-1] * i % mod
        inv[i] = mod - inv[mod%i] * (mod // i) % mod
        finv[i] = finv[i-1] * inv[i] % mod
    return fac, finv

def comb(n ,k, mod, fac, finv):
    '''
    二項係数の計算

    Parameters
    n : int
        元集合
    k : int
        元集合から選択する数
    mod : int
        あまり
    fac : list
        階乗のリスト
    finv : list
        逆元のリスト
    
    Returns
    c : int
        nCkの組み合わせの数
    '''
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod

fac, finv = createFacArr(N, mod)
ans = d[N-1]
#print(d)
for i in range(K):
    ans += d[N-2-i] * comb(N-1, i+1, mod, fac, finv)
    ans %= mod

print(ans)

Submission status: Runtime Error

Solution code:
N,M,K = list(map(int,input().split()))

MOD = 998244353
F = 10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, F + 1 ):
    g1.append( ( g1[-1] * i ) % MOD )
    inverse.append( ( -inverse[MOD % i] * (MOD//i) ) % MOD )
    g2.append( (g2[-1] * inverse[-1]) % MOD )

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

A = [M*pow(M-1,N-1-i,MOD) % MOD for i in range(K+1)]
A = [A[i] * cmb(N-1,i,MOD) % MOD for i in range(K+1)]
print(sum(A) % MOD)

Submission status: Runtime Error

Solution code:
#左からn個目でendが特定の色の場合に
N,M,K = list(map(int,input().split()))

def xgcd(a, b):
  x0, y0, x1, y1 = 1, 0, 0, 1
  while b != 0:
    q, a, b = a // b, b, a % b
    x0, x1 = x1, x0 - q * x1
    y0, y1 = y1, y0 - q * y1
  return a, x0, y0
def modinv(a, m):
  g, x, y = xgcd(a, m)
  if g != 1:
    raise Exception('modular inverse does not exist')
  else:
    return x % m
def combination(n, k, mod=1e9+7) -> int:
  ret = 1
  for i in range(1, k+1):
    ret = (ret * (n-k+i) * modinv(i, mod))%mod
  return int(ret)

def pow(base, exponent, mod=1e9+7) -> int:
  if exponent == 0:
    return 1
  if exponent > 1:
    d,m = divmod(exponent, 2)
    return (base**m * pow(base, d, mod)**2 ) % mod
  else:
    return base

m = 998244353
res = 0
B = 1
mi = modinv(M-1,m)
A = M * pow(M-1,N-1,m)
for k in range(K+1):
  if k>0:
    B = B*(N-k)//k 
  res = (res+ A*B)%m
  A = (A*mi)%m
print (res)

Submission status: Runtime Error

Solution code:
n, m, k = map(int, input().split())
ans = m*((m - 1)**(n - 1))
a = m*((m - 1)**(n - 1))
for i in range(1, k+1):

    a = a *(n - i) / (i * (m-1))
    ans += a
print(int(ans % 998244353))

Submission status: Runtime Error

Solution code:
n,m,k=map(int,input().split())
a=[0]*(k+1)
a[0]=1
for i in range(1,k+1):
    a[i]=(a[i-1]*(n-i))//(i)
e=pow(m-1,n-1)
ans=0
mod=998244353
for i in range(k+1):
    ans+=((m%mod)*(e%mod)*(a[i]%mod))%mod
    e//=(m-1)
    ans%=mod
print(ans)

Submission status: Runtime Error

Solution code:
N,M,K=map(int,input().split())
P=998244353

start=(M*pow(M-1,N-1,P))%P

fac=[0]*N
finv=[0]*N
inv=[0]*N
fac[0]=1
fac[1]=1
finv[0]=1
finv[1]=1
inv[1]=1
for i in range(2,N):
    fac[i]=(fac[i-1]*i)%P
    inv[i]=P-(inv[P%i]*(P//i))%P
    finv[i]=(finv[i-1]*inv[i])%P

def comb(n,k):
    return fac[n]*(finv[k]*finv[n-k]%P)%P



comp=0
last=(N-1)-K #K=0ならthru
if K>=1:
    for i in range(1,K+1):
        comp=(comp+comb(N-1,i)*pow(M-1,(N-1)-i,P))%P
comp=(comp*M)%P

print((start+comp)%P)

Submission status: Runtime Error

Solution code:
N, M, K = map(int, input().split())

dp = [[[0] * K + 2] for _ in range(N)]

x = 998244353
dp[0][0] = M
print(dp)
for j in range(N, 1):
    for i in range(K + 1):
        dp[j][i + 1] += dp[j - 1][i] % x
        dp[j][i] += dp[j - 1][i] * (M - 1) % x
ans = 0
for i in range(K + 1):
    ans += dp[N - 1][i] % x
print(ans)

Submission status: Runtime Error

Solution code:
DELIM = 998244353

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1)) % DELIM
    under = reduce(mul, range(1,r + 1))
    return over // under

def kaijo(n, x):
    double = (n**2) % DELIM
    if(x==1):
        return n
    if(x%2==0):
        return kaijo(double, x//2) % DELIM
    else:
        return (kaijo(double, x//2) * (n % DELIM)) % DELIM


def calc(N, M, x):
    m = M % DELIM
    m2 = (M-1) % DELIM
    nx = cmb(N-1, x) % DELIM
    if(x == 0):
        return (m * kaijo(m2, N-1)) % DELIM
    return (nx * m * kaijo(m2, N-1-x)) % DELIM

def main():
    N, M, K = map(int, input().split())
    ans = 0
    for x in range(0, K+1, 1):
        ans = (ans + calc(N, M, x)) % DELIM
    print(ans)


main()

Submission status: Runtime Error

Solution code:
import math

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

for i in range(k+1):
    temp = m*((m-1)**(n-k-1))%998244353
    comb = (math.factorial(n-i)//(math.factorial(n-(2*i))*math.factorial(i)))%998244353
    temp *= comb%998244353
    ans += temp

print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun May 10 20:54:37 2020

@author: Kanaru Sato
"""

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

dp = [[0 for i in range(k)] for j in range(n)]

dp[0][0] = m

for i in range(1,n-1):
    for j in range(min(i,k)+1):
        if j >= 1:
            dp[i][j] = (m-1)*dp[i-1][j] + dp[i-1][j-1]
        else:
            dp[i][j] = (m-1)*dp[i-1][j]
        dp[i][j] %= mod

ans = 0
for i in range(k+1):
    ans += dp[n-1][i]
print(ans%mod)

Submission status: Runtime Error

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
#from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 998244353
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

#コンビネーション
def cmb(n, r):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % mod

N = 3 * (10 ** 5)  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)

n, m, k = MAP()

pascal = [[1, 0]]
for i in range(n - k):
    pascal.append([1])
    for j in range(i):
        pascal[i + 1].append(pascal[i][j] + pascal[i][j + 1])
    pascal[i + 1].append(1)
    pascal[i + 1].append(0)
    #debug(i + 1, pascal[i + 1])

ans = m * pow(m - 1, n - 1, mod)
ans %= mod
for i in range(1, k + 1):
    tmp = sum(pascal[n - i][1:i + 1])
    #debug(i, tmp, m * pow(m - 1, n - i - 1, mod) * tmp)
    ans += m * pow(m - 1, n - i - 1, mod) * tmp
    ans %= mod
print(ans)
#debug(479519525)

Submission status: Runtime Error

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,m,k = na()
mod = 998244353
aall = pow(m,n,mod)

p = n-k+1


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


N = 10**3*3
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

if n//2 > k:
    print(aall-cmb(n+p,p,mod))
    exit()

print(aall)