#1027. 不喜欢拐弯 3 一秒512M

不喜欢拐弯 3 一秒512M

当前没有测试数据。

题目描述

一个 N×N 的棋盘,你要从左上角走到右下角,只能竖直向下走或水平向右走,不能走出棋盘外。每个格子要么是黑色,要么是白色。你不喜欢黑色,所以你绝不会踏入黑格子。你也不喜欢拐弯,所以在路途中,你不会拐弯超过 K 次。问:你有多少条不同的路线?

注:在起点处你可以任选一个方向开始行走,不计入拐弯次数。

输入格式

第一行两个整数 N, K。

接下来是一个 N×N 的字符矩阵,只包括两种字符:.,H,其中 . 表示白格子,H 表示黑格子。数据保证起点和终点是白格子。

输出格式

一个整数,表示不同路线条数。答案可能很大,你需要将答案对 998244353 取模后输出

样例输入

4 3
...H
.H..
....
H...

样例输出

6

数据范围

所有测试点满足:2≤N≤300,1≤K≤2×N-3