#agc035f. [agc035_f]Two Histograms
[agc035_f]Two Histograms
Problem Statement
We have a square grid with rows and columns. Takahashi will write an integer in each of the squares, as follows:
- First, write in every square.
- For each , choose an integer , and add to each of the leftmost squares in the -th row.
- For each , choose an integer , and add to each of the topmost squares in the -th column.
Now we have a grid where each square contains , , or . Find the number of different grids that can be made this way, modulo . We consider two grids different when there exists a square with different integers.
Constraints
- and are integers.
Input
Input is given from Standard Input in the following format:
Output
Print the number of different grids that can be made, modulo .
Sample Input 1
1 2
Sample Output 1
8
Let denote the grid where the square to the left contains and the square to the right contains . Eight grids can be made: and .
Sample Input 2
2 3
Sample Output 2
234
Sample Input 3
10 7
Sample Output 3
995651918
Sample Input 4
314159 265358
Sample Output 4
70273732