Jaiden is in a sticky situation. His home-made time machine took him to ancient Egypt but then broke, and he'll need some help from the locals to get it up and running. The fact that he doesn't speak Egyptian isn't ideal, but he has a brilliant plan to communicate using the universal language of maths.

Inside his time machine, Jaiden has brought with him a lot of sticks!

Using these sticks, Jaiden would like to draw out some numbers in the style of a seven segment display.

Jaiden's sticks are all either the length of 1 segment, or the length of 2 segments. He can use these sticks to draw out some numbers. Jaiden only likes putting sticks of length 2 vertically, but can put sticks of length 1 either horizonally or vertically. Below are some examples of numbers he could make with 6 segments of length 1 (red), and 1 segment of length 2 (blue). Note that leading zeroes are allowed.

How many ways can Jaiden use all of the sticks to create a number in the style of a seven segment display? A unique way is defined as an arrangement where the sticks are not arranged identically. Two arrangements are considered identical if the meet ALL of the following conditions:

• They represent the same number, including leading zeroes if there are any
• All of the sticks with length of one segment occupy exact same segment position in both arrangements
• All of the sticks with length of two segments occupy exact same segment position in both arrangements

Below is an example of some arrangments which are considered unique.

Input

The first and only line consists of 2 integers ~n~ and ~m~ ~(0 \leq n, m \leq 10^5)~, the number of sticks of length 1, and the number of sticks of length 2 he has respectively.

It is guaranteed that ~n \times m \leq 10^5~.

Output

Output a single integer - the number of possible ways Jaiden can create a number in the style of a seven segment display using all of the sticks, modulus by ~10^9+7~.

Clarifications

The digits must be drawn with the sticks exactly as they appear in the first diagram. For example, you may not form the digit 1 by putting 2 sticks of length 1/1 stick of length 2 on the left side of the digit.

Examples

Input 1

2 2

Output 1

7

The below image shows all possible ways to create a number in the seven segment display using all of the sticks.