#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("Ofast") #include #include using namespace std; #if __has_include() #include using namespace atcoder; #endif using ll = long long; using ld = long double; using ull = long long; #define endl "\n" #define REP3(i, m, n) for (int i = (m); (i) < int(n); ++ (i)) #define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++) #define ALL(x) begin(x), end(x) #define all(s) (s).begin(),(s).end() //#define rep2(i, m, n) for (int i = (m); i < (n); ++i) //#define rep(i, n) rep2(i, 0, n) #define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i) #define drep(i, n) drep2(i, n, 0) #define rever(vec) reverse(vec.begin(), vec.end()) #define sor(vec) sort(vec.begin(), vec.end()) #define fi first #define se second #define pb push_back #define P pair #define REP(i, n) for (int i = 0; i < (n); ++i) #define in scanner.read_int() //const ll mod = 998244353; const ll mod = 1000000007; const ll inf = 4500000000000000000ll; static const long double pi = 3.141592653589793; templatevoid vcin(vector &n){for(int i=0;i>n[i];} templatevoid vcin(vector &n,vector &m){for(int i=0;i>n[i]>>m[i];} templatevoid vcout(vector &n){for(int i=0;ivoid vcin(vector> &n){for(int i=0;i>n[i][j];}}} templatevoid vcout(vector> &n){for(int i=0;iauto min(const T& a){ return *min_element(all(a)); } templateauto max(const T& a){ return *max_element(all(a)); } templatevoid print(pair a){cout<bool chmax(T &a, const T &b) { if (abool chmin(T &a, const T &b) { if (b void ifmin(T t,T u){if(t>u){cout<<-1< void ifmax(T t,T u){if(t>u){cout<<-1<auto make_vector(T x,int arg,Args ...args){if constexpr(sizeof...(args)==0)return vector(arg,x);else return vector(arg,make_vector(x,args...));} ll modPow(ll a, ll n, ll mod) { ll ret = 1; ll p = a % mod; while (n) { if (n & 1) ret = ret * p % mod; p = p * p % mod; n >>= 1; } return ret; } vector divisor(ll x){ vector ans; for(ll i = 1; i * i <= x; i++){ if(x % i == 0) {ans.push_back(i); if(i*i!=x){ ans.push_back(x / ans[i]);}}}sor(ans); return ans; } template struct Sum{ vector data; Sum(const vector& v):data(v.size()+1){ for(ll i=0;i struct Sum2{ vector> data; Sum2(const vector> &v):data(v.size()+1,vector(v[0].size()+1)){ for(int i=0;i buffer; ssize_t n_written; ssize_t n_read; public: Scanner(): buffer(1024*1024) { do_read(); } int64_t read_int() { int64_t ret = 0, sgn = 1; int ch = current_char(); while (isspace(ch)) { ch = next_char(); } if (ch == '-') { sgn = -1; ch = next_char(); } for (; isdigit(ch); ch = next_char()) ret = (ret * 10) + (ch - '0'); return sgn * ret; } private: void do_read() { ssize_t r = read(0, &buffer[0], buffer.size()); if (r < 0) { throw runtime_error(strerror(errno)); } n_written = r; n_read = 0; } inline int next_char() { ++n_read; if (n_read == n_written) { do_read(); } return current_char(); } inline int current_char() { return (n_read == n_written) ? EOF : buffer[n_read]; } }; //Scanner scanner; //void vin(vector &n){for(int i=0;i vector NTT(vector a,vector b){ ll nmod=T::mod(); int n=a.size(); int m=b.size(); vector x1(n); vector y1(m); for(int i=0;i(x1,y1); auto z2=convolution<469762049>(x1,y1); auto z3=convolution<1224736769>(x1,y1); vector res(n+m-1); ll m1=167772161; ll m2=469762049; ll m3=1224736769; ll m1m2=104391568; ll m1m2m3=721017874; ll mm12=m1*m2%nmod; for(int i=0;i struct FormalPowerSeries:vector{ using vector::vector; using vector::operator=; using F=FormalPowerSeries; F operator-() const{ F res(*this); for(auto &e:res) e=-e; return res; } F &operator*=(const T &g){ for(auto &e:*this) e*=g; return *this; } F &operator/=(const T &g){ assert(g!=T(0)); *this*=g.inv(); return *this; } F &operator+=(const F &g){ int n=(*this).size(),m=g.size(); for(int i=0;i>=(const int d) { int n=(*this).size(); (*this).erase((*this).begin(),(*this).begin()+min(n, d)); (*this).resize(n); return *this; } F inv(int d=-1) const{ int n=(*this).size(); assert(n!=0&&(*this)[0]!=0); if(d==-1) d=n; assert(d>0); F res{(*this)[0].inv()}; while(res.size() s=NTT(f,r); s.resize(2*m); for(int i=0;i<2*m;i++){ s[i]=-s[i]; } s[0]+=2; vector g=NTT(s,r); g.resize(2*m); res=g; } res.resize(n); return res; } F &operator/=(const F &g){ int n=(*this).size(); *this=NTT(*this,g.inv()); (*this).resize(n); return (*this); } F &operator*=(const F &g){ int n=(*this).size(); *this=NTT(*this,g); for(int i=n;i<(*this).size();i++){ (*this)[i%n]+=(*this)[i]; } (*this).resize(n); return (*this); } void onemul(const int d,const T c){ int n=(*this).size(); for(int i=n-d-1;i>=0;i--){ (*this)[i+d]+=(*this)[i]*c; } } void onediv(const int d,const T c){ int n=(*this).size(); for(int i=0;i> g) { int n = (*this).size(); auto [d, c] = g.front(); if (d == 0) g.erase(g.begin()); else c = 0; for(int i=n-1;i>=0;i--){ (*this)[i] *= c; for (auto &[j, b] : g) { if (j > i) break; (*this)[i] += (*this)[i-j] * b; } } } void spacediv(vector> g) { int n = (*this).size(); auto [d, c] = g.front(); assert(d == 0 && c != T(0)); T ic = c.inv(); g.erase(g.begin()); for(int i=0;i i) break; (*this)[i] -= (*this)[i-j] * b; } (*this)[i] *= ic; } } T eval(const T &a) const { T x(1),res(0); for(auto e:*this) res+=e*x,x*=a; return res; } F differential() const { int n=(*this).size(); F res(n); for(int i=0;i0); F res{1}; while(res.size()0){ s[0]=T(1); } for(int i=0;i(n-1)/a||l==n){ F s(n); for(int i=0;i>i).sqrt(n-i/2)<<(i/2); if(int(ret.size())>(const int d) const { return F(*this)>>=d;} }; using mint=modint1000000007; using fps = FormalPowerSeries; using sfps = vector>; fps fpspow(fps a,ll n){ ll m=a.size(); fps ret(m); ret[0]=1; while(n){ if(n&1){ ret*=a; } a*=a; n/=2; } return ret; } int main() { cincout(); ll n,k,l; cin>>n>>k>>l; fps g(n); for(int i=1;i<=l;i++) g[i%n]++; g=fpspow(g,k); for(int i=0;i