Problem Description

Find the number of $h \times w$ matrices where each element is either $ 0 $ or $ 1 $, satisfying both of the following conditions, modulo integer $ M $.

• When interpreted as strings of length $ w $, the rows are sorted lexicographically.
• When interpreted as strings of length $ h $, the columns are sorted lexicographically.

Given integers $ H, W $, output the answer for all integer pairs $ h, w $ satisfying $1 \le h \le H$ and $1 \le w \le W$.

Input Format

Input is given from the standard input in the following format:

$H\ W\ M$

Output Format

Output $ H $ lines. The $ i $-th line ($1 \le i \le H$) should contain $ W $ integers separated by a single space. Specifically, the $ j $-th integer ($1 \le j \le W$) should be the answer for the case $ h = i, w = j $.

Sample Input and Output

Sample Input #1

2 3 5201314

Sample Output #1

2 3 4
3 7 14

Sample Input #2

10 8 1000000000

Sample Output #2

2 3 4 5 6 7 8 9
3 7 14 25 41 63 92 129
4 14 45 130 336 785 1682 3351
5 25 130 650 2942 11819 42305 136564
6 41 336 2942 24520 183010 1202234 6979061
7 63 785 11819 183010 2625117 33345183 371484319
8 92 1682 42305 1202234 33345183 836488618 470742266
9 129 3351 136564 6979061 371484319 470742266 230288201
10 175 6280 402910 36211867 651371519 194085968 670171373
11 231 11176 1099694 170079565 17940222 26957098 939510047

Sample Input #3

5 5 2

Sample Output #3

0 1 0 1 0
1 1 0 1 1
0 0 1 0 0
1 1 0 0 0
0 1 0 0 0

Notes/Hints

Data Range

• $1 \le H \le 21$
• $1 \le W \le 100$
• $2 \le M \le 10^9$

Sample Explanation 1

For $ (h, w) = (2, 3) $, there are $ 14 $ possible solutions.

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

见题面 Input 部分

见题面 Output 部分