Problem
Hari ini Moxxi berada dalam mood yang baik, jadi dia ingin mempelbagaikan muzik di barnya.
Kotak juke menyimpan n lagu, dan setiap satu daripadanya dicirikan oleh dua parameter: t
i dan g
i, di mana t_i — tempoh lagu dalam minit (1 ≤ t
i ≤ 15), g
i — genrenya (1 ≤ g
i ≤ 3).
Moxxi mahu membuat senarai main supaya jumlah tempohnya ialah tepat T minit. Kotak juke tidak pernah mengganggu lagu dan sentiasa memainkannya dari awal hingga akhir. Oleh itu, jika dia mula memainkan lagu ke-i, maka dia akan menghabiskan tepat t
i minit untuknya. Moxxi juga tidak suka apabila dua lagu daripada genre yang sama dimainkan secara berturut-turut atau apabila lagu diulang.
Bantu Moxxi mengira bilangan urutan lagu yang berbeza (urutannya penting), dengan jumlah tempoh tepat T, supaya tidak ada dua lagu berturut-turut daripada genre yang sama di dalamnya dan semua lagu dalam senarai main adalah berbeza.
Input:
Baris pertama input mengandungi dua integer n dan T (1 ≤ n ≤ 15, 1 ≤ T ≤ 225) — bilangan lagu dalam kotak juke dan jumlah tempoh yang diperlukan, masing-masing.
N baris seterusnya mengandungi perihalan lagu: baris ke-i mengandungi dua integer t
i dan g
i (1 ≤ t
i &le ; 15, 1 ≤g
i ≤ 3) — tempoh lagu ke-i dan genrenya, masing-masing.
Output:
Cetak satu integer — bilangan urutan lagu yang berbeza, dengan jumlah tempoh tepat T, supaya ia tidak mengandungi dua lagu berturut-turut daripada genre yang sama dan semua lagu dalam senarai main adalah berbeza. Oleh kerana jawapannya boleh besar, cetaknya modulo 10
9 + 7 (iaitu, bakinya apabila nombor dibahagikan dengan nombor 10
9 + 7).
Contoh:
| Input |
Output |
3 3
1 1
1 2
1 3
| 6 |
3 3
1 1
1 1
1 3
| 2 |
Penjelasan:
Dalam contoh pertama, Moxxi boleh mencipta mana-mana daripada 6 pilihan senarai main dengan menyusun semula lagu yang tersedia: [1,2,3], [1,3,2], [2,1,3], [2,3,1 ], [ 3,1,2] dan [3,2,1] (nombor lagu ditunjukkan).
Dalam contoh kedua, lagu pertama dan kedua tidak boleh berturut-turut (kerana ia mempunyai genre yang sama). Oleh itu, Moxxi boleh membuat senarai main dalam salah satu daripada 2 cara yang mungkin: [1,3,2] dan [2,3,1] (nombor lagu ditunjukkan).