Chess Pushing Game

All submissions for this problem are available.

Dave is playing a game with three pawns on a long board. The board can be seen as an (semi-)infinitely long sequence of grid squares numbered starting from 0 with width 3. Thus, the squares on the board can be referred to using (i,j) where i >= 0 and j = 0, 1 or 2. For this problem, the distance between two pawns is the distance along the first coordinate. For example, distance between pawns at (0,2) and (10,0) is 10.

The pawns are numbered 0, 1 and 2. Pawn j starts off at square (0, j) initially. In one move, a pawn can move one square to the right (increasing first coordinate, while second coordinate remains same). For example, a pawn can move from (4, 2) to (5,2). Another restriction is that if p < q, then pawn q can never be to the right(higher first coordinate) of pawn p. Yet another restriction is that at any point of time, pawns p and p+1 (for p=0 or p=1) should not be separated by a distance more than D.

At the end of K moves, all the pawns should end up at the same first coordinate. Dave wants to know how many ways there are to complete this game. Help him!

Input

The first and only line contains two integers D, K (0 ≤ D ≤ 7; 0 ≤ K ≤ 10⁹).

Output

Output an only integer which is the result calculated, by modulo of 1,000,000,007.

Example

Input:
1 3
Output:
1

Input:
2 6
Output:
5

---

Date:	2010-10-29
Time limit:	3s
Source limit:	50000B
Languages:	All except: TCL