题目内容

有一个由 $n \times n$ 个单元格构成的壁画，每个单元格可以涂上金色、银色或铜色中的一种，因此共有 $3^{n \times n}$ 种不同的涂色方案。

壁画的格点用 $(i,j)$ 表示，其中 $i$ 为从上到下的格线编号，$j$ 为从左到右的格线编号，编号从 $0$ 开始。一位画家从左上角的格点 $(0,0)$ 出发，每次可以沿着竖线向下移动一格到 $(i+1,j)$，或者沿着横线向右移动一格到 $(i,j+1)$，最终到达右下角的格点 $(n,n)$。画家走过的路径将壁画上的单元格分成两个区域：路径左下方的区域（由 $(0,0), (n,0), (n,n)$ 与路径围成）和右上方的区域（由 $(0,0), (0,n), (n,n)$ 与路径围成）。

如果一条路径满足：其左下方区域中不包含任何金色单元格，且右上方区域中不包含任何银色单元格，则称这条路径是「优美的」。若对于一种涂色方案，存在至少一条优美的路径，则称该涂色方案是「有效的」。