← 返回题目列表

AtCoder · arc138_f

F. KD 树

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

分数: 1000 点

问题陈述

有 N 点在平面上, i-th (1 \leq i \leq N) 其中是 (i,P_i)。 在这里, (P_1,P_2,\cdots,P_N) 是一个排列 (1,2,\cdots,N).

你可以 安排 非空集 点的 s ,这是一个递归操作,定义如下。

  • If s 恰好包含一个点,对其进行排列会创建一个仅由该点组成的序列。
  • If s 包含两个或多个点,通过执行以下两个操作之一对其进行排列可创建由这些点组成的序列。
    • 选择任意整数 x 并除以 s 一分为二:设置 a 的点 X- 坐标小于 x 和设置 b 其他要点。 在这里,既没有 a 也不 b 应为空。 通过连接排列获得的序列来创建序列 a 以及排列得到的序列 b 按此顺序。
    • 选择任意整数 y 并除以 s 一分为二:设置 a 的点 Y- 坐标小于 y 和设置 b 其他要点。 在这里,既没有 a 也不 b 应为空。 通过连接排列获得的序列来创建序列 a 以及排列得到的序列 b 按此顺序。

求模数 (10^9+7),可以通过排列点集获得的序列 \{(1,P_1),(2,P_2),\cdots,(N,P_N)\}.

约束

  • 1 \leq N \leq 30
  • (P_1,P_2,\cdots,P_N) 是一个排列 (1,2,\cdots,N).
  • 输入中的所有值都是整数。

输入

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

N
P_1 P_2 \cdots P_N

输出

打印答案。


示例输入 1

3
3 1 2

示例输出 1

3

可以获得以下三个序列。

  • ((1,3),(2,1),(3,2))
  • ((2,1),(3,2),(1,3))
  • ((2,1),(1,3),(3,2))

例如,序列 ((2,1),(1,3),(3,2)) 可以如下获得。

  • 安排集合 \{(1,3),(2,1),(3,2)\} 将其除以点集 Y- 坐标小于 2 (=\{(2,1)\})和其他点的集合(=\{(1,3),(3,2)\}).
    • 安排集合 \{(2,1)\} 获取序列 ((2,1)).
    • 安排集合 \{(1,3),(3,2)\} 将其除以点集 X- 坐标小于 3 和其他点的集合。
      • 安排集合 \{(1,3)\} 获取序列 ((1,3)).
      • 安排集合 \{(3,2)\} 获取序列 ((3,2)).
      • 连接所得的两个序列以获得序列 ((1,3),(3,2)).
    • 连接所得的两个序列以获得序列 ((2,1),(1,3),(3,2)).

示例输入 2

5
1 2 3 4 5

示例输出 2

1

示例输入 3

10
3 6 4 8 7 2 10 5 9 1

示例输出 3

1332

示例输入 4

30
7 11 8 26 4 13 28 5 14 1 16 27 10 2 23 25 17 6 3 18 24 15 9 22 21 29 12 20 19 30

示例输出 4

641915679