Problem
Heute ist Moxie in guter Stimmung, also will sie Musik in ihrer Bar anders machen.
Die Musikmaschine speichert n Songs mit jeweils zwei Parametern: t
I und g
Iwobei t_i die Länge des Songs in Minuten ist (1 ≤ t)
I ≤ 15, g
I - Ihr Genre.
I (3).
Moxie will eine Playlist machen, so dass seine Gesamtlänge genau T Minuten beträgt. Musikmaschine unterbricht nie Songs und reproduziert sie immer von Anfang bis Ende. Also, wenn er begann, das i-y-Song zu reproduzieren, wird er genau t damit verbringen.
I Minuten. Auch Moxie mag es nicht, zwei Songs des gleichen Genres in Folge zu spielen oder wenn Songs wiederholt werden.
Helfen Sie Moxie die Anzahl der verschiedenen Songsequenzen (die von Bedeutung sind), die Gesamtlänge von genau T, so dass es keine zwei aufeinander folgenden Songs des gleichen Genres und alle Songs in der Playlist sind unterschiedlich.
Eingabe:Die erste Zeile des Eintrags enthält zwei ganze Zahlen n und T (1 n ≤ 15, 1 ≤ T < 225) - die Anzahl der Songs in einer Musikmaschine und die erforderliche Gesamtlänge.
Als nächstes werden die Sandbeschreibungen in n Zeilen aufgezeichnet: i-I-I enthält zwei ganze Zahlen t
I und g
I (1 ≤ t)
I ≤ 15, 1 ≤ g
I (3) Die Länge des i- Liedes bzw. seines Genres.
Ausgangsdaten:Nehmen Sie eine ganze Zahl heraus, die Anzahl der verschiedenen Songsequenzen, die Gesamtlänge von T genau, so dass es keine zwei aufeinander folgenden Songs des gleichen Genres und alle Songs in der Playlist sind unterschiedlich. Da die Antwort groß sein kann, nehmen Sie es unter Modul 10.
ANHANG + 7 (d.h. der Rest der Zahl nach Zahl 10)
ANHANG + 7)
Beispiele:| Eingangsdaten | Ausgangsdaten |
3
1
Artikel 2
1 3 | 6 |
3
1
1
1 3 | 2 |
Beschreibung:Im ersten Beispiel kann Moxie eine der sechs Optionen für eine Wiedergabeliste erstellen, um bestehende Songs zu konvertieren: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2] und [3,2.1] (song numbers).
Im zweiten Beispiel können die ersten und zweiten Songs nicht kontrahiert werden (wie sie das gleiche Genre haben). So kann Moxie eine Playlist zu einer der beiden Möglichkeiten machen: [1,3.2] und [2,3,1] (die angegebenen Songnummern).