Problem
Bugün Moxxi'nin keyfi yerinde, bu yüzden barındaki müziği çeşitlendirmek istiyor.
Müzik kutusu n şarkıyı depolar ve her biri iki parametre ile karakterize edilir: t
i ve g
i, burada t_i — dakika cinsinden şarkı süresi (1 ≤ t
i ≤ 15), g
i — türü (1 ≤ g
i ≤ 3).
Moxxi, toplam süresi tam olarak T dakika olacak şekilde bir oynatma listesi oluşturmak istiyor. Müzik kutusu şarkıları asla kesintiye uğratmaz ve her zaman baştan sona çalar. Böylece, i'inci şarkıyı çalmaya başlarsa, o zaman tam olarak t
i dakikayı ona harcayacaktır. Moxxi aynı türden iki şarkının art arda çalınmasından veya şarkıların tekrarlanmasından da hoşlanmaz.
Moxxi'nin, içlerinde aynı türden iki ardışık şarkı olmayacak ve çalma listesindeki tüm şarkılar farklı olacak şekilde toplam süreleri tam olarak T olan farklı şarkı dizilerinin sayısını saymasına yardımcı olun (sıraları önemlidir).
Giriş:
Girişin ilk satırı iki tam sayı n ve T içerir (1 ≤ n ≤ 15, 1 ≤ T ≤ 225) — müzik kutusundaki şarkı sayısı ve gereken toplam süre.
Sonraki n satır, şarkıların açıklamalarını içerir: i'inci satır iki tamsayı içerir: t
i ve g
i (1 ≤ t
i &le 15, 1 ≤g
i ≤3) — sırasıyla i. şarkının süresi ve türü.
Çıktı:
Tek bir tamsayı yazdır — toplam süresi tam olarak T olan, aynı türden iki ardışık şarkıyı içermeyecek ve çalma listesindeki tüm şarkılar farklı olacak şekilde farklı şarkı dizilerinin sayısı. Cevap büyük olabileceğinden modulo 10
9 + 7 olarak yazdırın (yani, sayının 10
9 + 7 ile bölümünden kalan kısım).
Örnekler:
| Giriş |
Çıktı |
3 3
1 1
1 2
1 3
| 6 |
3 3
1 1
1 1
1 3
| 2 |
Açıklamalar:
İlk örnekte Moxxi, mevcut şarkıları yeniden düzenleyerek 6 çalma listesi seçeneğinden herhangi birini oluşturabilir: [1,2,3], [1,3,2], [2,1,3], [2,3,1 ], [ 3,1,2] ve [3,2,1] (şarkı numaraları belirtilmiştir).
İkinci örnekte, birinci ve ikinci şarkı ardışık olamaz (çünkü aynı türe sahipler). Böylece Moxxi, 2 olası yoldan biriyle bir çalma listesi oluşturabilir: [1,3,2] ve [2,3,1] (şarkı numaraları belirtilir).