問題文


列のグリッドがあり、はじめ 個全てのマスには が書き込まれています。

これに対して、あなたは以下の操作を 回以上、好きな回数行うことができます。

  • 任意の行、または列を1つ選ぶ。選んだ行(あるいは列)に含まれる全てのマスについて、そこに書き込まれている数字が 未満ならば を加算し、 に等しいなら何もしない。

最終的な盤面の状態として考えられるものの数を で割ったあまりを求めてください。 なお、2つの盤面の状態が異なるとは、あるマスが存在して、そのマスに書き込まれている数字が2つの盤面で異なることを言います。

制約


  • 入力は全て整数

入力


出力


答えを1行に出力してください。

入力例1


2 2 1

出力例1


10

例えば
01 11
11 00
のような盤面は作られる可能性がありますが、
01 01
10 00
のような盤面が作られることはありません。

入力例2


1 1 99999

出力例2


100000

盤面が同一であれば、操作方法は区別されません。

入力例3


314 159 265

出力例3


561547472

で出力してください。

Submit


Go (1.14)