Count Routes

Climb from the bottom row to the top row, using at least 1 and at most 2 distinct holds X in every row; # cannot be held. You cannot move down, and the Euclidean distance between consecutively used holds is at most w. Routes are distinguished by their sequence of holds; count the routes modulo 998244353.

This site's standard input/output is stated explicitly.

输入格式

The first line contains n m w, followed by n strings of length m over X/#, from top to bottom. 2≤n≤2000, 1≤m,w≤2000.

输出格式

Output one integer answer.

样例 1

输入：

3 4 1
XX#X
#XX#
#X#X

输出：

2

样例 2

输入：

2 1 1
X
X

输出：

1

样例 3

输入：

2 2 2
##
XX

输出：

0

样例说明

Example 1: from the bottom row you can only continue from column 2, pass through column 2 of the middle row, and reach column 2 of the top row; on the top row you can stop or move on to column 1, for 2 routes in total. Example 2: each of the two rows has one hold, so there is only 1 route. Example 3: the top row has no holds, so it cannot be reached, and the output is 0.