Bobby had a crazy day at school today. On the way back home, Bobby is accompanied by his oldest sister. Since she is a mathematics major in university, she poses a math question to Bobby about the sidewalk they are walking on. The sidewalk consists of an ~N~ by ~M~ grid consisting of blue, red, and yellow tiles, where ~N, M~ are positive integers. ~N~ represents the number of rows, while ~M~ represents the number of columns. Each of these tiles has dimensions of ~1 \times 1~. Bobby's sister notes that a blue tile is never horizontally adjacent to a red tile. In this case, two tiles are horizontally adjacent if they share their left or right border with one another. She asks Bobby to tell her the number of possible sidewalks satisfying these conditions.

Help Bobby find the number of ways to tile an ~N \times M~ sidewalk with blue, red, and yellow ~1 \times 1~ tiles such that a blue tile is never horizontally adjacent to a red tile. Note that a blue tile is allowed to be vertically adjacent to a red tile.

Constraints

~1 \le N \le 10^{12}~

~1 \le M \le 10^6~

Note: You will not be required to pass the sample cases to proceed to the subtasks.

Subtask 1 [10%]

~N = 1~

~1 \le M \le 10~

Subtask 2 [20%]

~1 \le N \le 5~

~1 \le M \le 10~

Subtask 3 [40%]

~1 \le N \le 10^6~

~1 \le M \le 10^6~

Subtask 4 [30%]

No additional constraints.

Input Specification

The first and only line contains two space-separated integers, ~N~ and ~M~.

Output Specification

Output will consist of a single integer: the number of possible sidewalks satisfying the given conditions, modulo ~10^9+7~ (i.e., find the remainder when the answer is divided by ~10^9+7~).

Sample Input 1

1 3

Sample Output 1

17

Explanation of Sample 1

The possible arrangements are: BBB, BBY, BYB, BYR, BYY, RRR, RRY, RYB, RYR, RYY, YBB, YBY, YRR, YRY, YYB, YYR, YYY.

Sample Input 2

2 4

Sample Output 2

1681