题目描述

在山顶堡垒之旅结束后，Alex 陷入了新的纠结：他既不想回家，也不知道接下来该去哪里。于是他想出了一个办法。

Alex 知道克卢日-纳波卡有 M 处景点。他打算询问自己的每一位朋友，对这 M 处景点分别是否喜欢。每位朋友的意见由一个长度为 M 的 01 串表示，其中：

• 1 表示“我喜欢”；
• 0 表示“我不喜欢”。

在收集完所有意见后，Alex 会选取一个朋友子集 S，然后只考虑这些朋友的意见，并执行如下算法：

按景点编号从 1 到 M 依次处理。处理当前景点时，把子集 S 中所有当前仍未被淘汰、但对该景点的意见不属于多数派的朋友全部删除。

• “多数派”只在当前尚未被淘汰的朋友中统计；
• 若两种意见人数相同，则认为喜欢该景点（即 1）的一方是多数派。

算法结束后，Alex 会留下恰好一种最终意见（这份意见可能由多位朋友共同拥有）。

若某位朋友：

1. 被选入了初始子集 S；
2. 并且算法结束后保留下来的最终意见与该朋友的意见完全相同；

那么称这位朋友的意见被**“采纳（counted）”**。

现在，对每位朋友 i，你需要求出：有多少个子集 S 会使得朋友 i 的意见被采纳。

由于答案可能很大，请对 MOD 取模输出。

输入格式

第一行输入三个整数 N, M, MOD。

接下来 N 行，每行输入一个长度为 M 的 01 串。第 i 行的第 j 个字符为：

• 1：表示朋友 i 喜欢景点 j；
• 0：表示朋友 i 不喜欢景点 j。

输出格式

输出一行 N 个整数，用空格分隔。

第 i 个数表示：使得朋友 i 的意见被采纳的子集 S 的个数，对 MOD 取模。

数据范围

• 1 ≤ N ≤ 4000
• 1 ≤ M ≤ 1000
• 2 ≤ MOD ≤ 1 000 000 007
• MOD 是质数

子任务与评分

样例

输入

3 2 11
10
11
10

输出

3 3 3

样例解释

第一个朋友的意见会在以下子集中被采纳：

{1}，{1, 3}，{1, 2, 3}

第二个朋友的意见会在以下子集中被采纳：

{2}，{1, 2}，{2, 3}

第三个朋友的意见会在以下子集中被采纳：

{3}，{1, 3}，{1, 2, 3}

例如考虑子集 {1, 2}：

• 两位参与者都喜欢第 1 个景点，因此都属于多数派，没有人被淘汰；
• 对于第 2 个景点，出现平票，因此按规则，“喜欢该景点”的一方算多数派，于是第一个朋友被淘汰；
• 算法结束后，只剩下第二个朋友，因此最终被采纳的意见是 11。