問題文
在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 以下结构是可能的。
入力例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