問題一覧 > 通常問題

No.1112 冥界の音楽

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 131
作問者 : trineutrontrineutron / テスター : 37zigen37zigen
11 ProblemId : 3449 / 出題時の順位表
問題文最終更新日: 2019-12-07 23:32:18

問題文

冥界の音楽を司るオリオン君は冥界の住人のために$N$音からなる歌を作曲することになった。作曲には以下のような制約がある。

冥界の住人に聞こえる音は限られており、$1, 2, \dots, K$しかない。また、冥界の住人には同時に2つ以上の音が聞こえない。そのため、$i$番目の音を$T_i$とすると$1 \le T_i \le K$でなければならない。曲の始まりと終わりを示すため、最初と最後の音は$1$でなければならない。さらに、連続する3音の組み合わせのうち、冥界で許されるのは$M$種類だけである。具体的には、任意の連続する3音$T_i, T_{i+1}, T_{i+2}$に対し、$(T_i, T_{i+1}, T_{i+2}) = (P_j, Q_j, R_j)$となるような$j (1 \le j \le M)$が存在しなければならない。

上記の制約を満たす曲は何通りあるか求めよ。答えは非常に大きくなる可能性があるので、$10^9+7$で割った余りを出力せよ。

入力

$K\ M\ N$
$P_1\ Q_1\ R_1$
$P_2\ Q_2\ R_2$
$\dots$
$P_M\ Q_M\ R_M$

1行目に、使用できる音の種類$K$、許される進行の数$M$、音の数$N$がスペース区切りで与えられます。
その後$M$行、$P_i, Q_i, R_i$がスペース区切りで与えられます。

入力は全て整数
$1 \le K \le 6$
$1 \le M \le K^3$
$3 \le N \le 10^{18}$
$1 \le P_i, Q_i, R_i \le K$
$i \ne j$ならば$(P_i, Q_i, R_i) \ne (P_j, Q_j, R_j)$

出力

制約を満たす曲は何通りあるか、$10^9+7$で割った余りを出力してください。最後に改行してください。

サンプル

サンプル1
入力
5 8 7
1 5 1
1 4 1
5 1 5
5 1 4
4 1 4
4 1 5
1 4 5
4 5 1
出力
9

1-4-5-1-4-5-1、1-X-1-Y-1-Z-1 (X, Y, Zは4または5) の9通りあります。

サンプル2
入力
2 3 3
2 2 2
1 2 2
2 2 1
出力
0

条件を満たす曲はありません。

サンプル3
入力
1 1 16
1 1 1
出力
1

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。