Description

This time, Xiao Keke wants to solve a problem related to Chinese chess. On an $n$ row by $m$ column board, place any number of cannons (possibly $0$) so that no cannon can attack another. How many placement methods are there? As you surely know, in Chinese chess the cannon’s attack rule is: one cannon attacks another if and only if they are in the same row or the same column, and there is exactly one piece between them. Come exercise your thinking with Xiao Keke!

Input Format

One line contains two integers $n, m$, separated by a space.

Output Format

Output the total number of valid placements. Since this number can be large, output the result modulo $9999973$.

1 3

7

Hint

Sample Explanation

Except for the configuration where all $3$ cells are filled with cannons, all other configurations are valid, so there are $2 \times 2 \times 2-1=7$ valid configurations.

Constraints

• For $30\%$ of the testdata, $n$ and $m$ do not exceed $6$.
• For $50\%$ of the testdata, at least one of $n$ and $m$ does not exceed $8$.
• For $100\%$ of the testdata, $1 \leq n, m \leq 100$.

Problem statement updated by: @syksykCCC.

Translated by ChatGPT 5