Description

一个 $N×N$ 的跳棋棋盘，有 $N$ 个皇后棋子被放置在棋盘上，使得每行、每列有且只有一个皇后棋子，每条对角线（包括两条主对角线的所有平行线）上至多有一个皇后棋子。棋盘上一部分格子可以放置棋子，而另一部分则不可以。

求放置棋子的方案总数。

Input Format

第一行有一个 $N$。接下来有 $N$ 行 $N$ 列描述一个棋盘，* 表示可放，. 表示不可放。

Output Format

输出方案总数。

4
**.*
****
****
****

1

Hint

$0< n\le14$