题目描述

在 Enchoveka 的餐馆里，有 N 个人，编号为 1,2,...,N。他们围坐在一张圆桌旁，使得：

• 对于 1 < i <= N，编号为 i 的人坐在编号为 i-1 的人的右边；
• 编号为 1 的人坐在编号为 N 的人的右边。

餐馆里只允许谈论 K 个特定话题，话题编号为 1,2,...,K。每个人都对其中的一部分话题感兴趣，并且每个人至少对一个话题感兴趣。

Enchoveka 不希望餐馆变成嘈杂的地方，因此每一场谈话都只能发生在圆桌上连续的一段人之间。现在他希望把这 N 个人划分成若干组，使得：

• 每个人恰好属于一组；
• 每一组中的人都坐在圆桌上的连续位置；
• 对于每一组，至少存在一个话题，是这一组所有人都共同感兴趣的。

请你计算：满足上述条件的分组方案数有多少种。答案对 10^9 + 7 取模。

输入格式

第一行输入两个正整数 N 和 K，分别表示人数和话题数。

接下来 N 行，每行包含一个长度为 K 的 01 串，表示对应那个人对哪些话题感兴趣：

• 若第 i 行第 j 个字符为 1，则表示编号为 i 的人对编号为 j 的话题感兴趣；
• 若为 0，则表示不感兴趣。

输出格式

输出一个整数，表示合法分组方案数对 10^9 + 7 取模后的结果。

数据范围

• 1 <= N × K <= 10^7

子任务

样例

输入

3 3
101
110
011

输出

4

样例解释

共有 4 种不同的合法划分：

1. 三个人都各自单独成组；
2. 第 1 人和第 2 人在同一组，第 3 人单独成组；
3. 第 2 人和第 3 人在同一组，第 1 人单独成组；
4. 第 1 人和第 3 人在同一组，第 2 人单独成组。

说明

虽然题目背景是“围成一圈”，但分组时要求的是每组对应圆桌上的一段连续区间，因此本质上需要处理环形划分计数问题。

由于 K <= 60 的子任务较强，通常需要考虑用位运算 / 位集来表示共同感兴趣的话题集合。