{"code":"grid1","name":"Đếm đường đi trên ma trận 1","description":"Cho ma trận gồm $H$ hàng và $W$ cột. Gọi $(i,j)$ là ô vuông ở hàng thứ $i$ và cột thứ $j$.\r\n\r\nVới mỗi $i,j(1\\le i\\le H,1\\le j\\le W)$, ô vuông $(i,j)$ được mô tả bởi kí tự $a_{i,j}$. Nếu $a_{i,j}=$`.` thì ô vuông này trống rỗng, nếu $a_{i,j}=$ `#` thì ô vuông này chứa vật cản.\r\n\r\n$Kaninho$ bắt đầu ở ô vuông $(1,1)$ và muốn đến ô vuông $(H,W)$ bằng việc lặp lại các bước: Đi sang phải hoặc đi xuống dưới ô trống kề với nó.\r\n\r\nTìm số con đường mà $Kaninho$ có thể đi được từ ô $(1,1)$ đến ô $(H,W)$. Bởi vì đáp án có thể lớn, nên trước khi in ra cần lấy mod $10^9+7$.\r\n\r\n

Input

\r\n\r\n+ Dòng thứ nhất chứa hai số nguyên $H,W(2\\le H,W\\le 1000)$ \r\n\r\n+ $H$ dòng tiếp theo, mỗi dòng chứa $W$ kí tự $a_{i,1},a_{i,2},...,a_{i,W}(1\\le i\\le H)$ - thể hiện ma trận $Kaninho$ cần đi. Biết rằng đề ra luôn đảm bảo các ô $(1,1)$ và $(H,W)$ đều trống.\r\n\r\n

Output

\r\n\r\n+ In ra đáp án cần tìm.\r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 3 4\r\n ...#\r\n .#..\r\n ....\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 3\r\n ```\r\n \r\n ??? warning \"Note\"\r\n\r\n ","points":400.0,"partial":false,"time_limit":2.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}