Count Self-Avoiding Walks Through a Maze

A garden maze is a grid rows of strings where "." is open path and "#" is a hedge. A visitor enters at the top-left cell and leaves at the bottom-right cell, moving up, down, left or right and never stepping on the same cell twice. Count the number of different walks. If the entrance or exit is a hedge, the answer is 0. A 1x1 open maze has one walk.

Examples

Input:  rows = ["..", ".."]
Output: 2

Input:  rows = ["...", ".#.", "..."]
Output: 2
Explanation: around the hedge clockwise or anticlockwise.

Input:  rows = ["#."]
Output: 0

Constraints

• 1 <= len(rows), len(rows[0]) <= 6 with at most 25 open cells

Goals

• Count simple paths in a grid by marking and unmarking cells
• Handle blocked start or finish cells