This problem is an exercise of Robinson–Schensted correspondence.

For the explanation of Robinson–Schensted correspondence, please refer to the following article. (Translator’s note: the following article is in Japanese. International readers may refer to English Wikipedia.)

ヤング図形と競技プログラミング (“Young tableau and competitive programming”, by 箱星)

In the original problem, the lengths of a longest increasing sequence (LIS) and a longest decreasing sequence (LDS) are specified, and the length of \(P\) is \((AB-1)\), so the shape of the standard tableaux of \(P\) is unique.

Specifically, the shape is a rectangle with \(B\) horizontal rows and \(A\) vertical columns, with the bottom-right square removed. Let \((i,j)\) denote the square in the \(i\)-th row from the top and \(j\)-th column from the left, and \(t_{i,j}\) be the number written on square \((i,j)\). Currently we have squares \((1,1),\ldots,(1,A),(2,1),\ldots,(2,A),\ldots,(B,1),\ldots,(B,A-1)\). Also, \(t_{i,j}<t_{i+1,j}, t_{i,j}<t_{i,j+1}\) for all \(t_{i,j}<t_{i+1,j}, t_{i,j}<t_{i,j+1}\).

Consider the third constraints. Since the LIS and LDS never changes, appending \((n+0.5)\) to \(P\) yields a tableau of shape \(B\times A\). Denoting by \(t'_{i,j}\) the number written on square \((i,j)\) of the resulting tableau, we must have

• \(t'_{1,A}=n+0.5\),
• \(t'_{i+1,A}=t_{i,A}\ (1\leq i \leq B-1)\).

To satisfy them, it is necessary that the original \(t\) satisfies

• \(t_{i,A}> t_{i+1,A-1}\ (1\leq i \leq B-1)\).

Overall, it is sufficient to count the number of \(t\) such that:

• \(t\) contains every integer between \(0\) and \((AB-1)\),
• \(t_{i,j}<t_{i+1,j}\),
• \(t_{i,j}<t_{i,j+1}\), and
• \(t_{i+1,A-1}< t_{i,A}\).

Without the fourth condition, the answer can be easily found using the hook length formula, but the fourth is troublesome.

In our case, the constraints are small enough to allow us to perform a DP (Dynamic Programming), in which the values of \(t\) are filled for each \(1,2,\ldots,AB-1\) in order. There are only at most \(500000\) states, so it runs fast enough with appropriate implementation.