Problem
今日、モクシーは機嫌が良いので、バーの音楽を多様化したいと考えています。
ジュークボックスには n 曲が保存されており、それぞれの曲は 2 つのパラメータ t
i と g
i によって特徴付けられます。曲の長さ (1 ≤ t
i — 1 ≤ t
i — 15)、g
i —ジャンル (1 ≤ g
i ≤ 3)。
Moxxi は、合計時間がちょうど T 分になるようなプレイリストを作成したいと考えています。ジュークボックスは曲を中断することはなく、常に曲を最初から最後まで再生します。したがって、i 番目の曲の演奏を開始すると、ちょうど t
i 分をそれに費やすことになります。 Moxxi は同じジャンルの曲が 2 つ続けて演奏されることや、曲が繰り返されることも好みません
。
Moxxi が、同じジャンルの連続した 2 曲が存在せず、プレイリスト内のすべての曲が異なるように、合計時間が正確に T になる、異なる曲のシーケンス (順序が重要です) の数を数えるのを手伝ってください。
入力:
入力の最初の行には、2 つの整数 n と T (1
です。
次の n 行には曲の説明が含まれます。i 番目の行には 2 つの整数 t
i と g
i (1 ≤ t
i &le) が含まれます。 ; 15, 1 ≤g
i ≤ 3) —それぞれ i 番目の曲の長さとジャンル。
出力:
単一の整数を出力します —同じジャンルの連続する 2 つの曲が含まれず、プレイリスト内のすべての曲が異なる、合計期間が正確に T である、異なる曲のシーケンスの数。答えは大きくなる可能性があるため、10
9 + 7 を法として出力します (つまり、数値を 10
9 + 7 で割った余り)。
例:
<本体>
| 入力 |
出力 |
3 3
1 1
1 2
1 3
| 6 |
3 3
1 1
1 1
1 3
| 2 |
説明:
最初の例では、Moxxi は利用可能な曲を並べ替えることで 6 つのプレイリスト オプションのいずれかを作成できます: [1,2,3]、[1,3,2]、[2,1,3]、[2,3,1] ]、[3,1,2]、[3,2,1]（曲番号表記）
2 番目の例では、1 番目の曲と 2 番目の曲を連続させることはできません (ジャンルが同じであるため)。したがって、Moxxi は、[1,3,2] および [2,3,1] (曲番号が示されています) の 2 つの方法のいずれかでプレイリストを作成できます。