問題一覧 > 通常問題

No.1111 コード進行

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 188
作問者 : trineutrontrineutron / テスター : ngtkanangtkana
5 ProblemId : 3498 / 出題時の順位表
問題文最終更新日: 2020-03-11 00:30:35

問題文

オリオン君は合唱曲を作曲することにした。コード進行が簡単すぎると退屈な曲になり、複雑すぎると理解不能な曲になってしまうため、適度に複雑なコード進行になるようにしたい。ここではコード進行を連続するコード2つとする。利用できるコードはコード$1$からコード$300$までの$300$種類あり、利用できるコード進行は$M$種類ある。$i (1 \le i \le M)$番目のコード進行はコード$P_i$の次にコード$Q_i (\ne P_i)$に進む進行で、その複雑度は$C_i$である。コード$N$個をつなげた曲のうち、複雑度の合計がちょうど$K$になる曲は何通りあるか。答えは非常に大きくなる可能性があるので、$10^9+7$で割った余りを求めよ。

入力

$N\ M\ K$
$P_1\ Q_1\ C_1$
$P_2\ Q_2\ C_2$
$\dots$
$P_M\ Q_M\ C_M$

入力は全て整数
$2 \le N \le 300$
$1 \le M \le 300$
$0 \le K \le 300$
$1 \le P_i, Q_i \le 300$
$P_i \ne Q_i$
$i \ne j$ならば$(P_i, Q_i) \ne (P_j, Q_j)$
$0 \le C_i \le 300$

出力

複雑度の合計がちょうど$K$になる曲が何通りあるか、$10^9+7$で割った余りを出力してください。最後に改行してください。

サンプル

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

1-2-3-2, 3-1-3-2, 1-3-2-3, 2-3-2-3, 3-2-3-1, 2-1-2-1の6通りあります。

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

そもそも曲を作ることができません。

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