Time Limit: 2 seconds / Memory Limit: 256 MB
うさぎたちは，クリスマスコンテストに向けてプログラミング練習会を行うことになった．あるうさぎは，こんな問題を作った．
Colorful Christmas
問題
クリスマスツリーにカラフルな飾りつけをしよう．
お店には N 種類の飾りがある．それぞれの飾りには色がついている．同じ色の飾りは 2 個以上使わないことにして，最も多くの飾りを使いたい．このときの使う飾りの組み合わせは何通りあるかを求めたい．
入力
N C1 ... CN1 行目は整数 N を含む．
続く N 行のうち i 行目 (1 ≤ i ≤ N) は，i 番目の飾りの色を表す文字列 Ci を含む．
出力
求める組み合わせの総数を 1,000,000,009 で割った余りを 1 行に出力せよ．
制約
- 1 ≤ N ≤ 150．
- 1 ≤ (Ci の長さ) ≤ 10．
- Ci はアルファベット小文字からなる．
入出力例
入力例 1
7 red blue blue green blue red blue出力例 1
81 番目，2 番目，4 番目の飾りを選ぶことで，3 個の飾りを使うことができ，これが最大である．同じ色の飾りを 2 個以上選ばないように 3 個の飾りを選ぶ方法は 8 通りある．
せっかくなので，うさぎは好きな数が正解になるような入力データを作ることにした．しかし，果たしてそんなことができるのだろうか．
X
1 行目は整数 X を含む．
与えられた入力が，問題 "Colorful Christmas" の正しい出力となるような，問題 "Colorful Christmas" の入力を 1 つ作り出力せよ．
ただし，そのようなものが存在しない場合は NO と 1 行に出力せよ．
100 点中 25 点分のデータは以下を満たす．
8
7 red blue blue green blue red blue