2017 Fall Waterloo Local ACM Contest, Problem D
Vera has a grid with rows and columns. Rows are numbered to and columns are numbered to . Let the cell in the -th row and -th column be . Cells are coloured white or black. A colouring is a pyramid if:
- Exactly cells are black.
- is black.
- If and are black, then is black for .
- If is black, then , if it exists, is black.
- If is black and there is no such that is black, then , if it exists, is white.
Two pyramids are different if there is a cell that is white in one pyramid and black in the other. Compute the number of different pyramids modulo .
Input
Line contains integers and .
Output
Print one line with one integer, the number of different pyramids modulo .
Sample Input 1
2 6
Sample Output 1
7
Sample Input 2
3 20
Sample Output 2
487
Note
For the first example, the seven pyramids are:
######
......
####..
.##...
####..
..##..
#####.
.#....
#####.
..#...
#####.
...#..
#####.
....#.
Comments