#P4831. Non-attacking Cannons on a Chinese Chessboard

    ID: 18075 Type: Default 1000ms 256MiB

Non-attacking Cannons on a Chinese Chessboard

Non-attacking Cannons on a Chinese Chessboard

Scarlet is trying to place (2n) cannons ((\text{炮})) on an (n \times m) Chinese chessboard such that no two cannons can attack each other. In Chinese chess the cannon attacks along a row or a column only if there is exactly one cannon placed between the attacker and the target. In other words, if two cannons are in the same row (or column) and there is exactly one cannon on some square between them in that row (or column), then these two cannons can attack one another. Otherwise, they are safe.

Since there are exactly (2n) cannons, note that every row must receive exactly two cannons. However, care must be taken in the columns: each column may receive one or two cannons only. (If a column were to receive three or more, then choosing the first and third cannon in the sorted order (by row) would result in exactly one cannon between them, and hence an attack.)

Your task is to calculate the number of valid arrangements of these cannons on the board abiding by the above rules.

All formulas above are in LaTeX format.

inputFormat

The input consists of two integers (n) and (m) (with (1 \le n, m \le 10)), representing the number of rows and columns respectively.

outputFormat

Output a single integer, which is the number of valid arrangements.

sample

1 2
1

</p>