[R51E]棋盘 - 代码源竞赛平台

时空限制

4S/512M

题目描述

apiadu 有一个 $n$ 行 $n$ 列的棋盘。棋盘上的每一个格子可以放至多一种棋子，棋子共有三种类型。由于每个格子有四种状态（空、第一种、第二种、第三种），因此整个棋盘共有 $4^{n \times n}$ 种放置棋子的方案。

每一种棋子的行走规则如下（所有移动均在棋盘范围内）：

• 第一种棋子：可以移动到同一行或同一列的任何空格，但在移动路线上不能跨过任何棋子。
• 第二种棋子：可以跳过同一行或同一列中恰好一个棋子，落在其后方的空格上。
• 第三种棋子：如果该棋子位于 $(x, y)$，它可以一步移动到 $(x-1, y-1)$，$(x-1, y+1)$，$(x+1, y-1)$ 或 $(x+1, y+1)$ 的空格。

apiadu 想知道，在所有 $4^{n \times n}$ 种方案中，有多少种方案满足：通过至多一步移动，可以使某个棋子到达指定的格子 $(x, y)$。

注：

1. “至多一步”包括：已经在 $(x, y)$ 处有一个棋子，或者存在一个棋子可以通过合法的移动规则一步到达 $(x, y)$。
2. 移动规则要求目标格子 $(x, y)$ 必须为空（除非棋子已经在该位置）。

格式

输入格式

第一行包含三个整数 $n, x, y$，分别表示棋盘的大小和目标格子的坐标。

输出格式

输出一个整数，表示满足条件的方案数对 $666666666$ 取模后的结果。

样例

样例输入 #1

3 2 1

样例输出 #1

250480

样例解释 #1

棋盘大小为 $3 \times 3$，目标点为 $(2, 1)$。在总共 $4^9 = 262144$ 种放置方案中，有 $250480$ 种方案满足至少有一个棋子可以在至多一步内到达或已经在 $(2, 1)$。

样例输入 #2

352446 171924 93544

样例输出 #2

145789174

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n\le$
$1$	$10$	$3$
$2$	$30$	$10000$
$3$	$30$	$10^7$
$4$	$30$	$2\times 10^8$

对于 $100\%$ 的数据，$3 \le n \le 2 \times 10^8$。