AT_joi2010yo_f 方向音痴のトナカイ

今年，圣诞老人再次从天而降来到 JOI 镇。JOI 镇的每一户人家都有孩子，因此圣诞老人必须给镇上的每一户人家送礼物。然而，今年带来的驯鹿有些方向感不佳，并且只能在建筑物的屋顶上降落，所以要给所有人家送完礼物，需要精心设计路线。 JOI 镇的街区按照东西南北方向整齐排列，每个区块可能是住宅、教堂或空地之一。JOI 镇只有一座教堂。圣诞老人和驯鹿将从教堂出发，按照以下规则，给所有住宅各送一次礼物后返回教堂。 - 由于今年的驯鹿方向感不佳，只能沿东西南北任意一个方向直线飞行，不能在空中转向。 - 可以自由飞越尚未送礼物的住宅上空，也可以在尚未送礼物的住宅降落。每次在住宅降落时，必须送出礼物，之后可以沿东西南北任意方向起飞。 - 在 JOI 镇的住宅中，圣诞夜在圣诞老人到来前不会点燃壁炉，但圣诞老人离开后会点燃壁炉。点燃壁炉后，烟囱会冒烟，因此不能再飞越已经送完礼物的住宅上空。 - 可以自由飞越教堂上空，但在所有礼物送完之前不能在教堂降落，因为教堂正在举行礼拜。 - 可以自由飞越空地上空，但不能在空地降落。 给定镇子的结构，请编写程序计算圣诞老人和驯鹿送礼物的路线有多少种。

输入共 $n+1$ 行。第 $1$ 行包含两个用空格分隔的整数 $m$（$1 \leq m \leq 10$）和 $n$（$1 \leq n \leq 10$）。第 $2$ 行到第 $n+1$ 行的每一行包含 $m$ 个用空格分隔的数字 $0$、$1$ 或 $2$，分别表示每个区块的状态。若将北起第 $i$ 行、西起第 $j$ 列的区块记作 $(i, j)$（$1 \leq i \leq n$，$1 \leq j \leq m$），则第 $i+1$ 行第 $j$ 个数为 $0$ 表示该区块为空地，为 $1$ 表示为住宅，为 $2$ 表示为教堂。教堂仅有一座，住宅数量不少于 $1$ 且不超过 $23$。保证测试数据中路线总数不超过 $2\,000\,000$。

输出仅包含一个整数，表示送礼物路线的总数。

### 样例解释 1 - - - - - - ### 样例解释 2  输入样例 $2$ 的全部 $6$ 种路线（数字表示送礼顺序）。 由 ChatGPT 4.1 翻译