#include #include using namespace std; #pragma region datastructure Matrix #include #include #include template struct Matrix { private: std::vector> A; static Matrix I(size_t n) { Matrix mat(n); for(int i = 0; i < n; i++) mat[i][i] = 1; return mat; } public: Matrix() = default; Matrix(std::vector> &vvec) { A = vvec; } Matrix(size_t n, size_t m) : A(n, std::vector(m, 0)) {} Matrix(size_t n, size_t m, T init) : A(n, std::vector(m, init)) {} Matrix(size_t n, std::vector &vec) : A(n, vec) {} Matrix(size_t n) : A(n, std::vector(n, 0)) {} size_t height() const { return A.size(); } size_t width() const { return A[0].size(); } inline const std::vector &operator[](int k) const { return A[k]; } inline std::vector &operator[](int k) { return A[k]; } Matrix &operator+=(const Matrix &B) { size_t n = height(), m = width(); assert(n == B.height() and m == B.width()); for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) (*this)[i][j] += B[i][j]; return *this; } Matrix &operator-=(const Matrix &B) { size_t n = height(), m = width(); assert(n == B.height() and m == B.width()); for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) (*this)[i][j] -= B[i][j]; return *this; } Matrix &operator*=(const Matrix &B) { size_t n = height(), m = B.width(), p = width(); assert(p == B.height()); std::vector> C(n, std::vector(m, 0)); for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) for(int k = 0; k < p; k++) C[i][j] += (*this)[i][k] * B[k][j]; A.swap(C); return *this; } Matrix &operator^=(long long k) { Matrix B = Matrix::I(height()); while(k > 0) { if(k & 1) B *= (*this); *this *= *this; k >>= 1ll; } A.swap(B.A); return *this; } bool operator==(const Matrix &B) { size_t n = height(), m = width(); if(n != B.height() or m != B.width()) return false; for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) if((*this)[i][j] != B[i][j]) return false; return true; } Matrix operator+(const Matrix &B) const { return (Matrix(*this) += B); } Matrix operator-(const Matrix &B) const { return (Matrix(*this) -= B); } Matrix operator*(const Matrix &B) const { return (Matrix(*this) *= B); } Matrix operator^(const long long &k) const { return (Matrix(*this) ^= k); } Matrix &operator+=(const T &t) { int n = height(), m = width(); for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) (*this)[i][j] += t; return *this; } Matrix &operator-=(const T &t) { int n = height(), m = width(); for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) (*this)[i][j] -= t; return *this; } Matrix &operator*=(const T &t) { int n = height(), m = width(); for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) (*this)[i][j] *= t; return *this; } Matrix &operator/=(const T &t) { int n = height(), m = width(); for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) (*this)[i][j] /= t; return *this; } Matrix operator+(const T &t) const { return (Matrix(*this) += t); } Matrix operator-(const T &t) const { return (Matrix(*this) -= t); } Matrix operator*(const T &t) const { return (Matrix(*this) *= t); } Matrix operator/(const T &t) const { return (Matrix(*this) /= t); } friend std::ostream &operator<<(std::ostream &os, Matrix &p) { size_t n = p.height(), m = p.width(); for(int i = 0; i < n; i++) { os << '['; for(int j = 0; j < m; j++) os << p[i][j] << (j == m - 1 ? "]\n" : ","); } return (os); } T determinant() { Matrix B(*this); size_t n = height(), m = width(); assert(n == m); T ret = 1; for(int i = 0; i < n; i++) { int idx = -1; for(int j = i; j < n; j++) if(B[j][i] != 0) idx = j; if(idx == -1) return 0; if(i != idx) { ret *= -1; swap(B[i], B[idx]); } ret *= B[i][i]; T vv = B[i][i]; for(int j = 0; j < n; j++) B[i][j] /= vv; for(int j = i + 1; j < n; j++) { T a = B[j][i]; for(int k = 0; k < n; k++) { B[j][k] -= B[i][k] * a; } } } return ret; } }; #pragma endregion #include "testlib.h" using mint = atcoder::modint1000000007; int n, k, l; int main() { registerValidation(); n = inf.readInt(1,100); inf.readSpace(); k = inf.readInt(1,100000); inf.readSpace(); l = inf.readInt(1,n); inf.readEoln(); inf.readEof(); Matrix mat(1, n), mul(n, n); mat[0][0] = 1; for(int i = 0; i < n; i++) for(int j = 1; j <= l; j++) mul[i][(i + j) % n] = 1; mat *= mul ^ k; for(int i = 0; i < n; i++) cout << mat[0][i].val() << '\n'; return 0; }