azui大爷在quack大爷的带领下开始玩集合了，可是他太懒了，不想做quack大爷布置的作业题，便拿来给你做了：S 集合中有n个不同的元素，我们从1-n标号。考虑S 的子集Si,j，将这些子集排成一个r行c列矩阵的样子。其中第一行为S1,1,S1,2,…,S1,c，第二行为S2,1,S2,2,..,S2,c一直到第r行为Sr,1, Sr,2,…, Sr,c。这些集合还满足对于在一行中左右相邻的两个集右，左侧是右侧的子集，即Si,j∈Si,j+1。这些集合还满足对于在一列中上下相邻的两个集合，上方是下方的子集，即Si,j∈Si+1,j。问对于S 的全部子集，有多少可能的情况排成上述的矩阵（每个子集可以重复使用），结果模109 +7 输出。你一定知道这么简单的题目怎么做，快帮帮azui大爷吧。
【输入格式】
一行三个数n,r,c.
【输出格式】
一个数表示答案。
【样例输入】
1 2 2
【样例输出】
6
【样例解释】
1
2
3
4
如上图标号后，有：1是2和3的子集，1，2，3都是4的子集。 用0表示空集，1表示元素1，从左到右是1、2、3、4的话，有以下6种情况0000 0001 0011 0101 0111 1111
【数据范围】 对于10%的数据，r*c*n <= 16 对于20%的数据，r*c <= 16, n <= 100 对于另20%的数据，r=1, c<=1000000 对于另10%的数据，n=1
对于100%的数据，r, c <= 1000000, n <= 10^9
题解：线性求逆元:
i*A[i] ≡ 1 (mod p), 求i的逆元A[i]
A[i] ≡ i^(-1) (mod p) 令p=k*i+r ( r<i,1<i<p ) k*i+r≡0 (mod p) (k*i+r) * i^(−1)*r^(−1) ≡ 0 * i^(−1)*r^(−1) (mod p) k*r^(−1)+i^(−1) ≡ 0 (mod p) i^(−1) ≡ -k*r^(−1) (mod p)
i^(−1) ≡ -(p/i)*(p%i)^(−1) (mod p)
即：A[i]=-(p/i)*A[p%i];
#include<cstdio> typedef long long LL; const int Mod=1e9+7; LL n, r, c; LL Mul( LL a, LL b ) { LL res=0; for( int i=1; i<=b; i<<=1, a=(a<<1)%Mod ) if( b&i ) res=(res+a)%Mod; return res; } LL Ksm( LL b, LL p ) { LL res=1; while(p) { if( p&1 ) res=Mul( res, b ); b=Mul( b, b ); p>>=1; } return res; } LL Fac( LL w ) {//阶乘factorial LL res=1; for( LL i=2; i<=w; i++ ) res=res*i%Mod; return res; } LL Inv( LL w ) {//求逆元 if( w==1 ) return 1; return ( Mod-Mod/w*Inv( Mod%w )%Mod )%Mod;//(num+Mod)%Mod避免负数 } LL C( LL n, LL m ) {//C( c+r, r )%Mod return Fac(n) * Inv( Fac(m) )%Mod * Inv( Fac(n-m) )%Mod; /*C(n,m)%Mod == n! / (m!*(n-m)!) % Mod == n! * (m!)^(-1) * ((n-m)!)^(-1) % Mod == n! * Inv(m!) * Inv((n-m)!) % Mod*/ } int main() { scanf( "%I64d%I64d%I64d", &n, &r, &c ); printf( "%I64d\n", Ksm( C(r+c,r), n ) ); return 0; }
