#agc035f. [agc035_f]Two Histograms
[agc035_f]Two Histograms
問題文
行 列のマス目があります。高橋君は、以下のようにして各マスに整数を書き込みます。
- まず、すべてのマスに を書き込む
- に対し、整数 を選び、上から 行目の左から 個のマスに書かれた整数すべてに を足す
- に対し、整数 を選び、左から 列目の上から 個のマスに書かれた整数すべてに を足す
こうして、各マスに のいずれかの整数の書かれたマス目が出来上がります。最終的にできる可能性のある相異なるマス目の個数を で割った余りを求めてください。 ただし、 つのマス目が異なるとは、あるマスが存在してそのマスに書かれた整数が異なることを指します。
制約
- は整数である
入力
入力は以下の形式で標準入力から与えられる。
出力
最終的にできる可能性のある相異なるマス目の個数を で割った余りを出力せよ。
入力例 1
1 2
出力例 1
8
左のマスに が、右のマスに が書き込まれたマス目を と表すことにすると、 の 通りのマス目ができる可能性があります。
入力例 2
2 3
出力例 2
234
入力例 3
10 7
出力例 3
995651918
入力例 4
314159 265358
出力例 4
70273732