binomial

对于给定的 $n$ 和 $p$ ，求对于所有的 $0\le i<p$ ，满足 $\dbinom{n}{k}\bmod p=i$ 的 $k$ 的个数。

注： $\dbinom{n}{k}=\dfrac{n!}{k!\,(n-k)!}$ 。

输入格式

仅一行，包含两个正整数 $n$ 和 $p$ 。

仅一行，为一个长度为 $p$ 的字符串 $s$ ，其中 $s_i$ 表示满足 $\dbinom{n}{k}\bmod p=i$ 的 $k$ 的个数除以 $29$ 后的余数， $s_i$ 视为一个 $29$ 进制的数字。

20 4

D440

当 $n=20$ 、 $p=4$ 时， $\dbinom{20}{k}\bmod 4$ 随 $k=0,1,\dots,20$ 依次为

1, 0, 2, 0, 1, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 1, 0, 2, 0, 1,

其中余数为 $0$ 的有 $13$ 个，余数为 $1$ 的有 $4$ 个，余数为 $2$ 的有 $4$ 个，余数为 $3$ 的有 $0$ 个。把 $13, 4, 4, 0$ 依次写成 $29$ 进制数字（ $13$ 记作 D）即得 D440。

本题为「binomial」，题面与测试数据整理自 BZOJ 2629。

20 4

D440