← 返回题目列表

AtCoder · codefestival_2015_final_g

G. 集邮活动

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

問題文

在Code节2015将举办sutampurari。在sutanpurari中,参加某个内容后,会得到对应内容的sutanpuo 1 张印章。

高桥君希望收集所有内容的印章。因此,高桥君设想了以下情况,对sutanpurari进行了预演练习。

  • 会场有 N 一个房间,以及2 个相连的房间 N-1 本条走廊构成。
  • 任何 2 两个房间之间,都可以通过走过一些走廊移动。
  • 内容有 N 种类,在房间 i (1 ≦ i ≦ N) 中的内容 i 正在进行中。

高桥君在这个预演操作中,按照以下类似伪代码的算法推进了sup塔拉里。需要注意的是,该算法保证在按下所有sup塔之前,一定会逐个按下 1 个后停止。

部屋 1 に入る
以下を繰り返す:
  今いる部屋のスタンプをまだ押してもらっていない場合:スタンプを押してもらう
  X = 今いる部屋からちょうど 1 本の通路を辿って移動できる部屋の集合
  X の中にまだ訪れていない部屋がある場合:
    そのうち最も番号が小さい部屋に移動する
  そうでない場合:
    今いる部屋が部屋 1 である場合:スタンプラリーを終了する
    そうでない場合:X のうち最も部屋 1 に近い部屋に移動する

高桥君被 i (1 ≦ i ≦ N) 按下的第几个sutanpumpu是内容 C_i 的su印章。此时,在预演中使用的会场结构可以考虑的情况有几种呢?会场的结构 N-1 假设用一组连接着的房间集合来表示。由于答案可能会是非常大的数,10^9+7 求余数。 在


入力

输入将以以下格式从标准输入提供。

N
C_1
C_2
:
C_N
  • 1 行上是整数 N (2 ≦ N ≦ 256) 。这意味着房间数量和内容数量都是 代表 N 。
  • 2 从线 N 行提供有关高桥收到的邮票顺序的信息。其中 给出 i (1 ≦ i ≦ N) 行上是整数 C_i (1 ≦ C_i ≦ N) 。这是i 您收到的印章就是内容 表明它是 C_i 邮票。然而, 当p \neq q 什么时候 C_p \neq C_q 有保证。

出力

可能的场馆结构数量 除以 10^9+7 (1,000,000,007) 后的余数 在 1 行输出。在输出末尾插入换行符。


入力例1

4
1
2
4
3

出力例1

3

如下图 3 以下结构是可能的。

figure1

入力例2

2
2
1

出力例2

0

入力例3

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

出力例3

348275800