30分杨辉三角暴力求组合数
70分预处理阶乘，用逆元计算
100分打表，发现刚好是斐波那契数列，如果用线性递推仍是70分，用矩阵快速幂优化即可得100分

严格证明：
有杨辉三角递推式可得

从而可得