Archer's Travel#3442

Archer's Travel

1 second
128 megabytes
Very easy

Let an archer be a chessman that can move one square forward, back, to the left, or to the right. An archer is situated at the square of an n \times m chessboard (the upper right square of the board is coded as ). The archer's goal is to travel through the board and return to the initial position in such a way that each square of the board is visited exactly once (the travel starts with the first move of the archer). It is required to determine the number of different ways to perform such a travel.

Input

Two positive integers and (2 \leq n \leq 5, 2 \leq m < 10^9).

Output

Print the number of ways to travel through the board calculated modulo 10^9.

Examples

Example 1

Loading
Loading