某中学有 n n n 名男同学， m m m 名女同学和两名老师要排队参加体检。他们排成一条直线，并且任意两名女同学不能相邻，两名老师也不能相邻，那么一共有多少种排法呢？（注意：任意两个人都是不同的）

只有一行且为用空格隔开的两个非负整数 n n n 和 m m m，其含义如上所述。

对于 30%的数据 n ≤ 100 , m ≤ 100 n\le 100,m\le 100 n≤100,m≤100

对于 100%的数据 n ≤ 2000 , m ≤ 2000 n\le 2000,m\le 2000 n≤2000,m≤2000

输出文件 output.txt 仅包含一个非负整数，表示不同的排法个数。注意答案可能很大。

直接一起搞好像有点麻烦， 考虑先把男生放好，有 n ! n! n!种放的方法， 然后向里面插入老师， 显然有 ( n + 1 ) 2 ‾ (n+1)^{\underline{2}} (n+1)2​种方案。然后再插入女生， 现在就有 m ! × ( n + 3 m ) m!\times \binom{n+3}{m} m!×(mn+3​)种方案了。

但是这样并没有考虑女生夹在两个老师之间的情况， 因此我们可以直接把两个老师和一个女生打包算在一起， 这种打包的方式就有 2 × m 2\times m 2×m种。然后考虑插男生， 有 n + 1 n+1 n+1种方式。最后剩下的 m − 1 m-1 m−1个女生再插入队列， 有 ( m − 1 ) ! × ( n + 2 m − 1 ) (m-1)!\times \binom{n+2}{m-1} (m−1)!×(m−1n+2​)种方法。

那么答案就是 n ! × ( ( ( n + 1 ) × n × m ! × ( n + 3 m ) ) + ( 2 × m × ( n + 1 ) × ( m − 1 ) ! × ( n + 2 m − 1 ) ) ) n!\times(((n+1)\times n\times m!\times\binom{n+3}{m})+(2\times m\times (n+1)\times (m-1)!\times \binom{n+2}{m-1})) n!×(((n+1)×n×m!×(mn+3​))+(2×m×(n+1)×(m−1)!×(m−1n+2​)))。

套一个高精板子就好了。

代码如下：