beecrowd | 1584

Espertofone

By Leandro Zatesko, UFFS BR Brazil

Timelimit: 1

The UFFS (União Federal dos Fabricantes de Selulares[sic]), a company 100% brazilian company, of group MEC (Mercado da Espanção[sic] Comercial), has just launched Espertofone, to compete against imported smartphones. Espertofones run a proper operational system, called Androido. When a user turns an Espertofone with Androido on, appears a unlock screen with a grid of N × N buttons. The user is supposed to, then, without untouching the finger off the screen, slide it through the buttons in order to draw his previously recorded unlock pattern and, thus, unlock the phone to be used. The system always maintains on screen a line segment with one endpoint on the last button taken and the other under the user's finger, and considers that the user takes a button B if and only if this line segment intercepts the centre of B. Differently than what happens with the rival company, in Android the user can repeat buttons, as long as it is possible. The Figure ilustrates a unlock pattern with K = 8 segments in a 4 × 4 grid, enumerating the segments. Notice that, in a 4 × 4 grid, it is not possible that button (3, 3) follows button (1, 1) in a unlock pattern, because the segment would mandatorily pass through the centre of button (2, 2). Obviously, never is possible that a button follows itself. In this problem, consider that the finger's user is as thin as necessary to conect buttons that can theoretically follow each other

UFFS wants now to prove that its system is better than the rival's, calculating the number of unlock pattern with K segments.

Input

The input consists of several test cases, each one in a line and in turn consisted of two integers: N e K (2 ≤ N ≤ 5, 0 ≤ K ≤ 1015).

Output

Printf for each test case the number of possible unlock patterns with exactly K line segments, considering a grid N × N. As this number can be very large, print the remainder this number leaves when divided by 109 + 7.

Sample Input Sample Output

2 0
2 1
2 2
2 3

4
12
36
108