背景

萌萌哒的TKD正在打代码,耳边放着Flower Dance,手指轻快地在键盘上舞动。
听着这美妙的旋律,TKD不禁想起了什么。
第一次遇到Po姐姐的时候,就一起欣赏了美丽的花舞吧。
两个人自由地在花海中徜徉...徜徉......
那真的是段美妙的回忆呢~

 

描述

欣赏花舞之后,腹黑的Po姐姐和TKD聊了起来。
‘TKD啊,你还记得我们是怎么走过花海的吗?’
‘唔...貌似记得不是太清楚了>v<’
‘我刚才观察了一下,其实花海中能走的路,就是一个n*m的网格图’
‘哦?是吗OwO’
‘然后呢,有一些节点被调皮的小妖精堵住了,是不能走的’
‘嗯是的,好可爱的妖精呢>_<’
‘即便如此我们还是都走了最短的路径呢~’
‘嗯嗯!~’
‘而且我还刻意走了一条和你走的路不相交的路哦~’
‘姐姐真是厉害呀,连我走的路是什么都知道~~~’
‘当然啊,姐姐可比你厉害多了。现在我考考你,我们从左上角走到右下角,只能向右或者向下走,有多少总走法呢?’
‘啊——?’
萌萌哒的TKD完全没有想到Po姐姐会如此腹黑。
你能帮TKD解答腹黑姐姐的问题吗~

 

输入格式

第一行两个正整数n和m,代表花海的大小
接下来n行每行一个长度为m的01串,描述花海中的每一个点
其中0代表可以走,1代表这个点被小妖精封住辣~
数据保证花海的左上角和右下角没有小妖精

 

输出格式

一行一个整数,代表Po姐姐和TKD从左上角走到右下角的方案数
答案对1000000007(109+7)取模
注意:对于两条不相交的路径A和B,如果Po姐姐走了A,TKD走了B,和Po姐姐走了B,TKD走了A我们视为同一种方案

 

样例输入

4 4
0001
0100
0000
0000

 

样例输出

5

 

数据范围与约定

  • 对于20%的数据,2\leq n,m\leq 10
  • 对于40%的数据,2\leq n,m\leq 100
  • 对于另外10%的数据,花海中不存在小妖精
  • 对于100%的数据,2\leq n,m\leq 2000

 

样例解释

五种方案如下图所示: