P3223 [HNOI2012] Queue

A certain middle school has $n$ boys, $m$ girls, and two teachers who are to line up for a physical examination. They form a single straight line, and no two girls may stand adjacent, and the two teachers may not be adjacent either. How many different lineups are there? (Note: every individual is distinct.)

A single line containing two non-negative integers $n$ and $m$, separated by a space, as described above.

A single non-negative integer, denoting the number of different lineups. Note that the answer may be large.

For $30\%$ of the testdata, $n \leq 100$, $m \leq 100$. For $100\%$ of the testdata, $n \leq 2000$, $m \leq 2000$. Translated by ChatGPT 5