Untitled diff
12 removals
218 lines
84 additions
289 lines
import java.io.OutputStream;
import java.io.OutputStream;
import java.io.IOException;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.io.BufferedWriter;
import java.io.Writer;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.OutputStreamWriter;
import java.util.InputMismatchException;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStream;
/**
/**
* Built using CHelper plug-in
* Built using CHelper plug-in
* Actual solution is at the top
* Actual solution is at the top
*/
*/
public class Main {
public class Main {
public static void main(String[] args) {
public static void main(String[] args) {
InputStream inputStream = System.in;
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
OutputStream outputStream = System.out;
InputReader in = new InputReader(inputStream);
InputReader in = new InputReader(inputStream);
OutputWriter out = new OutputWriter(outputStream);
OutputWriter out = new OutputWriter(outputStream);
ConnectedPermutations solver = new ConnectedPermutations();
ColoredForests solver = new ColoredForests();
solver.solve(1, in, out);
solver.solve(1, in, out);
out.close();
out.close();
}
}
static class ConnectedPermutations {
static class ColoredForests {
public static int mod = 924844033;
public static int mod = 924844033;
public static long pr = Utils.mod_exp(5, 21 * 21 * 2, mod);
public static long pr = Utils.mod_exp(5, 21 * 21 * 2, mod);
public static long[] om;
public static long[] om;
public static long[] cways;
public long[] fact;
public long[] ifact;
public long[] inv;
public long[] vals;
public long[] vals;
public long[] tr;
public long[] tr;
static {
static {
om = new long[21];
om = new long[21];
om[20] = pr;
om[20] = pr;
for (int i = 19; i >= 0; i--) {
for (int i = 19; i >= 0; i--) {
om[i] = om[i + 1] * om[i + 1] % mod;
om[i] = om[i + 1] * om[i + 1] % mod;
}
}
}
public long comb(int n, int k) {
return fact[n] * ifact[k] % mod * ifact[n - k] % mod;
}
}
public void solve(int testNumber, InputReader in, OutputWriter out) {
public void solve(int testNumber, InputReader in, OutputWriter out) {
int n = in.nextInt();
int n = in.nextInt(), c = in.nextInt();
int m = 1 << 19;
int m = 1 << 17;
cways = new long[m + 2];
cways[0] = 1;
long[][] x = Factorials.getFIF(m + 2, mod);
fact = x[0];
ifact = x[1];
inv = x[2];
for (int i = 0; i < c; i++) cways[i] = 0;
long[][] pow = new long[c + 1][cways.length];
for (int i = 1; i <= c; i++) {
pow[i][0] = 1;
for (int j = 1; j < cways.length; j++) {
pow[i][j] = pow[i][j - 1] * i % mod;
}
}
long[][] comb = new long[c + 1][c + 1];
for (int i = 0; i <= c; i++) for (int j = 0; j <= i; j++) comb[i][j] = comb(i, j);
for (int i = c; i < cways.length; i++) {
cways[i] = Utils.mod_exp(c, i, mod);
for (int j = i - 1; j >= i - c; j--) {
if (((i - j) & 1) == 1) {
cways[i] = (cways[i] - comb[c][c - i + j] * pow[c - i + j][i]) % mod;
if (cways[i] < 0) cways[i] += mod;
} else {
cways[i] = (cways[i] + comb[c][c - i + j] * pow[c - i + j][i]) % mod;
}
}
}
vals = new long[m + 1];
vals = new long[m + 1];
vals[1] = 1;
for (int i = 2; i <= m; i++) vals[i] = vals[i - 1] * i % mod;
tr = new long[m + 1];
tr = new long[m + 1];
System.arraycopy(vals, 0, tr, 0, m + 1);
for (int i = 1; i <= m; i++) {
f(1, m);
tr[i] = Utils.mod_exp(i, i - 2, mod) * ifact[i - 1] % mod * cways[i] % mod;
}
vals[0] = 1;
f(0, m - 1);
for (int i = 1; i <= n; i++)
for (int i = 1; i <= n; i++)
out.println(vals[i]);
out.println(vals[i] * fact[i] % mod);
}
}
public void f(int start, int end) {
public void f(int start, int end) {
if (start == end) return;
if (start == end) {
if (start != 0) vals[start] = vals[start] * inv[start] % mod;
return;
}
int mid = (start + end) / 2;
int mid = (start + end) / 2;
f(start, mid);
f(start, mid);
long[] x = Arrays.copyOfRange(vals, start, mid + 1);
long[] x = Arrays.copyOfRange(vals, start, mid + 1);
long[] rr = multiply(x, tr);
long[] rr = multiply(x, tr);
for (int i = mid + 1; i <= end; i++)
for (int i = mid + 1; i <= end; i++)
vals[i] = (vals[i] - rr[i - start] + mod) % mod;
vals[i] = (vals[i] + rr[i - start] + mod) % mod;
f(mid + 1, end);
f(mid + 1, end);
}
}
public void fft(long[] a, long omega) {
public void fft(long[] a, long omega) {
int N = a.length;
int N = a.length;
if (N == 1) return;
if (N == 1) return;
long[] even = new long[N / 2];
long[] even = new long[N / 2];
long[] odd = new long[N / 2];
long[] odd = new long[N / 2];
for (int i = 0; 2 * i < N; i++) even[i] = a[2 * i];
for (int i = 0; 2 * i < N; i++) even[i] = a[2 * i];
for (int i = 0; 2 * i + 1 < N; i++) odd[i] = a[2 * i + 1];
for (int i = 0; 2 * i + 1 < N; i++) odd[i] = a[2 * i + 1];
long omega2 = omega * omega % mod;
long omega2 = omega * omega % mod;
fft(even, omega2);
fft(even, omega2);
fft(odd, omega2);
fft(odd, omega2);
long cur = 1;
long cur = 1;
for (int i = 0; i < N / 2; i++) {
for (int i = 0; i < N / 2; i++) {
long x = cur * odd[i] % mod;
long x = cur * odd[i] % mod;
a[i] = (even[i] + x) % mod;
a[i] = (even[i] + x) % mod;
a[i + N / 2] = (even[i] + mod - x) % mod;
a[i + N / 2] = (even[i] + mod - x) % mod;
cur = cur * omega % mod;
cur = cur * omega % mod;
}
}
}
}
public long[] multiply(long[] a, long[] b) {
public long[] multiply(long[] a, long[] b) {
int resultSize = Integer.highestOneBit(a.length - 1) << 2;
int resultSize = Integer.highestOneBit(a.length - 1) << 2;
resultSize = Math.max(resultSize, 2);
resultSize = Math.max(resultSize, 2);
long[] ax = new long[resultSize];
long[] ax = new long[resultSize];
long[] bx = new long[resultSize];
long[] bx = new long[resultSize];
for (int i = 0; i < a.length; i++)
for (int i = 0; i < a.length; i++)
ax[i] = a[i];
ax[i] = a[i];
for (int i = 0; i < b.length && i < resultSize; i++)
for (int i = 0; i < b.length && i < resultSize; i++)
bx[i] = b[i];
bx[i] = b[i];
int ww = 31 - Integer.numberOfLeadingZeros(resultSize);
int ww = 31 - Integer.numberOfLeadingZeros(resultSize);
fft(ax, om[ww]);
fft(ax, om[ww]);
fft(bx, om[ww]);
fft(bx, om[ww]);
for (int i = 0; i < resultSize; i++)
for (int i = 0; i < resultSize; i++)
ax[i] = ax[i] * bx[i] % mod;
ax[i] = ax[i] * bx[i] % mod;
fft(ax, Utils.inv(om[ww], mod));
fft(ax, Utils.inv(om[ww], mod));
long[] result = new long[resultSize];
long[] result = new long[resultSize];
long d = Utils.inv(resultSize, mod);
long d = Utils.inv(resultSize, mod);
for (int i = 0; i < resultSize; i++) {
for (int i = 0; i < resultSize; i++) {
result[i] = ax[i] * d % mod;
result[i] = ax[i] * d % mod;
}
}
return result;
return result;
}
}
}
}
static class OutputWriter {
static class OutputWriter {
private final PrintWriter writer;
private final PrintWriter writer;
public OutputWriter(OutputStream outputStream) {
public OutputWriter(OutputStream outputStream) {
writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
}
}
public OutputWriter(Writer writer) {
public OutputWriter(Writer writer) {
this.writer = new PrintWriter(writer);
this.writer = new PrintWriter(writer);
}
}
public void close() {
public void close() {
writer.close();
writer.close();
}
}
public void println(long i) {
public void println(long i) {
writer.println(i);
writer.println(i);
}
}
}
}
static class InputReader {
static class InputReader {
private InputStream stream;
private InputStream stream;
private byte[] buf = new byte[1024];
private byte[] buf = new byte[1024];
private int curChar;
private int curChar;
private int numChars;
private int numChars;
public InputReader(InputStream stream) {
public InputReader(InputStream stream) {
this.stream = stream;
this.stream = stream;
}
}
public int read() {
public int read() {
if (this.numChars == -1) {
if (this.numChars == -1) {
throw new InputMismatchException();
throw new InputMismatchException();
} else {
} else {
if (this.curChar >= this.numChars) {
if (this.curChar >= this.numChars) {
this.curChar = 0;
this.curChar = 0;
try {
try {
this.numChars = this.stream.read(this.buf);
this.numChars = this.stream.read(this.buf);
} catch (IOException var2) {
} catch (IOException var2) {
throw new InputMismatchException();
throw new InputMismatchException();
}
}
if (this.numChars <= 0) {
if (this.numChars <= 0) {
return -1;
return -1;
}
}
}
}
return this.buf[this.curChar++];
return this.buf[this.curChar++];
}
}
}
}
public int nextInt() {
public int nextInt() {
int c;
int c;
for (c = this.read(); isSpaceChar(c); c = this.read()) {
for (c = this.read(); isSpaceChar(c); c = this.read()) {
;
;
}
}
byte sgn = 1;
byte sgn = 1;
if (c == 45) {
if (c == 45) {
sgn = -1;
sgn = -1;
c = this.read();
c = this.read();
}
}
int res = 0;
int res = 0;
while (c >= 48 && c <= 57) {
while (c >= 48 && c <= 57) {
res *= 10;
res *= 10;
res += c - 48;
res += c - 48;
c = this.read();
c = this.read();
if (isSpaceChar(c)) {
if (isSpaceChar(c)) {
return res * sgn;
return res * sgn;
}
}
}
}
throw new InputMismatchException();
throw new InputMismatchException();
}
}
public static boolean isSpaceChar(int c) {
public static boolean isSpaceChar(int c) {
return c == 32 || c == 10 || c == 13 || c == 9 || c == -1;
return c == 32 || c == 10 || c == 13 || c == 9 || c == -1;
}
}
}
}
static class Utils {
static class Utils {
public static long inv(long N, long M) {
public static long inv(long N, long M) {
long x = 0, lastx = 1, y = 1, lasty = 0, q, t, a = N, b = M;
long x = 0, lastx = 1, y = 1, lasty = 0, q, t, a = N, b = M;
while (b != 0) {
while (b != 0) {
q = a / b;
q = a / b;
t = a % b;
t = a % b;
a = b;
a = b;
b = t;
b = t;
t = x;
t = x;
x = lastx - q * x;
x = lastx - q * x;
lastx = t;
lastx = t;
t = y;
t = y;
y = lasty - q * y;
y = lasty - q * y;
lasty = t;
lasty = t;
}
}
return (lastx + M) % M;
return (lastx + M) % M;
}
public static long mod_exp(long b, long e, long mod) {
long res = 1;
while (e > 0) {
if ((e & 1) == 1)
res = (res * b) % mod;
b = (b * b) % mod;
e >>= 1;
}
return res;
}
}
static class Factorials {
public static long[][] getFIF(int max, int mod) {
long[] fact = new long[max];
long[] ifact = new long[max];
long[] inv = new long[max];
inv[1] = 1;
for (int i = 2; i < max; i++) {
inv[i] = (mod - mod / i) * inv[mod % i] % mod;
}
fact[0] = 1;
ifact[0] = 1;
for (int i = 1; i < max; i++) {
fact[i] = fact[i - 1] * i % mod;
ifact[i] = ifact[i - 1] * inv[i] % mod;
}
return new long[][]{fact, ifact, inv};
}
}
}
}
}
}