output_description: Print the minimum possible value of "the sum of the digits of A" plus "the sum
  of the digits of B".
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
attempt: from fractions import gcd
  
  N, A, B, K = map(int, input().split())
  mod = 998244353
  
  Factorial = [1] * (N + 1)
  for i in range(1, N + 1):
      Factorial[i] = Factorial[i - 1] * (i) % mod
  
  
  def power(x, y):
      if y == 0:
          return 1
      elif y == 1:
          return x % mod
      elif y % 2 == 0:
          return power(x, y // 2) ** 2 % mod
      else:
          return (power(x, y // 2) ** 2) * x % mod
  
  
  inverseFactorial = [1] * (N + 1)
  inverseFactorial[N] = power(Factorial[N], mod - 2)
  for i in range(0, N)[::-1]:
      inverseFactorial[i] = (inverseFactorial[i + 1] * (i + 1)) % mod
  
  
  def f(i, j):
      if i > j:
          i, j = j, i
      res = 0
      if j <= N:
          for k in range(max(0, i + j - N), i + 1):
              res += (
                  Factorial[N]
                  * inverseFactorial[i - k]
                  * inverseFactorial[j - k]
                  * inverseFactorial[k]
                  * inverseFactorial[N - i - j + k]
              )
      return res % mod
  
  
  ans = 0
  g = gcd(A, B)
  if K % g == 0:
      A, B, K = A // g, B // g, K // g
  else:
      print(0)
      exit()
  for i in range(K // A + 1):
      if (K - A * i) % B == 0:
          x0 = i
          y0 = (K - A * i) // B
          break
  m = 0
  while y0 - A * m >= 0:
      ans += f(x0 + B * m, y0 - A * m)
      ans %= mod
      m += 1
  
  print(ans % mod - 1)
  
problem_description: Statement
  
  Takahashi has two positive integers A and B.
  
  It is known that A plus B equals N. Find the minimum possible value of "the
  sum of the digits of A" plus "the sum of the digits of B" (in base 10).
samples: [{"input": "15", "output": "6\n    \n\nWhen A=2 and B=13, the sums of their digits are 2 and 4, which minimizes the\nvalue in question.\n\n* * *"}, {"input": "100000", "output": "10"}]