Artifact b6522f93bcade2955df5e2c79c3b76a3d5365402:
0000: 0a 2f 2f 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d .//-------------
0010: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0020: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0030: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0040: 0a 2f 2f 20 4d 6f 64 75 6c 6f 20 41 72 69 74 68 .// Modulo Arith
0050: 6d 65 74 69 63 73 0a 2f 2f 0a 2f 2f 20 56 65 72 metics.//.// Ver
0060: 69 66 69 65 64 20 62 79 0a 2f 2f 20 20 20 2d 20 ified by.// -
0070: 54 43 4f 31 30 20 52 33 20 4c 56 33 0a 2f 2f 20 TCO10 R3 LV3.//
0080: 20 20 2d 20 53 52 4d 20 35 34 35 20 4c 56 32 0a - SRM 545 LV2.
0090: 2f 2f 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d //--------------
00a0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
00b0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
00c0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a ---------------.
00d0: 0a 73 74 61 74 69 63 20 63 6f 6e 73 74 20 75 6e .static const un
00e0: 73 69 67 6e 65 64 20 4d 4f 44 56 41 4c 20 3d 20 signed MODVAL =
00f0: 31 30 30 30 30 30 30 30 30 37 3b 0a 73 74 72 75 1000000007;.stru
0100: 63 74 20 6d 69 6e 74 0a 7b 0a 09 75 6e 73 69 67 ct mint.{..unsig
0110: 6e 65 64 20 76 61 6c 3b 0a 09 6d 69 6e 74 28 29 ned val;..mint()
0120: 3a 76 61 6c 28 30 29 7b 7d 0a 09 6d 69 6e 74 28 :val(0){}..mint(
0130: 69 6e 74 20 20 20 20 20 20 78 29 3a 76 61 6c 28 int x):val(
0140: 78 25 4d 4f 44 56 41 4c 29 20 7b 7d 0a 09 6d 69 x%MODVAL) {}..mi
0150: 6e 74 28 75 6e 73 69 67 6e 65 64 20 78 29 3a 76 nt(unsigned x):v
0160: 61 6c 28 78 25 4d 4f 44 56 41 4c 29 20 7b 7d 0a al(x%MODVAL) {}.
0170: 09 6d 69 6e 74 28 4c 4c 20 20 20 20 20 20 20 78 .mint(LL x
0180: 29 3a 76 61 6c 28 78 25 4d 4f 44 56 41 4c 29 20 ):val(x%MODVAL)
0190: 7b 7d 0a 7d 3b 0a 6d 69 6e 74 26 20 6f 70 65 72 {}.};.mint& oper
01a0: 61 74 6f 72 2b 3d 28 6d 69 6e 74 26 20 78 2c 20 ator+=(mint& x,
01b0: 6d 69 6e 74 20 79 29 20 7b 20 72 65 74 75 72 6e mint y) { return
01c0: 20 78 20 3d 20 78 2e 76 61 6c 2b 79 2e 76 61 6c x = x.val+y.val
01d0: 3b 20 7d 0a 6d 69 6e 74 26 20 6f 70 65 72 61 74 ; }.mint& operat
01e0: 6f 72 2d 3d 28 6d 69 6e 74 26 20 78 2c 20 6d 69 or-=(mint& x, mi
01f0: 6e 74 20 79 29 20 7b 20 72 65 74 75 72 6e 20 78 nt y) { return x
0200: 20 3d 20 78 2e 76 61 6c 2d 79 2e 76 61 6c 2b 4d = x.val-y.val+M
0210: 4f 44 56 41 4c 3b 20 7d 0a 6d 69 6e 74 26 20 6f ODVAL; }.mint& o
0220: 70 65 72 61 74 6f 72 2a 3d 28 6d 69 6e 74 26 20 perator*=(mint&
0230: 78 2c 20 6d 69 6e 74 20 79 29 20 7b 20 72 65 74 x, mint y) { ret
0240: 75 72 6e 20 78 20 3d 20 4c 4c 28 78 2e 76 61 6c urn x = LL(x.val
0250: 29 2a 79 2e 76 61 6c 3b 20 7d 0a 6d 69 6e 74 20 )*y.val; }.mint
0260: 6f 70 65 72 61 74 6f 72 2b 28 6d 69 6e 74 20 78 operator+(mint x
0270: 2c 20 6d 69 6e 74 20 79 29 20 7b 20 72 65 74 75 , mint y) { retu
0280: 72 6e 20 78 2b 3d 79 3b 20 7d 0a 6d 69 6e 74 20 rn x+=y; }.mint
0290: 6f 70 65 72 61 74 6f 72 2d 28 6d 69 6e 74 20 78 operator-(mint x
02a0: 2c 20 6d 69 6e 74 20 79 29 20 7b 20 72 65 74 75 , mint y) { retu
02b0: 72 6e 20 78 2d 3d 79 3b 20 7d 0a 6d 69 6e 74 20 rn x-=y; }.mint
02c0: 6f 70 65 72 61 74 6f 72 2a 28 6d 69 6e 74 20 78 operator*(mint x
02d0: 2c 20 6d 69 6e 74 20 79 29 20 7b 20 72 65 74 75 , mint y) { retu
02e0: 72 6e 20 78 2a 3d 79 3b 20 7d 0a 0a 6d 69 6e 74 rn x*=y; }..mint
02f0: 20 50 4f 57 28 6d 69 6e 74 20 78 2c 20 4c 4c 20 POW(mint x, LL
0300: 65 29 20 7b 20 6d 69 6e 74 20 76 3d 31 3b 20 66 e) { mint v=1; f
0310: 6f 72 28 3b 65 3b 78 2a 3d 78 2c 65 3e 3e 3d 31 or(;e;x*=x,e>>=1
0320: 29 20 69 66 28 65 26 31 29 20 76 2a 3d 78 3b 20 ) if(e&1) v*=x;
0330: 72 65 74 75 72 6e 20 76 3b 20 7d 0a 6d 69 6e 74 return v; }.mint
0340: 26 20 6f 70 65 72 61 74 6f 72 2f 3d 28 6d 69 6e & operator/=(min
0350: 74 26 20 78 2c 20 6d 69 6e 74 20 79 29 20 7b 20 t& x, mint y) {
0360: 72 65 74 75 72 6e 20 78 20 2a 3d 20 50 4f 57 28 return x *= POW(
0370: 79 2c 20 4d 4f 44 56 41 4c 2d 32 29 3b 20 7d 0a y, MODVAL-2); }.
0380: 6d 69 6e 74 20 6f 70 65 72 61 74 6f 72 2f 28 6d mint operator/(m
0390: 69 6e 74 20 78 2c 20 6d 69 6e 74 20 79 29 20 7b int x, mint y) {
03a0: 20 72 65 74 75 72 6e 20 78 2f 3d 79 3b 20 7d 0a return x/=y; }.
03b0: 0a 2f 2f 20 6e 43 6b 20 3a 3a 20 4f 28 6c 6f 67 .// nCk :: O(log
03c0: 20 4d 4f 44 56 41 4c 29 20 74 69 6d 65 2c 20 4f MODVAL) time, O
03d0: 28 6e 29 20 73 70 61 63 65 2e 0a 76 65 63 74 6f (n) space..vecto
03e0: 72 3c 6d 69 6e 74 3e 20 46 41 43 5f 28 31 2c 31 r<mint> FAC_(1,1
03f0: 29 3b 0a 6d 69 6e 74 20 46 41 43 28 4c 4c 20 6e );.mint FAC(LL n
0400: 29 20 7b 20 77 68 69 6c 65 28 20 46 41 43 5f 2e ) { while( FAC_.
0410: 73 69 7a 65 28 29 3c 3d 6e 20 29 20 46 41 43 5f size()<=n ) FAC_
0420: 2e 70 75 73 68 5f 62 61 63 6b 28 20 46 41 43 5f .push_back( FAC_
0430: 2e 62 61 63 6b 28 29 2a 46 41 43 5f 2e 73 69 7a .back()*FAC_.siz
0440: 65 28 29 20 29 3b 20 72 65 74 75 72 6e 20 46 41 e() ); return FA
0450: 43 5f 5b 6e 5d 3b 20 7d 0a 6d 69 6e 74 20 43 28 C_[n]; }.mint C(
0460: 4c 4c 20 6e 2c 20 4c 4c 20 6b 29 20 7b 20 72 65 LL n, LL k) { re
0470: 74 75 72 6e 20 6b 3c 30 20 7c 7c 20 6e 3c 6b 20 turn k<0 || n<k
0480: 3f 20 30 20 3a 20 46 41 43 28 6e 29 20 2f 20 28 ? 0 : FAC(n) / (
0490: 46 41 43 28 6b 29 20 2a 20 46 41 43 28 6e 2d 6b FAC(k) * FAC(n-k
04a0: 29 29 3b 20 7d 0a 0a 2f 2f 20 6e 43 6b 20 3a 3a )); }..// nCk ::
04b0: 20 4f 28 31 29 20 74 69 6d 65 2c 20 4f 28 6e 5e O(1) time, O(n^
04c0: 32 29 20 73 70 61 63 65 2e 0a 76 65 63 74 6f 72 2) space..vector
04d0: 3c 20 76 65 63 74 6f 72 3c 6d 69 6e 74 3e 20 3e < vector<mint> >
04e0: 20 43 50 5f 3b 0a 6d 69 6e 74 20 43 28 4c 4c 20 CP_;.mint C(LL
04f0: 6e 2c 20 4c 4c 20 6b 29 20 7b 0a 09 77 68 69 6c n, LL k) {..whil
0500: 65 28 20 43 50 5f 2e 73 69 7a 65 28 29 20 3c 3d e( CP_.size() <=
0510: 20 6e 20 29 20 7b 0a 09 09 69 6e 74 20 6e 6e 20 n ) {...int nn
0520: 3d 20 43 50 5f 2e 73 69 7a 65 28 29 3b 0a 09 09 = CP_.size();...
0530: 43 50 5f 2e 70 75 73 68 5f 62 61 63 6b 28 76 65 CP_.push_back(ve
0540: 63 74 6f 72 3c 6d 69 6e 74 3e 28 6e 6e 2b 31 2c ctor<mint>(nn+1,
0550: 31 29 29 3b 0a 09 09 66 6f 72 28 69 6e 74 20 6b 1));...for(int k
0560: 6b 3d 31 3b 20 6b 6b 3c 6e 6e 3b 20 2b 2b 6b 6b k=1; kk<nn; ++kk
0570: 29 0a 09 09 09 43 50 5f 5b 6e 6e 5d 5b 6b 6b 5d )....CP_[nn][kk]
0580: 20 3d 20 43 50 5f 5b 6e 6e 2d 31 5d 5b 6b 6b 2d = CP_[nn-1][kk-
0590: 31 5d 20 2b 20 43 50 5f 5b 6e 6e 2d 31 5d 5b 6b 1] + CP_[nn-1][k
05a0: 6b 5d 3b 0a 09 7d 0a 09 72 65 74 75 72 6e 20 6b k];..}..return k
05b0: 3c 30 20 7c 7c 20 6e 3c 6b 20 3f 20 30 20 3a 20 <0 || n<k ? 0 :
05c0: 43 50 5f 5b 6e 5d 5b 6b 5d 3b 0a 7d 0a 0a 74 65 CP_[n][k];.}..te
05d0: 6d 70 6c 61 74 65 3c 74 79 70 65 6e 61 6d 65 20 mplate<typename
05e0: 54 3e 0a 76 65 63 74 6f 72 3c 54 3e 20 4d 41 54 T>.vector<T> MAT
05f0: 4d 55 4c 28 63 6f 6e 73 74 20 76 65 63 74 6f 72 MUL(const vector
0600: 3c 20 76 65 63 74 6f 72 3c 54 3e 20 3e 26 20 61 < vector<T> >& a
0610: 2c 20 63 6f 6e 73 74 20 76 65 63 74 6f 72 3c 54 , const vector<T
0620: 3e 26 20 76 29 0a 7b 0a 09 69 6e 74 20 4e 20 3d >& v).{..int N =
0630: 20 61 2e 73 69 7a 65 28 29 3b 0a 09 76 65 63 74 a.size();..vect
0640: 6f 72 3c 54 3e 20 75 28 4e 29 3b 0a 09 66 6f 72 or<T> u(N);..for
0650: 28 69 6e 74 20 69 3d 30 3b 20 69 3c 4e 3b 20 2b (int i=0; i<N; +
0660: 2b 69 29 0a 09 66 6f 72 28 69 6e 74 20 6a 3d 30 +i)..for(int j=0
0670: 3b 20 6a 3c 4e 3b 20 2b 2b 6a 29 0a 09 09 75 5b ; j<N; ++j)...u[
0680: 69 5d 20 2b 3d 20 61 5b 69 5d 5b 6a 5d 2a 76 5b i] += a[i][j]*v[
0690: 6a 5d 3b 0a 09 72 65 74 75 72 6e 20 75 3b 0a 7d j];..return u;.}
06a0: 0a 0a 74 65 6d 70 6c 61 74 65 3c 74 79 70 65 6e ..template<typen
06b0: 61 6d 65 20 54 3e 0a 76 65 63 74 6f 72 3c 20 76 ame T>.vector< v
06c0: 65 63 74 6f 72 3c 54 3e 20 3e 20 4d 41 54 4d 55 ector<T> > MATMU
06d0: 4c 28 63 6f 6e 73 74 20 76 65 63 74 6f 72 3c 20 L(const vector<
06e0: 76 65 63 74 6f 72 3c 54 3e 20 3e 26 20 61 2c 20 vector<T> >& a,
06f0: 63 6f 6e 73 74 20 76 65 63 74 6f 72 3c 20 76 65 const vector< ve
0700: 63 74 6f 72 3c 54 3e 20 3e 26 20 62 29 0a 7b 0a ctor<T> >& b).{.
0710: 09 69 6e 74 20 4e 20 3d 20 61 2e 73 69 7a 65 28 .int N = a.size(
0720: 29 3b 0a 09 76 65 63 74 6f 72 3c 20 76 65 63 74 );..vector< vect
0730: 6f 72 3c 54 3e 20 3e 20 63 28 4e 2c 20 76 65 63 or<T> > c(N, vec
0740: 74 6f 72 3c 54 3e 28 4e 29 29 3b 0a 09 66 6f 72 tor<T>(N));..for
0750: 28 69 6e 74 20 69 3d 30 3b 20 69 3c 4e 3b 20 2b (int i=0; i<N; +
0760: 2b 69 29 0a 09 66 6f 72 28 69 6e 74 20 6a 3d 30 +i)..for(int j=0
0770: 3b 20 6a 3c 4e 3b 20 2b 2b 6a 29 0a 09 66 6f 72 ; j<N; ++j)..for
0780: 28 69 6e 74 20 6b 3d 30 3b 20 6b 3c 4e 3b 20 2b (int k=0; k<N; +
0790: 2b 6b 29 0a 09 09 63 5b 69 5d 5b 6a 5d 20 2b 3d +k)...c[i][j] +=
07a0: 20 61 5b 69 5d 5b 6b 5d 2a 62 5b 6b 5d 5b 6a 5d a[i][k]*b[k][j]
07b0: 3b 0a 09 72 65 74 75 72 6e 20 63 3b 0a 7d 0a 0a ;..return c;.}..
07c0: 74 65 6d 70 6c 61 74 65 3c 74 79 70 65 6e 61 6d template<typenam
07d0: 65 20 54 3e 0a 76 65 63 74 6f 72 3c 20 76 65 63 e T>.vector< vec
07e0: 74 6f 72 3c 54 3e 20 3e 20 4d 41 54 50 4f 57 28 tor<T> > MATPOW(
07f0: 76 65 63 74 6f 72 3c 20 76 65 63 74 6f 72 3c 54 vector< vector<T
0800: 3e 20 3e 20 61 2c 20 4c 4c 20 65 29 0a 7b 0a 09 > > a, LL e).{..
0810: 69 6e 74 20 4e 20 3d 20 61 2e 73 69 7a 65 28 29 int N = a.size()
0820: 3b 0a 09 76 65 63 74 6f 72 3c 20 76 65 63 74 6f ;..vector< vecto
0830: 72 3c 54 3e 20 3e 20 63 28 4e 2c 20 76 65 63 74 r<T> > c(N, vect
0840: 6f 72 3c 54 3e 28 4e 29 29 3b 0a 09 66 6f 72 28 or<T>(N));..for(
0850: 69 6e 74 20 69 3d 30 3b 20 69 3c 4e 3b 20 2b 2b int i=0; i<N; ++
0860: 69 29 20 63 5b 69 5d 5b 69 5d 20 3d 20 31 3b 0a i) c[i][i] = 1;.
0870: 09 66 6f 72 28 3b 20 65 3b 20 65 3e 3e 3d 31 29 .for(; e; e>>=1)
0880: 20 7b 0a 09 09 69 66 28 65 26 31 29 0a 09 09 09 {...if(e&1)....
0890: 63 20 3d 20 4d 41 54 4d 55 4c 28 63 2c 20 61 29 c = MATMUL(c, a)
08a0: 3b 0a 09 09 61 20 3d 20 4d 41 54 4d 55 4c 28 61 ;...a = MATMUL(a
08b0: 2c 20 61 29 3b 0a 09 7d 0a 09 72 65 74 75 72 6e , a);..}..return
08c0: 20 63 3b 0a 7d 0a 0a 2f 2a 0a 2f 2f 20 4d 4f 44 c;.}../*.// MOD
08d0: 56 41 4c 20 6d 75 73 74 20 62 65 20 61 20 70 72 VAL must be a pr
08e0: 69 6d 65 21 21 0a 4c 4c 20 47 53 53 28 4c 4c 20 ime!!.LL GSS(LL
08f0: 6b 2c 20 4c 4c 20 62 2c 20 4c 4c 20 65 29 20 2f k, LL b, LL e) /
0900: 2f 20 6b 5e 62 20 2b 20 6b 5e 62 2b 31 20 2b 20 / k^b + k^b+1 +
0910: 2e 2e 2e 20 2b 20 6b 5e 65 0a 7b 0a 09 69 66 28 ... + k^e.{..if(
0920: 20 62 20 3e 20 20 65 20 29 20 72 65 74 75 72 6e b > e ) return
0930: 20 30 3b 0a 09 69 66 28 20 6b 20 3c 3d 20 31 20 0;..if( k <= 1
0940: 29 20 72 65 74 75 72 6e 20 6b 2a 28 65 2d 62 2b ) return k*(e-b+
0950: 31 29 3b 0a 09 72 65 74 75 72 6e 20 44 49 56 28 1);..return DIV(
0960: 53 55 42 28 50 4f 57 28 6b 2c 20 65 2b 31 29 2c SUB(POW(k, e+1),
0970: 20 50 4f 57 28 6b 2c 62 29 29 2c 20 6b 2d 31 29 POW(k,b)), k-1)
0980: 3b 0a 7d 0a 0a 2f 2f 20 77 6f 72 6b 73 20 66 6f ;.}..// works fo
0990: 72 20 6e 6f 6e 2d 70 72 69 6d 65 20 4d 4f 44 56 r non-prime MODV
09a0: 41 4c 0a 4c 4c 20 47 45 4f 28 4c 4c 20 78 5f 2c AL.LL GEO(LL x_,
09b0: 20 4c 4c 20 65 29 20 2f 2f 20 78 5e 30 20 2b 20 LL e) // x^0 +
09c0: 78 5e 31 20 2b 20 2e 2e 2e 20 2b 20 78 5e 65 2d x^1 + ... + x^e-
09d0: 31 0a 7b 0a 20 20 20 76 65 63 74 6f 72 3c 20 76 1.{. vector< v
09e0: 65 63 74 6f 72 3c 4c 4c 3e 20 3e 20 76 28 32 2c ector<LL> > v(2,
09f0: 20 76 65 63 74 6f 72 3c 4c 4c 3e 28 32 29 29 3b vector<LL>(2));
0a00: 0a 20 20 20 76 65 63 74 6f 72 3c 20 76 65 63 74 . vector< vect
0a10: 6f 72 3c 4c 4c 3e 20 3e 20 78 28 32 2c 20 76 65 or<LL> > x(2, ve
0a20: 63 74 6f 72 3c 4c 4c 3e 28 32 29 29 3b 0a 20 20 ctor<LL>(2));.
0a30: 20 76 5b 30 5d 5b 30 5d 20 3d 20 76 5b 31 5d 5b v[0][0] = v[1][
0a40: 31 5d 20 3d 20 31 3b 0a 20 20 20 78 5b 30 5d 5b 1] = 1;. x[0][
0a50: 30 5d 20 3d 20 78 5f 3b 20 78 5b 30 5d 5b 31 5d 0] = x_; x[0][1]
0a60: 20 3d 20 30 3b 0a 20 20 20 78 5b 31 5d 5b 30 5d = 0;. x[1][0]
0a70: 20 3d 20 31 20 3b 20 78 5b 31 5d 5b 31 5d 20 3d = 1 ; x[1][1] =
0a80: 20 31 3b 0a 20 20 20 66 6f 72 28 3b 65 3b 78 3d 1;. for(;e;x=
0a90: 4d 41 54 4d 55 4c 28 78 2c 78 29 2c 65 3e 3e 3d MATMUL(x,x),e>>=
0aa0: 31 29 0a 20 20 20 20 20 20 69 66 28 65 26 31 29 1). if(e&1)
0ab0: 0a 20 20 20 20 20 20 20 20 20 76 20 3d 20 4d 41 . v = MA
0ac0: 54 4d 55 4c 28 76 2c 20 78 29 3b 0a 20 20 20 72 TMUL(v, x);. r
0ad0: 65 74 75 72 6e 20 76 5b 31 5d 5b 30 5d 3b 0a 7d eturn v[1][0];.}
0ae0: 0a 0a 2f 2f 20 77 6f 72 6b 73 20 66 6f 72 20 6e ..// works for n
0af0: 6f 6e 2d 70 72 69 6d 65 20 4d 4f 44 56 41 4c 0a on-prime MODVAL.
0b00: 4c 4c 20 48 59 50 28 4c 4c 20 78 5f 2c 20 4c 4c LL HYP(LL x_, LL
0b10: 20 65 29 20 2f 2f 20 65 20 78 5e 30 20 2b 20 28 e) // e x^0 + (
0b20: 65 2d 31 29 20 78 5e 31 20 2b 20 2e 2e 2e 20 2b e-1) x^1 + ... +
0b30: 20 31 20 78 5e 65 2d 31 20 3d 20 47 45 4f 28 78 1 x^e-1 = GEO(x
0b40: 2c 31 29 2b 47 45 4f 28 78 2c 32 29 2b 2e 2e 2e ,1)+GEO(x,2)+...
0b50: 2b 47 45 4f 28 78 2c 65 29 0a 7b 0a 20 20 20 76 +GEO(x,e).{. v
0b60: 65 63 74 6f 72 3c 20 76 65 63 74 6f 72 3c 4c 4c ector< vector<LL
0b70: 3e 20 3e 20 76 28 33 2c 20 76 65 63 74 6f 72 3c > > v(3, vector<
0b80: 4c 4c 3e 28 33 29 29 3b 0a 20 20 20 76 65 63 74 LL>(3));. vect
0b90: 6f 72 3c 20 76 65 63 74 6f 72 3c 4c 4c 3e 20 3e or< vector<LL> >
0ba0: 20 78 28 33 2c 20 76 65 63 74 6f 72 3c 4c 4c 3e x(3, vector<LL>
0bb0: 28 33 29 29 3b 0a 20 20 20 76 5b 30 5d 5b 30 5d (3));. v[0][0]
0bc0: 20 3d 20 76 5b 31 5d 5b 31 5d 20 3d 20 76 5b 32 = v[1][1] = v[2
0bd0: 5d 5b 32 5d 20 3d 20 31 3b 0a 20 20 20 78 5b 30 ][2] = 1;. x[0
0be0: 5d 5b 30 5d 20 3d 20 78 5f 3b 20 78 5b 30 5d 5b ][0] = x_; x[0][
0bf0: 31 5d 20 3d 20 30 3b 20 78 5b 30 5d 5b 32 5d 20 1] = 0; x[0][2]
0c00: 3d 20 30 3b 0a 20 20 20 78 5b 31 5d 5b 30 5d 20 = 0;. x[1][0]
0c10: 3d 20 31 20 3b 20 78 5b 31 5d 5b 31 5d 20 3d 20 = 1 ; x[1][1] =
0c20: 31 3b 20 78 5b 31 5d 5b 32 5d 20 3d 20 30 3b 0a 1; x[1][2] = 0;.
0c30: 20 20 20 78 5b 32 5d 5b 30 5d 20 3d 20 30 20 3b x[2][0] = 0 ;
0c40: 20 78 5b 32 5d 5b 31 5d 20 3d 20 31 3b 20 78 5b x[2][1] = 1; x[
0c50: 32 5d 5b 32 5d 20 3d 20 31 3b 0a 20 20 20 65 2b 2][2] = 1;. e+
0c60: 2b 3b 0a 20 20 20 66 6f 72 28 3b 65 3b 78 3d 4d +;. for(;e;x=M
0c70: 41 54 4d 55 4c 28 78 2c 78 29 2c 65 3e 3e 3d 31 ATMUL(x,x),e>>=1
0c80: 29 0a 20 20 20 20 20 20 69 66 28 65 26 31 29 0a ). if(e&1).
0c90: 20 20 20 20 20 20 20 20 20 76 20 3d 20 4d 41 54 v = MAT
0ca0: 4d 55 4c 28 76 2c 20 78 29 3b 0a 20 20 20 72 65 MUL(v, x);. re
0cb0: 74 75 72 6e 20 76 5b 32 5d 5b 30 5d 3b 0a 7d 0a turn v[2][0];.}.
0cc0: 2a 2f 0a */.