output_description: Print the answer.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N M K
attempt: from itertools import product
  import math
  
  N, M, K = map(int, input().split())
  total_case = product(range(M), repeat=N)
  
  # すべての色の塗り方の数
  count = math.pow(M, N)
  
  # すべての色の塗り方をAとしてリスト化
  A = []
  for i in total_case:
      A.append(i)
  
  # 各塗り方に対して隣り合う色が存在するか判定する
  for j in A:
      # 色が被ってよい組み合わせ数
      limit = K
      out_flag = 0
      for p in range(N - 1):
          if j[p] == j[p + 1]:
              limit = limit - 1
              if limit < 0:
                  out_flag = -1
                  break
      if out_flag == -1:
          count = count - 1
  
  # 答えの算出および表示
  ans = int(count % 998244353)
  print(ans)
  
problem_description: 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.
samples: [{"input": "3 2 1", "output": "6\n    \n\nThe following ways to paint the blocks satisfy the conditions: `112`, `121`,\n`122`, `211`, `212`, and `221`. Here, digits represent the colors of the\nblocks.\n\n* * *"}, {"input": "100 100 0", "output": "73074801\n    \n\n* * *"}, {"input": "60522 114575 7559", "output": "479519525"}]