← 返回题目列表

AtCoder · abc113_d

D. 阿弥陀寺数量

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

Amidakuji 是日本的一种传统彩票方法。

为了制作amidakuji,我们首先绘制 W 平行的垂直线,然后绘制连接它们的水平线。每条垂直线的长度为 H+1 [cm],水平线的端点必须位于 1, 2, 3, ..., or H 距离顶部垂直线 [cm]。

A 有效的amidakuji 是满足以下条件的amidakuji:

  • 没有两条水平线共享一个端点。
  • 每条水平线的两个端点必须处于相同高度。
  • 水平线必须连接相邻的垂直线。

求满足以下条件的有效阿德库吉数,取模 1\ 000\ 000\ 007:如果我们沿着最左边垂直线的顶部到底部的路径,当遇到水平线时始终遵循水平线,我们就会到达底部 K从左侧算起第 3 条垂直线。

例如,在下面的 amakuji 中,我们将到达左起第四条垂直线的底部。

约束

  • H 是介于 1 和 100 (含)。
  • W 是介于 1 和 8 (含)。
  • K 是介于 1 和 W (含)。

输入

输入由标准输入按以下格式给出:

H W K

输出

打印满足条件的amidakuji的数量,模 1\ 000\ 000\ 007.


示例输入 1

1 3 2

示例输出 1

1

只有以下一位amidakuji满足条件:


示例输入 2

1 3 1

示例输出 2

2

只有以下两个amidakuji满足条件:


示例输入 3

2 3 3

示例输出 3

1

只有以下一位amidakuji满足条件:


示例输入 4

2 3 1

示例输出 4

5

只有以下五位阿甘寺满足条件:


示例输入 5

7 1 1

示例输出 5

1

由于只有一条垂直线,因此我们无法绘制任何水平线。因此,满足条件的阿甘寺只有一种:没有横线的阿甘寺。


示例输入 6

15 8 5

示例输出 6

437760187

请务必打印答案模数 1\ 000\ 000\ 007.