AT_codefestival_2015_final_g スタンプラリー

[problemUrl]: https://atcoder.jp/contests/code-festival-2015-final-open/tasks/codefestival_2015_final_g 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 $ で割った余りを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ 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 $ 行に出力せよ。出力の末尾に改行を入れること。

### Sample Explanation 1 下図のような $ 3 $ 通りの構造が考えられます。 !\[figure1\](https://code-festival-2015-final.contest.atcoder.jp/img/other/code\_festival\_2015\_final/final/petapetapeta.png)