#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using ll = long long; using namespace std; template bool chmin(A &a, const B b) { if (a <= b) return false; a = b; return true; } template bool chmax(A &a, const B b) { if (a >= b) return false; a = b; return true; } #ifndef LOCAL #define debug(...) ; #else #define debug(...) cerr << __LINE__ << " : " << #__VA_ARGS__ << " = " << _tostr(__VA_ARGS__) << endl; template ostream &operator<<(ostream &out, const vector &v); template ostream &operator<<(ostream &out, const pair &p) { out << "{" << p.first << ", " << p.second << "}"; return out; } template ostream &operator<<(ostream &out, const vector &v) { out << '{'; for (const T &item : v) out << item << ", "; out << "\b\b}"; return out; } void _tostr_rec(ostringstream &oss) { oss << "\b\b \b"; } template void _tostr_rec(ostringstream &oss, Head &&head, Tail &&...tail) { oss << head << ", "; _tostr_rec(oss, forward(tail)...); } template string _tostr(T &&...args) { ostringstream oss; int size = sizeof...(args); if (size > 1) oss << "{"; _tostr_rec(oss, forward(args)...); if (size > 1) oss << "}"; return oss.str(); } #endif constexpr int mod = 1'000'000'007; //1e9+7(prime number) constexpr int INF = 1'000'000'000; //1e9 constexpr ll LLINF = 2'000'000'000'000'000'000LL; //2e18 constexpr int SIZE = 200010; template struct ModInt { using ll = long long; ll val; ModInt(ll x = 0): val(x >= 0 ? x % M : (x % M + M) % M) {} explicit operator bool() const { return val != 0; } ModInt operator+() const { return *this; } ModInt operator-() const { return ModInt(-val); } ModInt operator+(const ModInt &rhs) const { return ModInt(*this) += rhs; } ModInt operator-(const ModInt &rhs) const { return ModInt(*this) -= rhs; } ModInt operator*(const ModInt &rhs) const { return ModInt(*this) *= rhs; } ModInt operator/(const ModInt &rhs) const { return ModInt(*this) /= rhs; } bool operator==(const ModInt &rhs) const { return val == rhs.val; } bool operator!=(const ModInt &rhs) const { return val != rhs.val; } bool operator<(const ModInt &rhs) const { return val < rhs.val; } bool operator>(const ModInt &rhs) const { return val > rhs.val; } bool operator<=(const ModInt &rhs) const { return val <= rhs.val; } bool operator>=(const ModInt &rhs) const { return val >= rhs.val; } ModInt operator++() { return *this += 1; } ModInt operator--() { return *this -= 1; } ModInt operator++(int) { return ++*this, *this - 1; } ModInt operator--(int) { return --*this, *this + 1; } ModInt &operator+=(const ModInt &rhs) { val += rhs.val; if (val >= M) val -= M; return *this; } ModInt &operator-=(const ModInt &rhs) { val -= rhs.val; if (val < 0) val += M; return *this; } ModInt &operator*=(const ModInt &rhs) { val = val * rhs.val % M; return *this; } ModInt &operator/=(ModInt rhs) { for (int exp = M - 2; exp; exp /= 2) { if (exp % 2) *this *= rhs; rhs *= rhs; } return *this; } friend int abs(const ModInt &arg) { return arg.val; } friend ostream &operator<<(ostream &os, const ModInt &rhs) { return os << rhs.val; } friend istream &operator>>(istream &is, ModInt &rhs) { ll x; is >> x; rhs = ModInt(x); return is; } }; template class Matrix { std::vector> val; public: int H, W; Matrix(int H, int W, T init = 0): val(H, std::vector(W, init)), H(H), W(W) {}; template operator Matrix() const { Matrix res(H, W); for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) res[i][j] = val[i][j]; return res; } Matrix(std::initializer_list> init) : val(init.size(), std::vector(init.begin()->size())), H(init.size()), W(init.begin()->size()) { auto list_it = init.begin(); for (int i = 0; i < H; i++) { auto it = list_it->begin(); for (int j = 0; j < W; j++) if (it != list_it->end()) val[i][j] = *it++; list_it++; } } std::vector &operator[](size_t idx) { return val[idx]; } const std::vector &operator[](size_t idx) const { return val[idx]; } const Matrix operator+() const { return *this; } const Matrix operator-() const { Matrix res(H, W); for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) res[i][j] = -val[i][j]; return res; } const Matrix operator+(const Matrix &m) const { assert(H == m.H && W == m.W); Matrix res(H, W); for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) res.val[i][j] = val[i][j] + m[i][j]; return res; } const Matrix operator-(const Matrix &m) const { assert(H == m.H && W == m.W); Matrix res(H, W); for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) res.val[i][j] = val[i][j] - m[i][j]; return res; } const Matrix operator*(const Matrix &m) const { assert(W == m.H); Matrix res(H, m.W); for (int i = 0; i < H; i++) for (int j = 0; j < m.W; j++) for (int k = 0; k < W; k++) res[i][j] += val[i][k] * m[k][j]; return res; } Matrix &operator+=(const Matrix &m) { assert(H == m.H && W == m.W); for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) val[i][j] += m[i][j]; return *this; } Matrix &operator-=(const Matrix &m) { assert(H == m.H && W == m.W); for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) val[i][j] -= m[i][j]; return *this; } Matrix &operator*=(const Matrix &m) { assert(H == m.H && W == m.W); this->val = (*this * m).val; return *this; } const std::vector> &toVector() const { return val; } Matrix pow(ll N) { assert(H == W); Matrix res(H, W), k = *this; for (int i = 0; i < H; i++) res[i][i] = 1; for (; N; N /= 2) { if (N & 1) res = res * k; k = k * k; } return res; } Matrix inv() const { assert(H == W); Matrix tmp = *this, res(H, W); for (int i = 0; i < H; i++) res[i][i] = 1; for (int i = 0; i < H; i++) { int pivot = i; for (int j = i; j < H; j++) if (abs(tmp[j][i]) > abs(tmp[pivot][i])) pivot = j; assert(tmp[pivot][i] != 0); //逆行列は存在しない if (pivot != i) { swap(tmp[i], tmp[pivot]); swap(res[i], res[pivot]); } U p = 1 / tmp[i][i]; for (int j = 0; j < H; j++) { tmp[i][j] *= p; res[i][j] *= p; } for (int j = 0; j < H; j++) { if (i != j) { U p = tmp[j][i]; for (int k = 0; k < H; k++) { tmp[j][k] -= tmp[i][k] * p; res[j][k] -= res[i][k] * p; } } } } return res; } U det() const { assert(H == W); Matrix v = *this; U res = 1; for (int i = 0; i < H; i++) { for (int j = i; j < H; j++) { if (v[j][i]) { swap(v[i], v[j]); if (i != j) res *= -1; break; } } U a = (U)1 / v[i][i]; for (int j = i + 1; j < H; j++) { U b = v[j][i] * a; for (int k = 0; k < H; k++) v[j][k] -= v[i][k] * b; } res *= v[i][i]; } return res; } friend ostream &operator<<(ostream &os, const Matrix &rhs) { for (int i = 0; i < rhs.H; i++) { os << (i == 0 ? "[[" : " ["); for (int j = 0; j < rhs.W; j++) { os << rhs.val[i][j] << (j + 1 == rhs.W ? "]" : " "); } os << (i + 1 == rhs.H ? "]" : "\n"); } return os; } }; int main() { int N, L, K; cin >> N >> K >> L; Matrix, ModInt<>> mat(N, N); for (int i = 0; i < N; i++) { for (int j = 1; j <= L; j++) { mat[i][(i + j) % N] = 1; } } auto ans = mat.pow(K); debug(mat, ans); for (int i = 0; i < N; i++) { cout << ans[0][i] << endl; } return 0; }