/* Beautiful Codes are MUCH better than 'Shorter' ones ! user : triveni date : 15/02/2018 time : 16:37:46 */ #include using namespace std; #define pii std::pair #define vi std::vector #define sz(v) (int)(v.size()) #define mp(a,b) make_pair(a,b) #define pb(a) push_back(a) #define each(it,s) for(auto it = s.begin(); it != s.end(); ++it) #define rep(i, n) for(int i = 0; i < (n); ++i) #define fill(a,v) memset(a, v, sizeof (a)) #define all(v) v.begin(), v.end() #define scan(n) scanf("%d", &n) #define scan2(n, m) scanf("%d%d", &n, &m) #define pin(n) printf("%d\n",n) #define pis(n) printf("%d ",n) #define pll(n) printf("%lld\n", n) #define X first #define Y second typedef long long ll; ll mod = 1000000007; inline int pow_(ll a, int n, int p=mod){ int r=1;while(n){if(n&1)r=r*a%p;n>>=1;a=a*a%p;}return r;} inline int inv_(int a) {return pow_(a, mod-2, mod);} inline int add(int a, int b){a+=b;if(a>=mod)a-=mod;return a;} inline int mul(int a, int b){return a*1ll*b%mod;} inline int sub(int a, int b){a-=b;if(a<0)a+=mod;return a;} inline void adds(int& a, int b){a+=b;if(a>=mod)a-=mod;} const int fin = 1; vector graph[100100]; int pathCount[100100]; int sub_sz[100100]; int vis[100100]; int marker = 1; int n; void dfs(int u) { sub_sz[u] = 1; vis[u] = marker; for (int c : graph[u]) if (vis[c] != marker && vis[c] != fin) { dfs(c); sub_sz[u] += sub_sz[c]; } } int getCenter(int u, int p, int s) { for (int c : graph[u]) if (c != p && vis[c] != fin) { if (sub_sz[c] * 2 > s) return getCenter(c, u, s); } return u; } int getCenter(int u){ ++marker; dfs(u); return getCenter(u, -1, sub_sz[u]); } int computePaths(int u, int p, int lastHt, vector& pCnt) { int d = ++lastHt; if (sz(pCnt) <= lastHt) pCnt.resize(lastHt<<1); pCnt[lastHt] += 1; adds(pathCount[lastHt], 2); for (int c : graph[u]) if (c != p && vis[c] != fin) { d = max(d, computePaths(c, u, lastHt, pCnt)); } return d; } typedef double ld; typedef complex pt; ld PI = acos(-1); void fft(pt * a, int n, bool inv) { for (int i = 1, j = 0; i < n; i++) { int bit = n >> 1; for (; j >= bit; bit >>= 1) j -= bit; j += bit; if (i < j) swap(a[i], a[j]); } for (int len = 2; len <= n; len <<= 1) { ld ang = 2 * PI / len * (inv ? -1 : 1); pt wlen(cos(ang), sin(ang)); for (int i = 0; i < n; i += len) { pt w(1); for (int j = 0; j < len/2; j++, w *= wlen) { pt u = a[i+j], v = a[i+j+len/2] * w; a[i+j] = u + v, a[i+j+len/2] = u - v; } } } if(inv) for(int i = 0; i < n; ++i) { a[i] /= n; } } pt df1[1<<17], df2[1<<17]; void convolve(vector & a, vector & b, int n2) { int n1 = sz(a); if (n1 * 1ll* n2 <= 100000){ rep(i, n1) rep(j, n2) adds(pathCount[i+j], mul(a[i], b[j]<<1)); } else { int n = 1; while(n+1= mod) x %= mod; if (x) adds(pathCount[i], x); } } } void solve(int u) { u = getCenter(u); adds(pathCount[0], 1); bool firstChild = true; vector v, v1; for (int c : graph[u]) if (vis[c] != fin) { if (firstChild) { computePaths(c, u, 0, v); firstChild = false; continue; } // d : maximum depth in that subtree int d = computePaths(c, u, 0, v1) + 1; convolve(v, v1, d); if (d > sz(v)) v.resize(d); rep(i, d) { adds(v[i], v1[i]); v1[i] = 0; } } vis[u] = fin; for(int c : graph[u]) if (vis[c] != fin) solve(c); } //-----------.----------.----------- int nttTmp[1<<17]; void ntt(int * ar, int n, int w) { if (n == 1) return ; int n2 = n>>1; for (int i = 1; i < n; i += 2) nttTmp[i/2] = ar[i]; rep(i, n2) ar[i] = ar[i<<1]; rep(i, n2) ar[i+n2] = nttTmp[i]; ntt(ar, n2, mul(w, w)); ntt(ar + n2, n2, mul(w, w)); int c = 1; rep(i, n2) { int toMul = mul(c, ar[i+n2]); ar[i+n2] = sub(ar[i], toMul); ar[i] = add(ar[i], toMul); c = mul(c, w); } } //-----------.----------.----------- int fact[1<<18]; int factInv[1<<18]; int dda[2][2][1<<18]; int ddb[2][2][1<<18]; ll ddI[2][2][1<<18]; int dp[1<<10][1<<10]; const int primes[3] = {(25<<22) + 1, (105<<23) + 1, (3<<18) + 1}; const int gens[3] = {3, 13, 5}; const int U = (1<<15) - 1; int w[3], nI[3]; ll cx, cy, cp; inline int ncr(int n, int r) { if (n < r || r < 0) return 0; return n < 1024 ? dp[n][r] : mul(fact[n], mul(factInv[r], factInv[n - r])); } void init() { rep(i, 1<<10) rep(j, i+1) { if (i == j || j == 0) dp[i][j] = 1; else dp[i][j] = add(dp[i-1][j-1], dp[i-1][j]); } fact[0] = 1; for (int i = 1; i < (1<<18); ++i) fact[i] = mul(fact[i-1], i); factInv[(1<<18)-1] = inv_(fact[(1<<18)-1]); for (int i = (1<<18)-2; i >= 0; --i) factInv[i] = mul(factInv[i+1], i+1); const int & p1 = primes[0], & p2 = primes[1]; cp = p1 * 1ll * p2; cx = p2 * 1ll * pow_(p2, p1-2, p1); cy = p1 * 1ll * pow_(p1, p2-2, p2); } // ----------.----------.----------- int tmp[1<<18]; inline ll fastMul1(ll a, int b) { ll ans = 0; while(b) { if (b & 1) {ans += a; if (ans >= cp) ans -= cp;} b >>= 1; a <<= 1; if (a >= cp) a -= cp; } return ans; } inline ll fastMul(ll val, int n) { ll q=((double)val*(double)n/(double)cp); ll res=val*n-cp*q; res=(res%cp+cp)%cp; return res; } // Chinese Remainder's Theorem inline ll combine(int r0, int r1) { ll ans = fastMul(cx, r0) + fastMul(cy, r1); if (ans >= cp) ans -= cp; return ans; } void do_ntt(int * a0, int * b0, int * a1, int * b1, ll * res, int n) { mod = primes[0]; rep(i, n) tmp[i] = mul(a0[i], b0[i]); ntt(tmp, n, w[0]); rep(i, n) res[i] = mul(tmp[i], nI[0]); mod = primes[1]; rep(i, n) tmp[i] = mul(a1[i], b1[i]); ntt(tmp, n, w[1]); rep(i, n) res[i] = combine(res[i], mul(tmp[i], nI[1])); mod = (int)1e9 + 7; rep(i, n) res[i] %= mod; } void poly_mul(int * a, int * b, int * res, int n) { // rep(i, n) rep(j, n) adds(res[i+j], mul(a[i], b[j])); rep(k, 2) { rep(i, n) { dda[k][0][i] = a[i] & U; dda[k][1][i] = a[i] >> 15; ddb[k][0][i] = b[i] & U; ddb[k][1][i] = b[i] >> 15; } mod = primes[k]; w[k] = pow_(gens[k], (mod-1)/n); ntt(dda[k][0], n, w[k]); ntt(dda[k][1], n, w[k]); ntt(ddb[k][0], n, w[k]); ntt(ddb[k][1], n, w[k]); w[k] = inv_(w[k]); nI[k] = inv_(n); mod = (int)1e9 + 7; } rep(i, 2) rep(j, 2) do_ntt(dda[0][i], ddb[0][j], dda[1][i], ddb[1][j], ddI[i][j], n); rep(i, n) { res[i] = add(ddI[0][0][i], (ddI[1][1][i] << 30) % mod); adds(res[i], ((ddI[0][1][i] + ddI[1][0][i]) << 15) % mod); } } vector brute() { vector ans(n); rep(i, n) { for(int p=i;p a(N); vector b(N); vector ans(N); int e = n - 1; rep(i, n) a[i] = mul(pathCount[i], fact[e - i]); rep(i, n) b[i] = factInv[i]; poly_mul(a.data(), b.data(), ans.data(), N); for (int d = 0; d < n; ++d) { int f_ans = mul(ans[e - d], mul(fact[e - d], factInv[e])); pin(f_ans); } putchar(10); return 0; }