eolymp
bolt
Try our new interface for solving problems
Problems

Aztec Treasure

Aztec Treasure

Time limit 1 second
Memory limit 128 MiB

During the recent excavations in Teotihuacan archeologists found a strange casket, the contents of which was probably used during the legendary corbans held by Montezuma, and a lot of equal rectangular bone pieces of size 1 × 2.

Archeologists found out that in order to open the casket you should tile the rectangular covering of this casket with bone pieces in a specific way. Pieces cannot overlap and intersect the border of the covering. Archeologists are afraid to break the casket, so they just want to try all possible ways of tiling. Your task is to calculate the number of such ways.

Input data

The only line contains two space-separated integers l and w, the length and the width of the casket's covering (1l, w100).

Output data

Output the number of ways of tiling modulo 10^9 + 7.

Examples

Input example #1
3 4
Output example #1
11
Author Igor Chevdar
Source 2009 Petrozavodsk Winter Session, Ural SU Contest, February 4, Problem B