Artifact 4e73ce5907de5c448c9406d6b5962e0b393a769c:
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 69 6e .static const in
00e0: 74 20 4d 4f 44 56 41 4c 20 3d 20 31 30 30 30 30 t MODVAL = 10000
00f0: 30 30 30 30 37 3b 0a 73 74 72 75 63 74 20 6d 69 00007;.struct mi
0100: 6e 74 0a 7b 0a 09 69 6e 74 20 76 61 6c 3b 0a 09 nt.{..int val;..
0110: 6d 69 6e 74 28 29 3a 76 61 6c 28 30 29 7b 7d 0a mint():val(0){}.
0120: 09 6d 69 6e 74 28 69 6e 74 20 20 20 20 78 29 3a .mint(int x):
0130: 76 61 6c 28 78 25 4d 4f 44 56 41 4c 29 20 7b 7d val(x%MODVAL) {}
0140: 0a 09 6d 69 6e 74 28 73 69 7a 65 5f 74 20 78 29 ..mint(size_t x)
0150: 3a 76 61 6c 28 78 25 4d 4f 44 56 41 4c 29 20 7b :val(x%MODVAL) {
0160: 7d 0a 09 6d 69 6e 74 28 4c 4c 20 20 20 20 20 78 }..mint(LL x
0170: 29 3a 76 61 6c 28 78 25 4d 4f 44 56 41 4c 29 20 ):val(x%MODVAL)
0180: 7b 7d 0a 7d 3b 0a 6d 69 6e 74 26 20 6f 70 65 72 {}.};.mint& oper
0190: 61 74 6f 72 2b 3d 28 6d 69 6e 74 26 20 78 2c 20 ator+=(mint& x,
01a0: 6d 69 6e 74 20 79 29 20 7b 20 72 65 74 75 72 6e mint y) { return
01b0: 20 78 20 3d 20 78 2e 76 61 6c 2b 79 2e 76 61 6c x = x.val+y.val
01c0: 3b 20 7d 0a 6d 69 6e 74 26 20 6f 70 65 72 61 74 ; }.mint& operat
01d0: 6f 72 2d 3d 28 6d 69 6e 74 26 20 78 2c 20 6d 69 or-=(mint& x, mi
01e0: 6e 74 20 79 29 20 7b 20 72 65 74 75 72 6e 20 78 nt y) { return x
01f0: 20 3d 20 78 2e 76 61 6c 2d 79 2e 76 61 6c 2b 4d = x.val-y.val+M
0200: 4f 44 56 41 4c 3b 20 7d 0a 6d 69 6e 74 26 20 6f ODVAL; }.mint& o
0210: 70 65 72 61 74 6f 72 2a 3d 28 6d 69 6e 74 26 20 perator*=(mint&
0220: 78 2c 20 6d 69 6e 74 20 79 29 20 7b 20 72 65 74 x, mint y) { ret
0230: 75 72 6e 20 78 20 3d 20 4c 4c 28 78 2e 76 61 6c urn x = LL(x.val
0240: 29 2a 79 2e 76 61 6c 3b 20 7d 0a 6d 69 6e 74 20 )*y.val; }.mint
0250: 50 4f 57 28 6d 69 6e 74 20 78 2c 20 4c 4c 20 65 POW(mint x, LL e
0260: 29 20 7b 20 6d 69 6e 74 20 76 3d 31 3b 20 66 6f ) { mint v=1; fo
0270: 72 28 3b 65 3b 78 2a 3d 78 2c 65 3e 3e 3d 31 29 r(;e;x*=x,e>>=1)
0280: 20 69 66 28 65 26 31 29 20 76 2a 3d 78 3b 20 72 if(e&1) v*=x; r
0290: 65 74 75 72 6e 20 76 3b 20 7d 0a 6d 69 6e 74 26 eturn v; }.mint&
02a0: 20 6f 70 65 72 61 74 6f 72 2f 3d 28 6d 69 6e 74 operator/=(mint
02b0: 26 20 78 2c 20 6d 69 6e 74 20 79 29 20 7b 20 72 & x, mint y) { r
02c0: 65 74 75 72 6e 20 78 20 2a 3d 20 50 4f 57 28 79 eturn x *= POW(y
02d0: 2c 20 4d 4f 44 56 41 4c 2d 32 29 3b 20 7d 0a 6d , MODVAL-2); }.m
02e0: 69 6e 74 20 6f 70 65 72 61 74 6f 72 2b 28 6d 69 int operator+(mi
02f0: 6e 74 20 78 2c 20 6d 69 6e 74 20 79 29 20 7b 20 nt x, mint y) {
0300: 72 65 74 75 72 6e 20 78 2b 3d 79 3b 20 7d 0a 6d return x+=y; }.m
0310: 69 6e 74 20 6f 70 65 72 61 74 6f 72 2d 28 6d 69 int operator-(mi
0320: 6e 74 20 78 2c 20 6d 69 6e 74 20 79 29 20 7b 20 nt x, mint y) {
0330: 72 65 74 75 72 6e 20 78 2d 3d 79 3b 20 7d 0a 6d return x-=y; }.m
0340: 69 6e 74 20 6f 70 65 72 61 74 6f 72 2a 28 6d 69 int operator*(mi
0350: 6e 74 20 78 2c 20 6d 69 6e 74 20 79 29 20 7b 20 nt x, mint y) {
0360: 72 65 74 75 72 6e 20 78 2a 3d 79 3b 20 7d 0a 6d return x*=y; }.m
0370: 69 6e 74 20 6f 70 65 72 61 74 6f 72 2f 28 6d 69 int operator/(mi
0380: 6e 74 20 78 2c 20 6d 69 6e 74 20 79 29 20 7b 20 nt x, mint y) {
0390: 72 65 74 75 72 6e 20 78 2f 3d 79 3b 20 7d 0a 76 return x/=y; }.v
03a0: 65 63 74 6f 72 3c 6d 69 6e 74 3e 20 46 41 43 5f ector<mint> FAC_
03b0: 28 31 2c 31 29 3b 0a 6d 69 6e 74 20 46 41 43 28 (1,1);.mint FAC(
03c0: 4c 4c 20 6e 29 20 7b 20 77 68 69 6c 65 28 20 46 LL n) { while( F
03d0: 41 43 5f 2e 73 69 7a 65 28 29 3c 3d 6e 20 29 20 AC_.size()<=n )
03e0: 46 41 43 5f 2e 70 75 73 68 5f 62 61 63 6b 28 20 FAC_.push_back(
03f0: 46 41 43 5f 2e 62 61 63 6b 28 29 2a 46 41 43 5f FAC_.back()*FAC_
0400: 2e 73 69 7a 65 28 29 20 29 3b 20 72 65 74 75 72 .size() ); retur
0410: 6e 20 46 41 43 5f 5b 6e 5d 3b 20 7d 0a 6d 69 6e n FAC_[n]; }.min
0420: 74 20 43 28 4c 4c 20 6e 2c 20 4c 4c 20 6b 29 20 t C(LL n, LL k)
0430: 7b 20 72 65 74 75 72 6e 20 6b 3c 30 20 7c 7c 20 { return k<0 ||
0440: 6e 3c 6b 20 3f 20 30 20 3a 20 46 41 43 28 6e 29 n<k ? 0 : FAC(n)
0450: 20 2f 20 28 46 41 43 28 6b 29 20 2a 20 46 41 43 / (FAC(k) * FAC
0460: 28 6e 2d 6b 29 29 3b 20 7d 0a 76 65 63 74 6f 72 (n-k)); }.vector
0470: 3c 20 76 65 63 74 6f 72 3c 6d 69 6e 74 3e 20 3e < vector<mint> >
0480: 20 43 50 5f 3b 20 2f 2f 20 50 61 73 63 61 6c 27 CP_; // Pascal'
0490: 73 20 74 72 69 61 6e 67 6c 65 3a 20 69 66 20 4f s triangle: if O
04a0: 28 31 29 20 6e 43 6b 20 69 73 20 6e 65 65 64 65 (1) nCk is neede
04b0: 64 2e 0a 6d 69 6e 74 20 43 28 4c 4c 20 6e 2c 20 d..mint C(LL n,
04c0: 4c 4c 20 6b 29 20 7b 0a 09 77 68 69 6c 65 28 20 LL k) {..while(
04d0: 43 50 5f 2e 73 69 7a 65 28 29 20 3c 3d 20 6e 20 CP_.size() <= n
04e0: 29 20 7b 0a 09 09 69 6e 74 20 6e 6e 20 3d 20 43 ) {...int nn = C
04f0: 50 5f 2e 73 69 7a 65 28 29 3b 0a 09 09 43 50 5f P_.size();...CP_
0500: 2e 70 75 73 68 5f 62 61 63 6b 28 76 65 63 74 6f .push_back(vecto
0510: 72 3c 6d 69 6e 74 3e 28 6e 6e 2b 31 2c 31 29 29 r<mint>(nn+1,1))
0520: 3b 0a 09 09 66 6f 72 28 69 6e 74 20 6b 6b 3d 31 ;...for(int kk=1
0530: 3b 20 6b 6b 3c 6e 6e 3b 20 2b 2b 6b 6b 29 0a 09 ; kk<nn; ++kk)..
0540: 09 09 43 50 5f 5b 6e 6e 5d 5b 6b 6b 5d 20 3d 20 ..CP_[nn][kk] =
0550: 43 50 5f 5b 6e 6e 2d 31 5d 5b 6b 6b 2d 31 5d 20 CP_[nn-1][kk-1]
0560: 2b 20 43 50 5f 5b 6e 6e 2d 31 5d 5b 6b 6b 5d 3b + CP_[nn-1][kk];
0570: 0a 09 7d 0a 09 72 65 74 75 72 6e 20 6b 3c 30 20 ..}..return k<0
0580: 7c 7c 20 6e 3c 6b 20 3f 20 30 20 3a 20 43 50 5f || n<k ? 0 : CP_
0590: 5b 6e 5d 5b 6b 5d 3b 0a 7d 0a 0a 74 65 6d 70 6c [n][k];.}..templ
05a0: 61 74 65 3c 74 79 70 65 6e 61 6d 65 20 54 3e 0a ate<typename T>.
05b0: 76 65 63 74 6f 72 3c 54 3e 20 4d 41 54 4d 55 4c vector<T> MATMUL
05c0: 28 63 6f 6e 73 74 20 76 65 63 74 6f 72 3c 20 76 (const vector< v
05d0: 65 63 74 6f 72 3c 54 3e 20 3e 26 20 61 2c 20 63 ector<T> >& a, c
05e0: 6f 6e 73 74 20 76 65 63 74 6f 72 3c 54 3e 26 20 onst vector<T>&
05f0: 76 29 0a 7b 0a 09 69 6e 74 20 4e 20 3d 20 61 2e v).{..int N = a.
0600: 73 69 7a 65 28 29 3b 0a 09 76 65 63 74 6f 72 3c size();..vector<
0610: 54 3e 20 75 28 4e 29 3b 0a 09 66 6f 72 28 69 6e T> u(N);..for(in
0620: 74 20 69 3d 30 3b 20 69 3c 4e 3b 20 2b 2b 69 29 t i=0; i<N; ++i)
0630: 0a 09 66 6f 72 28 69 6e 74 20 6a 3d 30 3b 20 6a ..for(int j=0; j
0640: 3c 4e 3b 20 2b 2b 6a 29 0a 09 09 75 5b 69 5d 20 <N; ++j)...u[i]
0650: 2b 3d 20 61 5b 69 5d 5b 6a 5d 2a 76 5b 6a 5d 3b += a[i][j]*v[j];
0660: 0a 09 72 65 74 75 72 6e 20 75 3b 0a 7d 0a 0a 74 ..return u;.}..t
0670: 65 6d 70 6c 61 74 65 3c 74 79 70 65 6e 61 6d 65 emplate<typename
0680: 20 54 3e 0a 76 65 63 74 6f 72 3c 20 76 65 63 74 T>.vector< vect
0690: 6f 72 3c 54 3e 20 3e 20 4d 41 54 4d 55 4c 28 63 or<T> > MATMUL(c
06a0: 6f 6e 73 74 20 76 65 63 74 6f 72 3c 20 76 65 63 onst vector< vec
06b0: 74 6f 72 3c 54 3e 20 3e 26 20 61 2c 20 63 6f 6e tor<T> >& a, con
06c0: 73 74 20 76 65 63 74 6f 72 3c 20 76 65 63 74 6f st vector< vecto
06d0: 72 3c 54 3e 20 3e 26 20 62 29 0a 7b 0a 09 69 6e r<T> >& b).{..in
06e0: 74 20 4e 20 3d 20 61 2e 73 69 7a 65 28 29 3b 0a t N = a.size();.
06f0: 09 76 65 63 74 6f 72 3c 20 76 65 63 74 6f 72 3c .vector< vector<
0700: 54 3e 20 3e 20 63 28 4e 2c 20 76 65 63 74 6f 72 T> > c(N, vector
0710: 3c 54 3e 28 4e 29 29 3b 0a 09 66 6f 72 28 69 6e <T>(N));..for(in
0720: 74 20 69 3d 30 3b 20 69 3c 4e 3b 20 2b 2b 69 29 t i=0; i<N; ++i)
0730: 0a 09 66 6f 72 28 69 6e 74 20 6a 3d 30 3b 20 6a ..for(int j=0; j
0740: 3c 4e 3b 20 2b 2b 6a 29 0a 09 66 6f 72 28 69 6e <N; ++j)..for(in
0750: 74 20 6b 3d 30 3b 20 6b 3c 4e 3b 20 2b 2b 6b 29 t k=0; k<N; ++k)
0760: 0a 09 09 63 5b 69 5d 5b 6a 5d 20 2b 3d 20 61 5b ...c[i][j] += a[
0770: 69 5d 5b 6b 5d 2a 62 5b 6b 5d 5b 6a 5d 3b 0a 09 i][k]*b[k][j];..
0780: 72 65 74 75 72 6e 20 63 3b 0a 7d 0a 0a 74 65 6d return c;.}..tem
0790: 70 6c 61 74 65 3c 74 79 70 65 6e 61 6d 65 20 54 plate<typename T
07a0: 3e 0a 76 65 63 74 6f 72 3c 20 76 65 63 74 6f 72 >.vector< vector
07b0: 3c 54 3e 20 3e 20 4d 41 54 50 4f 57 28 76 65 63 <T> > MATPOW(vec
07c0: 74 6f 72 3c 20 76 65 63 74 6f 72 3c 54 3e 20 3e tor< vector<T> >
07d0: 20 61 2c 20 4c 4c 20 65 29 0a 7b 0a 09 69 6e 74 a, LL e).{..int
07e0: 20 4e 20 3d 20 61 2e 73 69 7a 65 28 29 3b 0a 09 N = a.size();..
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 63 28 4e 2c 20 76 65 63 74 6f 72 3c > > c(N, vector<
0810: 54 3e 28 4e 29 29 3b 0a 09 66 6f 72 28 69 6e 74 T>(N));..for(int
0820: 20 69 3d 30 3b 20 69 3c 4e 3b 20 2b 2b 69 29 20 i=0; i<N; ++i)
0830: 63 5b 69 5d 5b 69 5d 20 3d 20 31 3b 0a 09 66 6f c[i][i] = 1;..fo
0840: 72 28 3b 20 65 3b 20 65 3e 3e 3d 31 29 20 7b 0a r(; e; e>>=1) {.
0850: 09 09 69 66 28 65 26 31 29 0a 09 09 09 63 20 3d ..if(e&1)....c =
0860: 20 4d 41 54 4d 55 4c 28 63 2c 20 61 29 3b 0a 09 MATMUL(c, a);..
0870: 09 61 20 3d 20 4d 41 54 4d 55 4c 28 61 2c 20 61 .a = MATMUL(a, a
0880: 29 3b 0a 09 7d 0a 09 72 65 74 75 72 6e 20 63 3b );..}..return c;
0890: 0a 7d 0a 0a 2f 2a 0a 2f 2f 20 4d 4f 44 56 41 4c .}../*.// MODVAL
08a0: 20 6d 75 73 74 20 62 65 20 61 20 70 72 69 6d 65 must be a prime
08b0: 21 21 0a 4c 4c 20 47 53 53 28 4c 4c 20 6b 2c 20 !!.LL GSS(LL k,
08c0: 4c 4c 20 62 2c 20 4c 4c 20 65 29 20 2f 2f 20 6b LL b, LL e) // k
08d0: 5e 62 20 2b 20 6b 5e 62 2b 31 20 2b 20 2e 2e 2e ^b + k^b+1 + ...
08e0: 20 2b 20 6b 5e 65 0a 7b 0a 09 69 66 28 20 62 20 + k^e.{..if( b
08f0: 3e 20 20 65 20 29 20 72 65 74 75 72 6e 20 30 3b > e ) return 0;
0900: 0a 09 69 66 28 20 6b 20 3c 3d 20 31 20 29 20 72 ..if( k <= 1 ) r
0910: 65 74 75 72 6e 20 6b 2a 28 65 2d 62 2b 31 29 3b eturn k*(e-b+1);
0920: 0a 09 72 65 74 75 72 6e 20 44 49 56 28 53 55 42 ..return DIV(SUB
0930: 28 50 4f 57 28 6b 2c 20 65 2b 31 29 2c 20 50 4f (POW(k, e+1), PO
0940: 57 28 6b 2c 62 29 29 2c 20 6b 2d 31 29 3b 0a 7d W(k,b)), k-1);.}
0950: 0a 0a 2f 2f 20 77 6f 72 6b 73 20 66 6f 72 20 6e ..// works for n
0960: 6f 6e 2d 70 72 69 6d 65 20 4d 4f 44 56 41 4c 0a on-prime MODVAL.
0970: 4c 4c 20 47 45 4f 28 4c 4c 20 78 5f 2c 20 4c 4c LL GEO(LL x_, LL
0980: 20 65 29 20 2f 2f 20 78 5e 30 20 2b 20 78 5e 31 e) // x^0 + x^1
0990: 20 2b 20 2e 2e 2e 20 2b 20 78 5e 65 2d 31 0a 7b + ... + x^e-1.{
09a0: 0a 20 20 20 76 65 63 74 6f 72 3c 20 76 65 63 74 . vector< vect
09b0: 6f 72 3c 4c 4c 3e 20 3e 20 76 28 32 2c 20 76 65 or<LL> > v(2, ve
09c0: 63 74 6f 72 3c 4c 4c 3e 28 32 29 29 3b 0a 20 20 ctor<LL>(2));.
09d0: 20 76 65 63 74 6f 72 3c 20 76 65 63 74 6f 72 3c vector< vector<
09e0: 4c 4c 3e 20 3e 20 78 28 32 2c 20 76 65 63 74 6f LL> > x(2, vecto
09f0: 72 3c 4c 4c 3e 28 32 29 29 3b 0a 20 20 20 76 5b r<LL>(2));. v[
0a00: 30 5d 5b 30 5d 20 3d 20 76 5b 31 5d 5b 31 5d 20 0][0] = v[1][1]
0a10: 3d 20 31 3b 0a 20 20 20 78 5b 30 5d 5b 30 5d 20 = 1;. x[0][0]
0a20: 3d 20 78 5f 3b 20 78 5b 30 5d 5b 31 5d 20 3d 20 = x_; x[0][1] =
0a30: 30 3b 0a 20 20 20 78 5b 31 5d 5b 30 5d 20 3d 20 0;. x[1][0] =
0a40: 31 20 3b 20 78 5b 31 5d 5b 31 5d 20 3d 20 31 3b 1 ; x[1][1] = 1;
0a50: 0a 20 20 20 66 6f 72 28 3b 65 3b 78 3d 4d 41 54 . for(;e;x=MAT
0a60: 4d 55 4c 28 78 2c 78 29 2c 65 3e 3e 3d 31 29 0a MUL(x,x),e>>=1).
0a70: 20 20 20 20 20 20 69 66 28 65 26 31 29 0a 20 20 if(e&1).
0a80: 20 20 20 20 20 20 20 76 20 3d 20 4d 41 54 4d 55 v = MATMU
0a90: 4c 28 76 2c 20 78 29 3b 0a 20 20 20 72 65 74 75 L(v, x);. retu
0aa0: 72 6e 20 76 5b 31 5d 5b 30 5d 3b 0a 7d 0a 0a 2f rn v[1][0];.}../
0ab0: 2f 20 77 6f 72 6b 73 20 66 6f 72 20 6e 6f 6e 2d / works for non-
0ac0: 70 72 69 6d 65 20 4d 4f 44 56 41 4c 0a 4c 4c 20 prime MODVAL.LL
0ad0: 48 59 50 28 4c 4c 20 78 5f 2c 20 4c 4c 20 65 29 HYP(LL x_, LL e)
0ae0: 20 2f 2f 20 65 20 78 5e 30 20 2b 20 28 65 2d 31 // e x^0 + (e-1
0af0: 29 20 78 5e 31 20 2b 20 2e 2e 2e 20 2b 20 31 20 ) x^1 + ... + 1
0b00: 78 5e 65 2d 31 20 3d 20 47 45 4f 28 78 2c 31 29 x^e-1 = GEO(x,1)
0b10: 2b 47 45 4f 28 78 2c 32 29 2b 2e 2e 2e 2b 47 45 +GEO(x,2)+...+GE
0b20: 4f 28 78 2c 65 29 0a 7b 0a 20 20 20 76 65 63 74 O(x,e).{. vect
0b30: 6f 72 3c 20 76 65 63 74 6f 72 3c 4c 4c 3e 20 3e or< vector<LL> >
0b40: 20 76 28 33 2c 20 76 65 63 74 6f 72 3c 4c 4c 3e v(3, vector<LL>
0b50: 28 33 29 29 3b 0a 20 20 20 76 65 63 74 6f 72 3c (3));. vector<
0b60: 20 76 65 63 74 6f 72 3c 4c 4c 3e 20 3e 20 78 28 vector<LL> > x(
0b70: 33 2c 20 76 65 63 74 6f 72 3c 4c 4c 3e 28 33 29 3, vector<LL>(3)
0b80: 29 3b 0a 20 20 20 76 5b 30 5d 5b 30 5d 20 3d 20 );. v[0][0] =
0b90: 76 5b 31 5d 5b 31 5d 20 3d 20 76 5b 32 5d 5b 32 v[1][1] = v[2][2
0ba0: 5d 20 3d 20 31 3b 0a 20 20 20 78 5b 30 5d 5b 30 ] = 1;. x[0][0
0bb0: 5d 20 3d 20 78 5f 3b 20 78 5b 30 5d 5b 31 5d 20 ] = x_; x[0][1]
0bc0: 3d 20 30 3b 20 78 5b 30 5d 5b 32 5d 20 3d 20 30 = 0; x[0][2] = 0
0bd0: 3b 0a 20 20 20 78 5b 31 5d 5b 30 5d 20 3d 20 31 ;. x[1][0] = 1
0be0: 20 3b 20 78 5b 31 5d 5b 31 5d 20 3d 20 31 3b 20 ; x[1][1] = 1;
0bf0: 78 5b 31 5d 5b 32 5d 20 3d 20 30 3b 0a 20 20 20 x[1][2] = 0;.
0c00: 78 5b 32 5d 5b 30 5d 20 3d 20 30 20 3b 20 78 5b x[2][0] = 0 ; x[
0c10: 32 5d 5b 31 5d 20 3d 20 31 3b 20 78 5b 32 5d 5b 2][1] = 1; x[2][
0c20: 32 5d 20 3d 20 31 3b 0a 20 20 20 65 2b 2b 3b 0a 2] = 1;. e++;.
0c30: 20 20 20 66 6f 72 28 3b 65 3b 78 3d 4d 41 54 4d for(;e;x=MATM
0c40: 55 4c 28 78 2c 78 29 2c 65 3e 3e 3d 31 29 0a 20 UL(x,x),e>>=1).
0c50: 20 20 20 20 20 69 66 28 65 26 31 29 0a 20 20 20 if(e&1).
0c60: 20 20 20 20 20 20 76 20 3d 20 4d 41 54 4d 55 4c v = MATMUL
0c70: 28 76 2c 20 78 29 3b 0a 20 20 20 72 65 74 75 72 (v, x);. retur
0c80: 6e 20 76 5b 32 5d 5b 30 5d 3b 0a 7d 0a 2a 2f 0a n v[2][0];.}.*/.