upd：修改一处笔误。

神仙 Kubic 的思路真的简洁而自然，我这种小蒟蒻也能看明白 qwq。

（Kubic 为什么这么强大？Kubic 为什么这么强大？Kubic 为什么这么强大？Kubic 为什么这么强大？Kubic 为什么这么强大？Kubic 为什么这么强大？Kubic 为什么这么强大？Kubic 为什么这么强大？Kubic 为什么这么强大？Kubic 为什么这么强大？Kubic 为什么这么强大？）

先将 $s,t$ 升序排序，定义 $a_i$ 表示最小的能和第 $i$ 头牛匹配的牛棚，$b_i$ 表示最小的能和第 $i$ 个牛棚匹配的牛。

假设最小的未被匹配的牛为 $p$，则「极大匹配」的充要条件为 $s_p\gt t_{a_p}$。

考虑枚举这个最小未被匹配的牛，设其编号为 $i$。

不难发现，$[a_i,n]$ 范围内的牛棚必须被匹配，否则 $i$ 一定可以和 $a_i$ 匹配。

$1\sim i-1$ 的牛必然能和 $[a_i,n]$ 内的牛棚匹配，$i+1\sim n$ 的牛则不一定。

考虑枚举 $1\sim i-1$ 匹配到 $[a_i,n]$ 内的牛棚的数量为 $j$，那么就需要 $1\sim i-1$ 未被匹配的牛全部与 $[1,a_i)$ 内的某个牛棚匹配（根据条件），$i+1\sim n$ 的某些牛和 $[a_i,n]$ 内未被匹配的 $n-a_i+1-j$ 个牛棚匹配。

这个问题并不难解决。设 $f_{i,j}$ 表示前 $i$ 个牛棚和 $j$ 头牛匹配的方案数，$g_{i,j}$ 表示后 $i$ 头牛和 $j$ 个牛棚匹配的方案数。

转移方程：$f_{i,j}=f_{i-1,j}+f_{i-1,j-1}\times \max\{0,b_i-j+1\},g_{i,j}=g_{i+1,j}+g_{i+1,j-1}\times \max\{n-a_i-j+2,0\}$。

则上述方案总数可以表示为 $g_{i+1,n-a_i+1-j}\times f_{a_i-1,i-j-1}\times j!$。

最后不要忘了加上 $f_{n,n}$，表示「完美匹配」的方案数。