Module: Recursive enumeration

Problem

Today Moxxi is in a good mood, so she wants to diversify the music in her bar.
The jukebox stores n songs, and each of them is characterized by two parameters: t_i and g_i, where t_i — song duration in minutes (1 ≤ t_i ≤ 15), g_i — its genre (1 ≤ g_i ≤ 3).
Moxxi wants to make a playlist such that its total duration is exactly T minutes. The jukebox never interrupts songs and always plays them from beginning to end. Thus, if he starts playing the i-th song, then he will spend exactly t_i minutes on it. Moxxi also doesn't like it when two songs of the same genre are played in a row or when songs are repeated.
Help Moxxi count the number of different sequences of songs (their order matters), with a total duration of exactly T, such that there are no two consecutive songs of the same genre in them and all songs in the playlist are different.

Input:
The first line of the input contains two integers n and T (1 ≤ n ≤ 15, 1 ≤ T ≤ 225) — the number of songs in the jukebox and the required total duration, respectively.
Next n lines contain descriptions of the songs: the i-th line contains two integers t_i and g_i (1 ≤ t_i ≤ 15, 1 ≤g_i ≤ 3) — the duration of the i-th song and its genre, respectively.

Output:
Print a single integer — the number of different sequences of songs, with a total duration of exactly T, such that they do not contain two consecutive songs of the same genre and all songs in the playlist are different. Since the answer can be large, print it modulo 10⁹ + 7 (that is, the remainder when the number is divided by the number 10⁹ + 7).

Examples:
 

Input	Output
3 3 1 1 1 2 1 3	6
3 3 1 1 1 1 1 3	2

Explanations:
In the first example, Moxxi can create any of the 6 playlist options by rearranging the available songs: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [ 3,1,2] and [3,2,1] (song numbers are indicated).

In the second example, the first and second songs cannot be consecutive (because they have the same genre). Thus, Moxxi can make a playlist in one of 2 possible ways: [1,3,2] and [2,3,1] (song numbers are indicated).