typical90_python/src/o.py at master · riantkb/typical90_python · GitHub

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
import sys
from itertools import accumulate

input = sys.stdin.readline

mod = 1000000007


def init_comb(n):
    global facts, invfacts
    facts = [i for i in range(n + 1)]
    facts[0] = 1
    facts = list(accumulate(facts, lambda x, y: x * y % mod))
    invfacts = [n + 1 - i for i in range(n + 1)]
    invfacts[0] = pow(facts[n], -1, mod)
    invfacts = list(reversed(list(accumulate(invfacts,
                                             lambda x, y: x * y % mod))))


def comb(n, r):
    return facts[n] * invfacts[r] * invfacts[n - r] % mod


def main():
    n = int(input())
    init_comb(n)
    for i in range(1, n + 1):
        ans = 0
        for j in range(1, n + 1):
            if n - (i - 1) * (j - 1) < j:
                break
            ans += comb(n - (i - 1) * (j - 1), j)
        print(ans % mod)


if __name__ == "__main__":
    main()