异或和
题号:NC16734
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

有一个n*m的网格图,给出小B出现在每个位置的可能性,用一个n*m的01矩阵表示,小B等概率出现在所有1的位置。求小A在每个位置上与小B期望曼哈顿距离的异或和,先把期望取模之后再异或

输入描述:

第一行读入两个整数 n,m (n,m <= 2000)
接下来n行,每行读入一个长度为m的01字符串。

输出描述:

输出一个整数表示答案模 109+7
示例1

输入

复制
1 3
101

输出

复制
1

说明

小A出现在(1,1)的时候期望曼哈顿距离是1
小A出现在(1,2)的时候期望曼哈顿距离是1
小A出现在(1,3)的时候期望曼哈顿距离是1
答案是这三者的异或和。