ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ural SU contest. Petrozavodsk training camp. Winter 2006

About     Problems     Submit solution     Judge status     Standings
Contest is over

A. Archer's Travel

Time limit: 1.0 second
Memory limit: 64 MB
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 (1, 1) of an N × M chessboard (the upper right square of the board is coded as (N, M)). 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

Integers N and M separated with a space. 2 ≤ N ≤ 5; 2 ≤ M ≤ 109.

Output

You should output the number of ways to travel through the board calculated modulo 109.

Sample

inputoutput
2 3
2
Problem Author: Alexander Ipatov (prepared by Vladimir Yakovlev)
Problem Source: Ural SU Contest. Petrozavodsk Winter Session, January 2006
To submit the solution for this problem go to the Problem set: 1459. Archer's Travel