#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
Sample Output 1
Let denote the grid where the square to the left contains and the square to the right contains . Eight grids can be made: and .