Каждой твари — по паре

Заметим, что нас не интересуют конкретные положения тварей на плоскости, а лишь знак их координаты. Пусть есть $$$X_+$$$ тварей-мальчиков с положительной $$$x$$$-координатой и $$$X_-$$$ тварей-мальчиков с отрицательной $$$x$$$-координатой. Аналогично, пусть есть $$$Y_+$$$ тварей-девочек с положительной $$$y$$$-координатой и $$$Y_-$$$ тварей-девочек с отрицательной $$$y$$$-координатой. Посчитаем эти значения в начале решения.

Переберем, сколько будет пар, в которых обе твари будут иметь положительную координату. Пусть это значение будет равняться $$$P_{++}$$$. Зная это значение, мы можем определить количество пар, в которых мальчик будет иметь положительную координату, а девочка — отрицательную. Несложно понять, что это количество $$$P_{+-} = X_+ - P_{++}$$$ (так как $$$P_{++} + P_{+-} = X_+$$$). Аналогично можно определить количество пар, в которых мальчик будет иметь отрицательную координату, а девочка — положительную $$$P_{-+} = Y_+ - P_{++}$$$ и количество пар, в которых обе твари будут иметь отрицательную координату $$$P_{--} = X_- - P_{-+}$$$.

Зная эти значения, мы можем вычислить количество разбиений на пары при таких значениях. Легко понять, что достаточно для каждой твари определить знак координаты твари, с которой она будет в паре. Таким образом, нам нужно из $$$X_+$$$ тварей с положительной $$$x$$$-координатой выбрать какие-то $$$P_{++}$$$, в паре с которыми будет тварь с положительной $$$y$$$-координатой. Чтобы сделать это есть $$$C_{X_+}^{P_{++}}$$$ вариантов, где $$$C_n^k$$$ — количество сочетаний из $$$n$$$ по $$$k$$$. Напомним, что число сочетаний может быть вычислено по формуле $$$C_n^k = \frac{n!}{k!(n-k)!}$$$. Аналогично, нам нужно из $$$X_-$$$ тварей с отрицательной $$$x$$$-координатой нужно выбрать какие-то $$$P_{-+}$$$, в паре с которыми будет тварь с положительной $$$y$$$-координатой. Для этого есть $$$C_{X_-}^{P_{-+}}$$$ вариантов. Аналогично, есть $$$C_{Y_+}^{P_{++}}$$$ и $$$C_{Y_-}^{P_{+-}}$$$ вариантов для тварей-девочек. Таким образом, чтобы получить ответ, переберем значение $$$P_{++}$$$, и если все значения $$$P_{+-}, P_{-+}, P_{--}$$$ получились неотрицательными, прибавим к ответу значение $$$C_{X_+}^{P_{++}} \cdot C_{X_-}^{P_{-+}} \cdot C_{Y_+}^{P_{++}} \cdot C_{Y_-}^{P_{+-}}$$$.

Чтобы быстро вычислять значения $$$C_n^k$$$, посчитаем в начале программы значения $$$n!$$$ и обратные к ним значения по нужному модулю, это позволит вычислять $$$C_n^k$$$ за время $$$\mathcal{O}(1)$$$. Для того, чтобы искать обратное по модулю число, можно использовать алгоритм быстрого возведения в степень, работающий за время $$$\mathcal{O}(\log M)$$$, где $$$M$$$ — модуль, по кторому производятся вычисления. Таким образом, асимптотика времени работы программы составит $$$\mathcal{O}(n \log M)$$$.