//generated by GPT-5.4?, modified by hamamu
namespace Enumerate2D{
using ll=long long;

template<class MLL,class CMB>
MLL countKonHWallLineColumn(ll H,ll W,ll K,CMB &cmb){
    MLL ret=0;
    for (ll h=0; h<=H; ++h) for (ll w=0; w<=W; ++w){
        ll sign = 1 - (((H+W-h-w)&1) << 1); //(-1)^(H+W-h-w)
        ret += sign * cmb(h*w,K) * cmb(H,h) * cmb(W,w);
    }
    return ret;
}
}//namespace
using Enumerate2D::countKonHWallLineColumn;
/*
-- 要件 --
- cmb(ll n,ll r)がbinom{n}{r}をMLL型で返すこと
- cmb(ll n,ll r)がn≦H*Wで動作すること

- ---- H*Wマスの全行全列に黒マスがあるようKマス塗る方法の個数 ---- O(HW)
combination<mll> cmb(H*W+10);
mll ct=countKonHWallLineColumn<mll>(H,W,K,cmb);
*/