小 Zina 梦想成为一名机器人工程师。她下载了一个模拟程序，沉浸在机器人计算机生成谜题的世界中。

在其中一个问题中，机器人站在一面无限长的墙前，墙上有一排从左到右依次排列的开关。每个开关的宽度为 1 厘米。最初，所有开关都是关闭的。

机器人可以拥有多个机械臂。每个机械臂是一排包含一个或多个手指插槽的结构，每个插槽宽度为 1 厘米，每个插槽要么是空的，要么安装有一个手指。例如，Zina 目前的机器人有两个机械臂：一个有 5 个插槽，手指安装在第 1、中间和最后一个插槽中；另一个有 3 个插槽，每个插槽都安装有手指。

当机器人触碰墙壁，使得手指的位置与某些开关的位置重合时，被手指触碰的开关状态会变为相反（关闭的开关变为开启，开启的开关变为关闭）。每个机械臂可以自由地向左或向右移动，但不能旋转。每个机械臂可以在任意位置触碰墙壁任意多次。

一旦开关的状态达到某种情况，即最左侧开启的开关的左边缘与最右侧开启的开关的右边缘之间的距离恰好为 $k$ 厘米时，墙上就会打开一个通道，机器人就可以进行下一个任务。例如，Zina 现在看到的墙壁满足 $k = 5$。如果关于 $k$ 厘米的条件不再满足，通道就会再次关闭。

Zina 解决了这个问题和其他一些问题，但其中一个她始终无法攻克。她去论坛阅读后了解到，确实由于模拟程序中的一个错误，有些问题根本没有解，而有些问题在最左侧和最右侧开启的开关之间有不止一种可能的开关配置。Zina 思考：给定一个特定的问题，如何找到它有多少种解？

请解决 Zina 问题的推广版本。给定可用机械臂的列表和数字 $k$，求出有多少种可能的最终开关配置，使得通道是打开的。

输入格式

输入的第一行包含两个整数 $n$ 和 $k$：机器人的机械臂数量以及开启的开关边缘之间所需的距离 ($1 \le n, k \le 50$)。

接下来的 $n$ 行描述了机械臂。每一行由 0 和 1 组成，从左到右列出插槽：0 对应空插槽，1 对应带有手指的插槽。保证每行的长度在 1 到 50 个字符之间，并且保证每行的第一个和最后一个字符都是 1。

输出格式

输出一个整数：使用可用机械臂可以获得的、且最左侧开启的开关的左边缘与最右侧开启的开关的右边缘之间的距离恰好为 $k$ 厘米的不同开关配置的数量。如果两种配置是通过不同方式获得的，但开关的状态相同，则它们被视为相等。可以通过向左或向右平移而相互得到的配置也被视为相等。

样例

样例输入 1

2 5
10101
111

样例输出 1

2

样例输入 2

2 3
1001
100011

样例输出 2

1