Given N positions in a row, for every k from 1 through N, count the ways to choose k positions so that no two chosen positions are adjacent. Print each answer modulo 1,000,000,007.
Suppose the chosen positions are x_1 < x_2 < ... < x_k. Since consecutive choices cannot be adjacent, each gap satisfies x_(i+1) >= x_i + 2. Shift the i-th chosen position left by i - 1, defining y_i = x_i - (i - 1). The y_i are now strictly increasing positions chosen from 1 through N - k + 1. This is a bijection: from any k distinct positions in that shortened range, adding i - 1 to the i-th one recovers a unique valid selection in the original row. Therefore the answer is C(N - k + 1, k). If k > N - k + 1, there are not enough positions after removing the required gaps, so the answer is zero.
Precompute factorials through N, then compute inverse factorials using Fermat’s little theorem: for nonzero a modulo the prime MOD, a^(MOD-1) ≡ 1, so a^(MOD-2) is its inverse. One binary exponentiation obtains the inverse of N!; walking downward gives every inverse factorial. Then C(n, k) = n! / (k!(n-k)!) is evaluated with modular multiplication.
The preprocessing takes O(N + log MOD) time and O(N) space; each of the N answers takes constant time. Products of two residues fit in Java long because they are below MOD^2 < Long.MAX_VALUE.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
import java.io.*;
public class Main {
static final long MOD = 1_000_000_007L;
static class FastScanner {
private final InputStream input;
private final byte[] buffer = new byte[1 << 16];
private int length = 0;
private int pointer = 0;
FastScanner(InputStream input) {
this.input = input;
}
private int read() throws IOException {
if (pointer == length) {
length = input.read(buffer);
pointer = 0;
if (length == -1) return -1;
}
return buffer[pointer++];
}
int nextInt() throws IOException {
int c;
do {
c = read();
} while (c <= ' ' && c != -1);
int value = 0;
while (c > ' ') {
value = value * 10 + c - '0';
c = read();
}
return value;
}
}
static long modPow(long base, long exponent) {
long result = 1;
while (exponent > 0) {
if ((exponent & 1) == 1) result = result * base % MOD;
base = base * base % MOD;
exponent >>= 1;
}
return result;
}
public static void main(String[] args) throws IOException {
FastScanner input = new FastScanner(System.in);
int n = input.nextInt();
long[] factorial = new long[n + 1];
long[] inverseFactorial = new long[n + 1];
factorial[0] = 1;
for (int i = 1; i <= n; i++) {
factorial[i] = factorial[i - 1] * i % MOD;
}
inverseFactorial[n] = modPow(factorial[n], MOD - 2);
for (int i = n; i > 0; i--) {
inverseFactorial[i - 1] = inverseFactorial[i] * i % MOD;
}
StringBuilder output = new StringBuilder();
for (int k = 1; k <= n; k++) {
int available = n - k + 1;
long ways = 0;
if (k <= available) {
ways = factorial[available] * inverseFactorial[k] % MOD
* inverseFactorial[available - k] % MOD;
}
output.append(ways).append('\n');
}
System.out.print(output);
}
}