Mirror Strings

Time limit1sMemory limit1024 MB

Summary

Count the mirror strings whose length is between L and R, where a mirror string looks the same flipped up-down or flipped left-right, modulo 10^9+7.

Level: Medium6 of 10
Topics: Dynamic programming, Combinatorics, Prefix sum
Solved: No attempts yet

Problem

A character is a "mirror character" if it looks the same when flipped up and down and when flipped left and right. The uppercase mirror characters are H, I, O, and X. The lowercase mirror characters are l (people often write it as a vertical line), o, and x.

In the same way, a string that looks the same when flipped up and down or when flipped left and right is a "mirror string". For example, XXOOOOXX is a mirror string.

The height of a character affects how a mirror string is built. For example, llll and oooo are both mirror strings. However, lool is not a mirror string because it looks different when flipped up and down. The uppercase characters H, I, O, X and the lowercase character l have height 2, while the lowercase letters x and o have height 1.

Tommy wants to build mirror strings from lowercase and uppercase characters. He wants to know how many different mirror strings have a length in the range $[L, R]$ , that is, how many mirror strings have a length $m$ with $L \leq m \leq R$ .

There are 7 mirror strings of length 1: H, I, O, X, l, o, and x. There are also 7 mirror strings of length 2: HH, II, OO, XX, ll, oo, and xx. Longer lengths have many more. For example, there are 29 mirror strings of length 3.

Input

The first and only line contains two integers $L$ and $R$ ( $1 \leq L \leq R \leq 10^6$ ), the range of mirror string lengths that Tommy wants to count.

Output

Print the number of mirror strings whose length $m$ satisfies $L \leq m \leq R$ , modulo $10^9 + 7$ .

Examples3

Example 1
Input
```
1 4
```
Expected output
```
72
```
Example 2
Input
```
2 3
```
Expected output
```
36
```
Example 3
Input
```
2 1000000
```
Expected output
```
664868576
```