P2289 [HNOI2004] Postman

Xiao Li works at the post office in city P. Every day, his job is to start from the post office, collect letters from all the mailboxes under his charge, and then return to the post office. The mailboxes he manages happen to form an $m \times n$ lattice of points (with equal spacing). The mailbox at the upper-left corner is exactly at the post office entrance. Xiao Li is a very unconventional person. He hopes to take a different route every day, but at the same time he does not want the route length to increase (that is, he chooses a shortest route; note that the route length is the physical distance he actually walks, and there is no restriction on how many times he passes each mailbox). He wants to know how many different routes he can take. Between any two mailboxes, he walks along a straight line. Write a program that takes the values of $m$ and $n$ for the lattice as input, and computes the total number of different routes Xiao Li can choose.

The input consists of a single line with two integers $m$, $n$, representing the size of the lattice of mailboxes under Xiao Li’s charge.

Output one line with a single integer, the number of different routes Xiao Li can choose.

#### Explanation for Sample Input/Output 1  --- #### Constraints - For $100\%$ of the testdata, it is guaranteed that $1 \le m \le 10$, $1 \le n \le 20$, and $n \times m$ is even. Translated by ChatGPT 5