問題文

Code Festival 2015 ではスタンプラリーが開催されます。スタンプラリーでは、あるコンテンツに参加するとそのコンテンツに対応するスタンプを 1 つ押してもらえます。

高橋君は全てのコンテンツのスタンプを集めたいと思っています。そこで高橋君は、以下のような状況を想定してスタンプラリーの予行演習を行いました。

• 会場は N 個の部屋と、2 つの部屋を繋ぐ N-1 本の通路からなる。
• どの 2 つの部屋の間も、いくつかの通路を辿ることで移動することができる。
• コンテンツは N 種類あり、部屋 i (1 ≦ i ≦ N) ではコンテンツ i が行なわれている。

高橋君はこの予行演習で、以下の疑似コードのようなアルゴリズムでスタンプラリーを進めました。なお、このアルゴリズムは必ず全てのスタンプを 1 つずつ押してもらった後に停止することが保証されています。

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

高橋君が i (1 ≦ i ≦ N) 番目に押してもらったスタンプはコンテンツ C_i のスタンプでした。このとき、予行演習で用いた会場の構造として考えられるものは何通りあるでしょうか？会場の構造は N-1 本の通路が繋いでいる部屋の組の集合で表されるものとします。なお、答えは非常に大きな数となることがあるため、10^9+7 で割った余りを求めてください。

入力例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