Bessie's Direction-Constrained Path Counting

Bessie the cow is on her way back from her favorite pasture to the barn. The farm is organized as an \(N \times N\) grid (\(2 \le N \le 50\)). The pasture is located at the top-left cell and the barn at the bottom-right cell. Bessie can only move right or down. Some cells contain haybales, represented by '#' in the grid, and Bessie cannot pass through these obstacles; she must go around them.

Feeling a bit tired today, Bessie wishes to change her walking direction at most \(K\) times (\(1 \le K \le 3\)). Changing direction is defined when the current move is different from the previous move; note that the first move does not count as a change. Two routes are considered different if there is at least one cell that is visited in one route and not in the other.

Determine the number of distinct paths Bessie can take from the pasture to the barn while obeying these rules.

inputFormat

The first line contains two integers \(N\) and \(K\). The next \(N\) lines each contain a string of \(N\) characters. Each character is either a . (representing an open cell) or a # (representing a haybale which Bessie cannot traverse).

outputFormat

Output a single integer representing the number of distinct paths from the top-left corner to the bottom-right corner with at most \(K\) direction changes.

sample

2 1
..
..

2