#pragma GCC optimize(3, "unroll-loops", "no-stack-protector") #define atsum(l, r) accumulate(l, r, 0) #include #include #include using namespace std; using ll = long long; using ull = unsigned long long; constexpr int inf = 0x3f3f3f3f; constexpr ll INF = 0x3f3f3f3f3f3f3f3f; template inline void chkmin(T &x, T y) { x = min(x, y); } template inline void chkmax(T &x, T y) { x = max(x, y); } namespace FastIO { // ------------------------------ #define IN_HAS_NEG #define OUT_HAS_NEG #define CHK_EOF #define DISABLE_MMAP // ------------------------------ #if __cplusplus < 201400 #error Please use C++14 or higher. #endif #if __cplusplus > 201700 #define INLINE_V inline #else #define INLINE_V #endif #if ( defined(LOCAL) || defined (_WIN32) ) && !defined(DISABLE_MMAP) #define DISABLE_MMAP #endif #ifndef DISABLE_MMAP #include #endif #ifdef LOCAL inline char gc() { return getchar(); } inline void pc(char c) { putchar(c); } #else #ifdef DISABLE_MMAP INLINE_V constexpr int _READ_SIZE = 1 << 18; INLINE_V static char _read_buffer[_READ_SIZE], *_read_ptr = nullptr, *_read_ptr_end = nullptr; inline char gc() { if ( __builtin_expect(_read_ptr == _read_ptr_end, false) ) { _read_ptr = _read_buffer; _read_ptr_end = _read_buffer + fread(_read_buffer, 1, _READ_SIZE, stdin); #ifdef CHK_EOF if ( __builtin_expect(_read_ptr == _read_ptr_end, false) ) return EOF; #endif } return *_read_ptr++; } #else INLINE_V static const char *_read_ptr = (const char *)mmap(nullptr, INT_MAX, 1, 2, 0, 0); inline char gc() { return *_read_ptr++; } #endif INLINE_V constexpr int _WRITE_SIZE = 1 << 18; INLINE_V static char _write_buffer[_WRITE_SIZE], *_write_ptr = _write_buffer; inline void pc(char c) { *_write_ptr++ = c; if ( __builtin_expect(_write_buffer + _WRITE_SIZE == _write_ptr, false) ) { fwrite(_write_buffer, 1, _write_ptr - _write_buffer, stdout); _write_ptr = _write_buffer; } } INLINE_V struct _auto_flush { ~_auto_flush() { fwrite(_write_buffer, 1, _write_ptr - _write_buffer, stdout); } } _auto_flush; #endif #ifdef CHK_EOF inline bool _isdigit(char c) { return ( c & 16 ) && c != EOF; } inline bool _isgraph(char c) { return c > 32 && c != EOF; } #else inline bool _isdigit(char c) { return c & 16; } inline bool _isgraph(char c) { return c > 32; } #endif template < class T > INLINE_V constexpr bool _is_integer = numeric_limits < T >::is_integer; template < class T > INLINE_V constexpr bool _is_signed = numeric_limits < T >::is_signed; template < class T > INLINE_V constexpr bool _is_unsigned = _is_integer < T > && !_is_signed < T >; template <> INLINE_V constexpr bool _is_integer < __int128 > = true; template <> INLINE_V constexpr bool _is_integer < __uint128_t > = true; template <> INLINE_V constexpr bool _is_signed < __int128 > = true; template <> INLINE_V constexpr bool _is_unsigned < __uint128_t > = true; #undef INLINE_V inline void read(char &c) { do c = gc(); while ( !_isgraph(c) ); } inline void read_cstr(char *s) { char c = gc(); while ( !_isgraph(c) ) c = gc(); while ( _isgraph(c) ) *s++ = c, c = gc(); *s = 0; } inline void read(string &s) { char c = gc(); s.clear(); while ( !_isgraph(c) ) c = gc(); while ( _isgraph(c) ) s.push_back(c), c = gc(); } #ifdef IN_HAS_NEG template < class T, enable_if_t < _is_signed < T >, int > = 0 > inline void read(T &x) { char c = gc(); bool f = true; x = 0; while ( !_isdigit(c) ) { if ( c == 45 ) f = false; c = gc(); } if ( f ) while ( _isdigit(c) ) x = x * 10 + ( c & 15 ), c = gc(); else while ( _isdigit(c) ) x = x * 10 - ( c & 15 ), c = gc(); } template < class T, enable_if_t < _is_unsigned < T >, int > = 0 > #else template < class T, enable_if_t < _is_integer < T >, int > = 0 > #endif inline void read(T &x) { char c = gc(); while ( !_isdigit(c) ) c = gc(); x = 0; while ( _isdigit(c) ) x = x * 10 + ( c & 15 ), c = gc(); } inline void write(char c) { pc(c); } inline void write_cstr(const char *s) { while ( *s ) pc(*s++); } inline void write(const string &s) { for ( char c : s ) pc(c); } #ifdef OUT_HAS_NEG template < class T, enable_if_t < _is_signed < T >, int > = 0 > inline void write(T x) { char buffer[numeric_limits < T >::digits10 + 1]; int digits = 0; if ( x >= 0 ) do buffer[digits++] = ( x % 10 ) | 48, x /= 10; while ( x ); else { pc(45); do buffer[digits++] = -( x % 10 ) | 48, x /= 10; while ( x ); } while ( digits ) pc(buffer[--digits]); } template < class T, enable_if_t < _is_unsigned < T >, int > = 0 > #else template < class T, enable_if_t < _is_integer < T >, int > = 0 > #endif inline void write(T x) { char buffer[numeric_limits < T >::digits10 + 1]; int digits = 0; do buffer[digits++] = ( x % 10 ) | 48, x /= 10; while ( x ); while ( digits ) pc(buffer[--digits]); } template < int N > struct _tuple_io_helper { template < class ...T > static inline void _read(tuple < T... > &x) { _tuple_io_helper < N - 1 >::_read(x), read(get < N - 1 > (x)); } template < class ...T > static inline void _write(const tuple < T... > &x) { _tuple_io_helper < N - 1 >::_write(x), pc(32), write(get < N - 1 > (x)); } }; template <> struct _tuple_io_helper < 1 > { template < class ...T > static inline void _read(tuple < T... > &x) { read(get < 0 > (x)); } template < class ...T > static inline void _write(const tuple < T... > &x) { write(get < 0 > (x)); } }; template < class ...T > inline void read(tuple < T... > &x) { _tuple_io_helper < sizeof...(T) >::_read(x); } template < class ...T > inline void write(const tuple < T... > &x) { _tuple_io_helper < sizeof...(T) >::_write(x); } template < class T1, class T2 > inline void read(pair < T1, T2 > &x) { read(x.first), read(x.second); } template < class T1, class T2 > inline void write(const pair < T1, T2 > &x) { write(x.first), pc(32), write(x.second); } template < class T1, class ...T2 > inline void read(T1 &x, T2 &...y) { read(x), read(y...); } template < class ...T > inline void read_cstr(char *x, T *...y) { read_cstr(x), read_cstr(y...); } template < class T1, class ...T2 > inline void write(const T1 &x, const T2 &...y) { write(x), write(y...); } template < class ...T > inline void write_cstr(const char *x, const T *...y) { write_cstr(x), write_cstr(y...); } template < class T > inline void print(const T &x) { write(x); } inline void print_cstr(const char *x) { write_cstr(x); } template < class T1, class ...T2 > inline void print(const T1 &x, const T2 &...y) { print(x), pc(32), print(y...); } template < class ...T > inline void print_cstr(const char *x, const T *...y) { print_cstr(x), pc(32), print_cstr(y...); } inline void println() { pc(10); } inline void println_cstr() { pc(10); } template < class ...T > inline void println(const T &...x) { print(x...), pc(10); } template < class ...T > inline void println_cstr(const T *...x) { print_cstr(x...), pc(10); } } using namespace FastIO; template inline void clear(T &x) { T y; swap(x, y); } template class Modint { private: static constexpr uint32_t get_r() { uint32_t ret = mod; for (int i = 0; i < 4; i++) ret *= 2 - mod * ret; return ret; } static constexpr uint32_t r = get_r(); static constexpr uint32_t n2 = -uint64_t(mod) % mod; static_assert(r * mod == 1 && mod < (1 << 30) && mod & 1); uint32_t data; public: constexpr Modint() : data(0) {} template constexpr Modint(const int_t x) : data(reduce( uint64_t((sizeof(int_t) < sizeof(uint32_t) ? x : x % int_t(mod)) + mod) * n2)){}; static constexpr uint32_t reduce(const uint64_t x) { return (x + uint64_t(uint32_t(x) * (-r)) * mod) >> 32; } constexpr Modint &operator+=(const Modint &r) { if (int32_t(data += r.data - 2 * mod) < 0) { data += 2 * mod; } return *this; } constexpr Modint &operator-=(const Modint &r) { if (int32_t(data -= r.data) < 0) { data += 2 * mod; } return *this; } constexpr Modint &operator*=(const Modint &r) { return data = reduce((uint64_t)data * r.data), *this; } constexpr Modint &operator/=(const Modint &r) { return *this *= r.inv(); } constexpr friend Modint operator+(Modint l, const Modint &r) { return l += r; } constexpr friend Modint operator-(Modint l, const Modint &r) { return l -= r; } constexpr friend Modint operator*(Modint l, const Modint &r) { return l *= r; } constexpr friend Modint operator/(Modint l, const Modint &r) { return l /= r; } constexpr friend bool operator==(Modint l, const Modint &r) { return l.value() == r.value(); } constexpr Modint operator-() const { return Modint() - Modint(*this); } template constexpr Modint pow(int_t r) const { Modint res(1), w(*this); for (; r; r >>= 1, w *= w) if (r & 1) res *= w; return res; } constexpr Modint inv() const { return pow(mod - 2); } constexpr uint32_t value() const { uint32_t res = reduce(data); return res >= mod ? res - mod : res; } }; using modint = Modint<>; namespace cmaths { const int FACMAX = 1e7 + 10; modint fac[FACMAX], ifac[FACMAX], inv[FACMAX]; inline void initfac(int n) { fac[0] = 1; for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i; } inline void initifac(int n) { ifac[n] = fac[n].inv(); for (int i = n - 1; ~i; i--) ifac[i] = ifac[i + 1] * (i + 1); } inline modint C(int a, int b) { return a < b ? 0 : fac[a] * ifac[b] * ifac[a - b]; } inline modint A(int a, int b) { return a < b ? 0 : fac[a] * ifac[a - b]; } inline void getInv(int k) { inv[1] = 1; for (int i = 2; i <= k; ++i) inv[i] = ifac[i] * fac[i - 1]; } inline void initall(int n = FACMAX - 2) { initfac(n), initifac(n), getInv(n); } }; using namespace cmaths; const int N = 1e6 + 10; int k; inline modint calcpath(int x, int y, int m) { return C(m, x) * C(m, y); } inline void changea(int &x, int &y) { swap(x, y), x -= k + 1, y += k + 1; } inline void changeb(int &x, int &y) { swap(x, y), x += k + 1, y -= k + 1; } int n, m; // x = y + k; // y = x + k; int main() { initall(); read(n, m, k), --n, --m, m += n, k >>= 1; modint ans = calcpath(n, n, m); int an = n, bn = n; bool type = 1; while (1) { (type ? changeb : changea)(an, bn); if (an < 0 || bn < 0) break; if (type & 1) ans -= calcpath(an, bn, m) * 2; else ans += calcpath(an, bn, m) * 2; type ^= 1; } println(ans.value()); return 0; }