P15856 [Lanqiao Cup 2nd International Contest] Sightseeing

The sample provided in the official Lanqiao Cup statement for this problem is incorrect. The sample has been recalculated based on the correct interpretation.

Little E visits a city and finds that all roads run either east-west (called Streets) or north-south (called Avenues), dividing the city blocks into many square regions. The city has a total of $n$ Streets, numbered from $1$ to $n$ from south to north, and $m$ Avenues, numbered from $1$ to $m$ from east to west. These Streets and Avenues partition the city into many regions, and each region is adjacent to two Streets and two Avenues. Some regions are a whole block that pedestrians cannot enter. Some regions are split into $2 \times 2$ smaller blocks, and pedestrians can pass through the road in the very middle. The figure below shows an example with $3$ Streets and $4$ Avenues, forming $6$ regions in total. :::align{center}  ::: Little E is currently standing at Street $1$ and Avenue $1$. He plans to tour the city by walking to Street $n$ and Avenue $m$, and then walking back. Little E does not want to take detours or walk along any road segment more than once, so he wants both the outward trip and the return trip to follow shortest paths, and the combined route must not traverse the same road segment twice. There are many plans that satisfy Little E's requirements. Please tell Little E how many such plans there are in total.

The first line contains two integers $n, m$, representing the number of Streets and the number of Avenues. The next $n - 1$ lines each contain $m - 1$ integers, describing each region. If the corresponding integer is $0$, it means a whole region that pedestrians cannot enter. If the corresponding integer is $1$, it means a region split into $2 \times 2$ smaller blocks. To make it easy to match the map, the input from top to bottom corresponds to the map from north to south, and the input from left to right corresponds to the map from west to east. Therefore, from the input point of view, Little E is currently standing in the bottom-right corner. He needs to walk to the top-left corner and then return to the bottom-right corner.

Output one integer, the total number of plans. If there are too many plans, output the remainder of the number of plans modulo $1000$.

### Sample Explanation This corresponds to the example in the problem description. Note that the sample output in the original problem is $18$, which should be wrong, because it only counts the number of one-way shortest paths. ### Constraints For $20\%$ of the test cases, $1 \le n, m \le 5$. For $40\%$ of the test cases, $1 \le n, m \le 20$. For $60\%$ of the test cases, $1 \le n, m \le 100$. For $100\%$ of the test cases, $1 \le n, m \le 1000$. Translated by ChatGPT 5