给定一个长度为 $n$ 的二进制字符串 $s$。对于所有 $k$ 从 $1$ 到 $n$，计算长度恰好为 $k$ 的 $s$ 的所有子序列之间的两两汉明距离之和。由于答案可能非常大，请将其对 $40\,961$ 取模。
两个等长字符串之间的汉明距离是指这两个字符串在对应位置上不同的字符个数。
输入格式
输入仅一行，包含一个长度为 $n$ 的字符串 $s$ ($1 \le n \le 8 \cdot 10^3$)，仅由字符 “0” 和 “1” 组成。
输出格式
输出 $n$ 个数字：第 $k$ 个数字应为长度恰好为 $k$ 的 $s$ 的所有子序列之间的两两汉明距离之和，对 $40\,961$ 取模。
样例
输入 1
11000110111001
输出 1
48 4056 15326 31033 20654 29362 32472 13700 21357 12217 20411 12456 212 0
输入 2
000
输出 2
0 0 0