nefu 628 Garden visiting

题目：给出一个n*m大的花园，求出从左上角到右下角的路径数目（路径单调）。

方法：路径数=c（m+n-2,m-1);别忘了最后对p取余。由于数据最大能达到10^5，使用杨辉三角记录的话会爆内存，所以只能换方法。

           由于c(x,y)=x!/(y!*(x-y)!)，这里我们可以将x!分解素因子，并保存记录下来，同样的方法记录后面两个，由于x!必然能够整除(y!*(x-y)!)，所以后面两个数有的因子，x!比然有，只需要将他们的因子的指数相加减，就能得到最后结果的素因子分解的情况，然后最后使用快速幂取模，就能得到最后的结果。

注意：如何进行素因子分解？

            首先要打表将所有的素因子求出来，这里有是将n！进行素因子分解，假设想要求出其中有多少个5，这里是有技巧的。

            假设n=200，那么因子5的个数=200/5+40/5+8/5=49，怎么得到的呢？200中5的倍数有40个，这40个数中其中是25的倍数的有8个，所以还能分解出8个5，这8个数中还有一个是125的倍数，还能分解出一个5，就这样一直循环下去，就能求出指数的值。

代码：