Seat

seat.cpp/in/out

• 时间限制：1.0s
• 空间限制：512MB

题目描述

有 $n + 2$ 个座位等距地排成一排，从左到右编号为 $0$ 至 $n + 1$。

最开始时 0 号以及 $n + 1$ 号座位上已经坐了一个小 G，接下来会有 $n$ 个小 G 依次找一个空座位坐下。由于小 G 们坐得太近就容易互相搏弈，每个小 G 会找一个当前离最近的小 G 距离最远的座位坐下。如果有多个备选的座位，这个小 G 会等概率选择其中一个。

给出 $n$，求第 $i$ 个坐下的小 G 坐在 $j$ 号座位的概率，对 $P$ 取模。具体来说，如果答案化为最简分数可以表示为 $\frac{a}{b}$，你需要输出 $a \times b^{-1}$，其中 $b^{-1} = b^{P-2} \pmod P$。

输入格式

从文件 seat.in 中读入数据。

一行两个整数 $n, P$。

输出格式

输出到文件 seat.out 中。

输出 $n$ 个整数，第 $i$ 行第 $j$ 个整数表示第 $i$ 个小 G 坐在第 $j$ 个座位的概率。

样例 1 输入

4 10007

样例 1 输出

0 5004 5004 0
3336 1668 1668 3336
3336 1668 1668 3336
3336 1668 1668 3336

样例 1 解释

第一个小 G 会在中间两个位置中随机选择一个，接下来无论选哪个位置最近的距离都是 1。

$\frac{1}{2} = 5004 \pmod{10007}$，$\frac{1}{3} = 3336 \pmod{10007}$，$\frac{1}{6} = 1668 \pmod{10007}$。

样例 2

见选手目录下的 seat/seat2.in 与 seat/seat2.ans。

数据范围

对于所有数据，满足 $2 \le n \le 1024$，$2000 \le P \le 30000$，$P$ 是质数。本题共 25 个测试点，每个测试点 4 分。