如果对于每个 $$$1 < i \le n$$$ 都满足 $$$a_i = a_{i-1} + 1$$$,我们称长度为 $$$n$$$ 的数组 $$$a$$$ 为奇特。
让我们将应用于长度为 $$$n$$$ 的排列 $$$^\dagger$$$ 的 $$$f(p)$$$ 称为可以分区的最小子数组数,这样每个子数组都是奇特的。例如 $$$f([1,2,3]) = 1$$$,而 $$$f([3,1,2]) = 2$$$ 且 $$$f([3,2,1]) = 3$$$。
给定 $$$n$$$ 和长度为 $$$n$$$ 的排列 $$$p$$$,我们将长度为 $$$n$$$ 的排列 $$$p'$$$ 定义为 $$$k$$$-特殊当且仅当:
- $$$p'$$$ 按字典顺序比 $$$p$$$ 更小$$$^\ddagger$$$,并且
- $$$f(p') = k$$$。
你的任务是计算每个 $$$1 \le k \le n$$$ 的 $$$k$$$ 特殊排列模 $$$m$$$ 的数量。
$$$^\dagger$$$ 排列是一个数组,由 $$$n$$$ 不同的整数组成,从 $$$1$$$ 到 $$$n$$$,按任意顺序排列。例如,$$$[2,3,1,5,4]$$$ 是一个排列,但 $$$[1,2,2]$$$ 不是排列($$$2$$$ 在数组中出现两次),$$$[1,3,4]$$$ 也不是排列($$$n=3$$$ 但数组中有 $$$4$$$)。
$$$^\ddagger$$$ 长度为 $$$n$$$ 的排列 $$$a$$$ 按字典顺序小于长度为 $$$n$$$ 的排列 $$$b$$$ 当且仅当以下条件成立:在 $$$a$$$ 和 $$$b$$$ 不同的第一个位置,排列 $$$a$$$ 的元素小于对应的元素$$$b$$$ 中的元素。
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 2000$$$, $$$10 \le m \le 10^9$$$) — 排列的长度和所需的模数。
第二行包含 $$$n$$$ 不同的整数 $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$) — 排列 $$$p$$$。
输出
打印 $$$n$$$ 整数,其中第 $$$k$$$ 个整数是 $$$k$$$-特殊排列以 $$$m$$$ 为模的数。
示例
输入 #1
4 666012 1 3 4 2
输出 #1
1 0 1 1
输入 #2
3 10 3 2 1
输出 #2
1 2 2
输入 #3
7 1000000000 7 2 1 3 5 4 6
输出 #3
1 6 40 201 705 1635 1854
输入#4
10 11 10 9 8 7 6 5 4 3 2 1
输出#4
1 9 9 0 1 5 5 0 1 0
注意
在第一个示例中,按字典顺序小于 $$$[1,3,4,2]$$$ 的排列是:
- $$$[1,2,3,4]$$$, $$$f([1,2,3,4])=1$$$;
- $$$[1,2,4,3]$$$, $$$f([1,2,4,3])=3$$$;
- $$$[1,3,2,4]$$$,$$$f([1,3,2,4])=4$$$。
因此我们的答案是$$$[1,0,1,1]$$$。
在第二个示例中,按字典顺序小于 $$$[3,2,1]$$$ 的排列是:
- $$$[1,2,3]$$$, $$$f([1,2,3])=1$$$;
- $$$[1,3,2]$$$, $$$f([1,3,2])=3$$$;
- $$$[2,1,3]$$$, $$$f([2,1,3])=3$$$;
- $$$[2,3,1]$$$, $$$f([2,3,1])=2$$$;
- $$$[3,1,2]$$$,$$$f([3,1,2])=2$$$。
因此我们的答案是$$$[1,2,2]$$$。