K Candy Description Alex has prepared n different candies. Before he distributes these candies to the children Alex would like to consider all his options. If there are m children in the school find out the number of ways Chef can distribute these n candies to m children. Since the number of ways to distribute cookies may be very large report the answer modulo 1e9+7. Input The first line of input consists of T, the number of test cases. The next T lines consist of 2 integers each, n and m. 1 <=T <= 10^5 1<=n,m<=1e9 Output Print T lines with the answer for each case on a new line. Sample Input 3 1 2 2 1 10 1 Sample Output 2 1 1
先简单介绍一下快速幂，举个例子。你要求n^m，你如何去写？
一个个乘？那么它的复杂度就是O（n）。有没有更快的方法呢？
我要求n^m，不妨先求n^(m/2)，这样我一平方，就得到了n^m。m越大省略的步骤越多，对不对？
既然这样，我们根据极限的思想，不断二分，然后利用递归，便可将复杂度缩小到O（lgn）。当然其中会有奇偶性的细节性问题，这里先只说一个大体思想。
上面是例题，等明天我详细写一下。
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------
long long function( long long n, long long m) { long long tmp = m % mod; long long ret = 1; while(n){ if(n&1) ret = ret*tmp%mod; tmp *= tmp; n >>= 1; } return ret; 具体函数的实现，很巧妙。想了很久没想出来。学习了。