题目描述

在标准的 N 皇后问题中，我们需要在一个 N×N 的国际象棋棋盘上放置 N 个皇后，使得它们彼此之间不能互相攻击（即任意两个皇后不能在同一行、同一列或同一对角线上）。而在本题中，棋盘的部分格子可能被标记为不可放置皇后（用“.”表示），只有标记为“*”的格子可以放置皇后。
你的任务是计算出满足以下条件的所有合法方案总数：
1.每一行必须恰好放置一个皇后。
2.每一列只能放置一个皇后。
3.任何两个皇后不能在同一对角线。
4.皇后只能放置在标记为“*”的格子中。

输入格式：

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

输出格式：

输出方案总数

输入样例#1：

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

输出样例#1：

1

数据范围：

0<n<=14;