分数: 900 点
问题陈述
你正在开发青蛙形状的机器人,并决定让它们互相比赛。
首先,您放置了 N 机器人到数轴上。 这些机器人都有编号 1 通过 N。 机器人当前坐标 i is x_i。 在这里,所有 x_i 是整数,并且 0 < x_1 < x_2 < ... < x_N.
您将重复执行以下操作:
- 在数轴上选择一个机器人。设机器人的坐标为 x。选择目标坐标 x-1 or x-2,未被其他机器人占用。机器人现在跳转到选定的坐标。
当机器人的坐标变为 0 或更少,机器人被认为已完成并将立即从数轴上删除。 您将重复该操作,直到所有机器人完成比赛。
根据您在操作中的选择, N 机器人可以以不同的顺序完成比赛。 可以有多少种不同的顺序 N 机器人完成比赛? 求出模数的答案 10^9+7.
约束
- 2 ≤ N ≤ 10^5
- x_i 是一个整数。
- 0 < x_1 < x_2 < ... < x_N ≤ 10^9
部分分数
- 在测试集中值得 500 点, N ≤ 8.
输入
输入由标准输入按以下格式给出:
N x_1 x_2 ... x_N
输出
打印不同订单的数量 N 机器人可以完成比赛,模数 10^9+7.
示例输入 1
3 1 2 3
示例输出 1
4
三个机器人可以按照四种不同的顺序完成比赛:
- (机器人 1 → 机器人 2 → 机器人 3)
- (机器人 1 → 机器人 3 → 机器人 2)
- (机器人 2 → 机器人 1 → 机器人 3)
- (机器人 2 → 机器人 3 → 机器人 1)
示例输入 2
3 2 3 4
示例输出 2
6
三个机器人可以按照六种不同的顺序完成比赛:
- (机器人 1 → 机器人 2 → 机器人 3)
- (机器人 1 → 机器人 3 → 机器人 2)
- (机器人 2 → 机器人 1 → 机器人 3)
- (机器人 2 → 机器人 3 → 机器人 1)
- (机器人 3 → 机器人 1 → 机器人 2)
- (机器人 3 → 机器人 2 → 机器人 1)
例如,订单 (机器人 3 → 机器人 2 → 机器人 1) 可以实现如下图所示:
示例输入 3
8 1 2 3 5 7 11 13 17
示例输出 3
10080
示例输入 4
13 4 6 8 9 10 12 14 15 16 18 20 21 22
示例输出 4
311014372
记得打印答案模数 10^9+7。 这种情况不包含在部分分数的测试集中。