AT1202Contest_c binarydigit

[problemUrl]: https://atcoder.jp/contests/DEGwer2023/tasks/1202Contest_c 各要素が $ 0 $ または $ 1 $ の $ h\ \times\ w $ 行列であって以下の条件をともに満たすものの個数を整数 $ M $ で割った余りを求めてください． - 各行を長さ $ w $ の文字列として解釈したとき，行方向に辞書順でソートされている． - 各列を長さ $ h $ の文字列として解釈したとき，列方向に辞書順でソートされている． 入力で整数 $ H,\ W $ が与えられるので， $ 1\ \le\ h\ \le\ H $, $ 1\ \le\ w\ \le\ W $ を満たす全ての整数 $ h,\ w $ の組について答えてください．

入力は以下の形式で標準入力から与えられる． > $ H\ W\ M $

$ H $ 行出力せよ． 第 $ i $ 行 $ (1\ \le\ i\ \le\ H) $ には $ W $ 個の整数を半角空白区切りで出力せよ．特に $ j $ 番目の整数 $ (1\ \le\ j\ \le\ W) $ として $ h\ =\ i,\ w\ =\ j $ のときの本問の答えを出力せよ．

### 数据范围 - $ 1\ \le\ H\ \le\ 21 $ - $ 1\ \le\ W\ \le\ 100 $ - $ 2\ \le\ M\ \le\ 10^9 $ ### Sample Explanation 1 对于 $ (h,\ w)\ =\ (2,\ 3) $ 的 $ 14 $ 个方案。 ```plain 000 000 000 000 001 001 001 001 001 011 011 011 011 111 000 001 011 111 001 010 011 110 111 011 100 101 111 111 ```