今天是hidadz小朋友的生日，她邀请了许多朋友来参加她的生日party。 hidadz带着朋友们来到花园中，打算
坐成一排玩游戏。为了游戏不至于无聊，就座的方案应满足如下条件：对于任意连续的一段，男孩与女孩的数目之
差不超过k。很快，小朋友便找到了一种方案坐了下来开始游戏。hidadz的好朋友Susie发现，这样的就座方案其实
是很多的，所以大家很快就找到了一种，那么到底有多少种呢？热爱数学的hidadz和她的朋友们开始思考这个问题
…… 假设参加party的人中共有n个男孩与m个女孩，你是否能解答Susie和hidadz的疑问呢？由于这个数目可能很
多，他们只想知道这个数目除以12345678的余数。

　　仅包含一行共3个整数，分别为男孩数目n,女孩数目m,常数k。

　　应包含一行，为题中要求的答案。

n , m ≤ 150，k ≤ 20。

#include <algorithm>
#include <cstdio>
using std::min;
using std::max;
const int N = 155;
const int K = 25;
const int mod = 12345678;
int f[N][N][K][K];
int main() {
  int n, m, k;
  scanf("%d%d%d", &n, &m, &k);
  for (int i = 0; i <= k; ++i)
    for (int j = 0; j <= k; ++j)
      f[0][0][i][j] = 1;
  for (int ij = 1; ij <= n + m; ++ij)
    for (int i = max(ij - m, 0); i <= min(ij, n); ++i) {
      int j = ij - i;
      for (int a = 0; a <= k; ++a)
        for (int b = 0; b <= k; ++b) {
          f[i][j][a][b] = 0;
          if (i && a) f[i][j][a][b] += f[i - 1][j][a - 1][min(b + 1, k)];
          if (j && b) f[i][j][a][b] += f[i][j - 1][min(a + 1, k)][b - 1];
          f[i][j][a][b] %= mod;
        }
    }
  printf("%d\n", f[n][m][k][k]);
  return 0;
}