// #pragma GCC target("avx2") // #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; using pii = pair; using pll = pair; #define TEST cerr << "TEST" << endl #define AMARI 998244353 // #define AMARI 1000000007 #define TIME_LIMIT 1980000 #define el '\n' #define El '\n' // 二項係数の計算(余り付き) // nCkについて、n,k<10^7の時前処理O(N)、計算O(1)で行う class ococo_combination { public: long long n, p; vector kaizyou, gyakugen, gyakugen_kaizyou; // 二項係数に出てくる最大値をaに変更する // O(1) ここで変更したaが他の関数の計算時間に影響を与える。 void update_max(int a) { n = a; kaizyou.resize(n); gyakugen.resize(n); gyakugen_kaizyou.resize(n); } // 素数で割った余りを出力する時その余りをpに変更する // a = 0にすると余りは出さずに計算する // O(1) void update_mod(int a) { p = a; } // 前処理を行う update_maxとupdate_modを先にやった方が良い // O(N) void maesyori(void) { kaizyou[0] = 1; gyakugen[0] = 1; gyakugen_kaizyou[0] = 1; kaizyou[1] = 1; gyakugen[1] = 1; gyakugen_kaizyou[1] = 1; for(int i = 2; i < n; i++) { kaizyou[i] = kaizyou[i - 1] * i % p; gyakugen[i] = p - gyakugen[p % i] * (p / i) % p; gyakugen_kaizyou[i] = gyakugen_kaizyou[i - 1] * gyakugen[i] % p; } } // 二項係数nCkの計算を行う // O(1) long long nCk(int n, int k) { if(n < k || n < 0 || k < 0) return 0; else { long long ans = kaizyou[n]; long long kari = gyakugen_kaizyou[n - k]; kari %= p; kari *= gyakugen_kaizyou[k]; kari %= p; ans *= kari; ans %= p; return ans; } } }; #define MULTI_TEST_CASE false void solve(void) { ococo_combination oc; ll h,w,k; cin >> h >> w >> k; oc.update_max(max(h,w) + 1); oc.update_mod(AMARI); oc.maesyori(); ll ans = 0; //y=一定にi本引くことを考える for(ll i = 0; i <= h; i++){ ll black = w * (h - i); if(black < k)break; //x=一定に1本追加で引くことで黒いマスは(h-i)個減る if((black - k) % (h - i) != 0)continue; ll j = (black - k) / (h - i); //cerr << i << ' ' << j << el; if(j < 0)continue; ans += oc.nCk(h,i) * oc.nCk(w,j); ans %= AMARI; } cout << ans << el; return; } void calc(void) { return; } signed main(void) { cin.tie(nullptr); ios::sync_with_stdio(false); calc(); int t = 1; if(MULTI_TEST_CASE) cin >> t; while(t--) { solve(); } return 0; }