首页 > 试题广场 >

Fluorescent 2

[编程题]Fluorescent 2

时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 512M，其他语言1024M
算法知识视频讲解

In ICPCCamp, there are n switches and m bulbs.The m bulbs are ON at the beginning.
Bobo knows in advance an n x m binary matrix C_{i, j}. When the i-th switch is pressed, all the bulbs j satisfying C_{i, j} = 1 flip its state between ON and OFF.
Let f(S) be the number of bulbs staying ON after the switches in set S is pressed. Find the sum of f(S)³ (cubic of f(S)) modulo (10⁹+7) over all 2ⁿ possible choices of S.

输入描述:

The input consists of several test cases and is terminated by end-of-file.
The first line of each test case contains two integers n and m.
The i-th of the following n lines contains m integers C_{i, 1}, C_{i, 2}, ..., C_{i, m}.

输出描述:

For each test case, print an integer which denotes the result.

示例1

输入

输出

10
30

说明

For the first sample, there are 2² = 4 choices of S.
* , f(S) = 2, .
* S = {1}, f(S) = 1, .
* S = {2}, f(S) = 1, .
* S = {1, 2}, f(S) = 0, .
Thus, the result is 8 + 1 + 1 + 0 = 10.

备注:

* 1 ≤ n ≤ 50
* 1 ≤ m ≤ 1000
* C_{i, j} ∈ {0, 1}
* The number of test cases does not exceed 500.
* The number of test cases with m > 50 does not exceed 1.

算法知识视频讲解