Artifact b669f317babaf285dd3c99005ad3f02129fab1ff:
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: 53 52 4d 20 33 39 37 20 44 69 76 31 20 4c 56 32 SRM 397 Div1 LV2
0080: 0a 2f 2f 20 20 20 2d 20 53 52 4d 20 34 32 38 20 .// - SRM 428
0090: 44 69 76 31 20 4c 56 32 0a 2f 2f 20 20 20 2d 20 Div1 LV2.// -
00a0: 43 6f 64 65 43 72 61 66 74 20 32 30 31 30 20 43 CodeCraft 2010 C
00b0: 4e 54 49 4e 54 20 44 52 41 57 0a 2f 2f 2d 2d 2d NTINT DRAW.//---
00c0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
00d0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
00e0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
00f0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 0a 73 74 61 74 ----------..stat
0100: 69 63 20 63 6f 6e 73 74 20 4c 4c 20 4d 4f 44 56 ic const LL MODV
0110: 41 4c 20 3d 20 31 30 30 30 30 30 30 30 30 37 3b AL = 1000000007;
0120: 20 2f 2f 20 6d 75 73 74 20 66 69 74 20 69 6e 20 // must fit in
0130: 33 32 2d 62 69 74 73 0a 0a 4c 4c 20 41 44 44 28 32-bits..LL ADD(
0140: 4c 4c 20 78 2c 20 4c 4c 20 79 29 20 7b 20 72 65 LL x, LL y) { re
0150: 74 75 72 6e 20 28 78 2b 79 29 25 4d 4f 44 56 41 turn (x+y)%MODVA
0160: 4c 3b 20 7d 0a 4c 4c 20 53 55 42 28 4c 4c 20 78 L; }.LL SUB(LL x
0170: 2c 20 4c 4c 20 79 29 20 7b 20 72 65 74 75 72 6e , LL y) { return
0180: 20 28 78 2d 79 2b 4d 4f 44 56 41 4c 29 25 4d 4f (x-y+MODVAL)%MO
0190: 44 56 41 4c 3b 20 7d 0a 4c 4c 20 4d 55 4c 28 4c DVAL; }.LL MUL(L
01a0: 4c 20 78 2c 20 4c 4c 20 79 29 20 7b 20 72 65 74 L x, LL y) { ret
01b0: 75 72 6e 20 28 78 2a 79 29 25 4d 4f 44 56 41 4c urn (x*y)%MODVAL
01c0: 3b 20 7d 0a 4c 4c 20 50 4f 57 28 4c 4c 20 78 2c ; }.LL POW(LL x,
01d0: 20 4c 4c 20 65 29 20 7b 0a 09 4c 4c 20 76 20 3d LL e) {..LL v =
01e0: 20 31 3b 0a 09 66 6f 72 28 3b 65 3b 78 3d 4d 55 1;..for(;e;x=MU
01f0: 4c 28 78 2c 78 29 2c 65 3e 3e 3d 31 29 0a 09 09 L(x,x),e>>=1)...
0200: 69 66 28 65 26 31 29 0a 09 09 09 76 20 3d 20 4d if(e&1)....v = M
0210: 55 4c 28 76 2c 20 78 29 3b 0a 09 72 65 74 75 72 UL(v, x);..retur
0220: 6e 20 76 3b 0a 7d 0a 0a 2f 2f 20 4d 4f 44 56 41 n v;.}..// MODVA
0230: 4c 20 6d 75 73 74 20 62 65 20 61 20 70 72 69 6d L must be a prim
0240: 65 21 21 0a 4c 4c 20 44 49 56 28 4c 4c 20 78 2c e!!.LL DIV(LL x,
0250: 20 4c 4c 20 79 29 20 7b 20 72 65 74 75 72 6e 20 LL y) { return
0260: 4d 55 4c 28 78 2c 20 50 4f 57 28 79 2c 20 4d 4f MUL(x, POW(y, MO
0270: 44 56 41 4c 2d 32 29 29 3b 20 7d 0a 0a 2f 2f 20 DVAL-2)); }..//
0280: 4d 4f 44 56 41 4c 20 6d 75 73 74 20 62 65 20 61 MODVAL must be a
0290: 20 70 72 69 6d 65 21 21 0a 4c 4c 20 43 28 4c 4c prime!!.LL C(LL
02a0: 20 6e 2c 20 4c 4c 20 6b 29 20 7b 0a 09 4c 4c 20 n, LL k) {..LL
02b0: 76 20 3d 20 31 3b 0a 09 66 6f 72 28 4c 4c 20 69 v = 1;..for(LL i
02c0: 3d 31 3b 20 69 3c 3d 6b 3b 20 2b 2b 69 29 0a 09 =1; i<=k; ++i)..
02d0: 09 76 20 3d 20 44 49 56 28 4d 55 4c 28 76 2c 20 .v = DIV(MUL(v,
02e0: 6e 2d 69 2b 31 29 2c 20 69 29 3b 0a 09 72 65 74 n-i+1), i);..ret
02f0: 75 72 6e 20 76 3b 0a 7d 0a 0a 2f 2f 20 4d 4f 44 urn v;.}..// MOD
0300: 56 41 4c 20 6d 75 73 74 20 62 65 20 61 20 70 72 VAL must be a pr
0310: 69 6d 65 21 21 0a 4c 4c 20 47 53 53 28 4c 4c 20 ime!!.LL GSS(LL
0320: 6b 2c 20 4c 4c 20 62 2c 20 4c 4c 20 65 29 20 2f k, LL b, LL e) /
0330: 2f 20 6b 5e 62 20 2b 20 6b 5e 62 2b 31 20 2b 20 / k^b + k^b+1 +
0340: 2e 2e 2e 20 2b 20 6b 5e 65 0a 7b 0a 09 69 66 28 ... + k^e.{..if(
0350: 20 62 20 3e 20 20 65 20 29 20 72 65 74 75 72 6e b > e ) return
0360: 20 30 3b 0a 09 69 66 28 20 6b 20 3c 3d 20 31 20 0;..if( k <= 1
0370: 29 20 72 65 74 75 72 6e 20 6b 2a 28 65 2d 62 2b ) return k*(e-b+
0380: 31 29 3b 0a 09 72 65 74 75 72 6e 20 44 49 56 28 1);..return DIV(
0390: 53 55 42 28 50 4f 57 28 6b 2c 20 65 2b 31 29 2c SUB(POW(k, e+1),
03a0: 20 50 4f 57 28 6b 2c 62 29 29 2c 20 6b 2d 31 29 POW(k,b)), k-1)
03b0: 3b 0a 7d 0a 0a 0a 0a 0a 4c 4c 20 43 70 61 73 63 ;.}.....LL Cpasc
03c0: 61 6c 28 4c 4c 20 6e 2c 20 4c 4c 20 6b 29 0a 7b al(LL n, LL k).{
03d0: 0a 09 76 65 63 74 6f 72 3c 20 76 65 63 74 6f 72 ..vector< vector
03e0: 3c 4c 4c 3e 20 3e 20 63 28 6e 2b 31 2c 20 76 65 <LL> > c(n+1, ve
03f0: 63 74 6f 72 3c 4c 4c 3e 28 6b 2b 31 29 29 3b 0a ctor<LL>(k+1));.
0400: 09 66 6f 72 28 4c 4c 20 6e 6e 3d 31 3b 20 6e 6e .for(LL nn=1; nn
0410: 3c 3d 6e 3b 20 2b 2b 6e 6e 29 0a 09 09 66 6f 72 <=n; ++nn)...for
0420: 28 4c 4c 20 6b 6b 3d 30 3b 20 6b 6b 3c 3d 6d 69 (LL kk=0; kk<=mi
0430: 6e 28 6e 6e 2c 6b 29 3b 20 2b 2b 6b 6b 29 0a 09 n(nn,k); ++kk)..
0440: 09 09 63 5b 6e 6e 5d 5b 6b 6b 5d 20 3d 20 6b 6b ..c[nn][kk] = kk
0450: 3d 3d 30 20 7c 7c 20 6b 6b 3d 3d 6e 6e 20 3f 20 ==0 || kk==nn ?
0460: 31 20 3a 20 41 44 44 28 63 5b 6e 6e 2d 31 5d 5b 1 : ADD(c[nn-1][
0470: 6b 6b 2d 31 5d 2c 20 63 5b 6e 6e 2d 31 5d 5b 6b kk-1], c[nn-1][k
0480: 6b 5d 29 3b 0a 09 72 65 74 75 72 6e 20 63 5b 6e k]);..return c[n
0490: 5d 5b 6b 5d 3b 0a 7d 0a 0a 76 65 63 74 6f 72 3c ][k];.}..vector<
04a0: 20 76 65 63 74 6f 72 3c 4c 4c 3e 20 3e 20 4d 41 vector<LL> > MA
04b0: 54 4d 55 4c 28 76 65 63 74 6f 72 3c 20 76 65 63 TMUL(vector< vec
04c0: 74 6f 72 3c 4c 4c 3e 20 3e 26 20 61 2c 20 76 65 tor<LL> >& a, ve
04d0: 63 74 6f 72 3c 20 76 65 63 74 6f 72 3c 4c 4c 3e ctor< vector<LL>
04e0: 20 3e 26 20 62 29 0a 7b 0a 20 20 20 69 6e 74 20 >& b).{. int
04f0: 4e 20 3d 20 61 2e 73 69 7a 65 28 29 3b 0a 20 20 N = a.size();.
0500: 20 76 65 63 74 6f 72 3c 20 76 65 63 74 6f 72 3c vector< vector<
0510: 4c 4c 3e 20 3e 20 63 28 4e 2c 20 76 65 63 74 6f LL> > c(N, vecto
0520: 72 3c 4c 4c 3e 28 4e 29 29 3b 0a 20 20 20 66 6f r<LL>(N));. fo
0530: 72 28 69 6e 74 20 69 3d 30 3b 20 69 3c 4e 3b 20 r(int i=0; i<N;
0540: 2b 2b 69 29 0a 20 20 20 66 6f 72 28 69 6e 74 20 ++i). for(int
0550: 6a 3d 30 3b 20 6a 3c 4e 3b 20 2b 2b 6a 29 0a 20 j=0; j<N; ++j).
0560: 20 20 66 6f 72 28 69 6e 74 20 6b 3d 30 3b 20 6b for(int k=0; k
0570: 3c 4e 3b 20 2b 2b 6b 29 0a 20 20 20 20 20 20 63 <N; ++k). c
0580: 5b 69 5d 5b 6a 5d 20 3d 20 41 44 44 28 63 5b 69 [i][j] = ADD(c[i
0590: 5d 5b 6a 5d 2c 20 4d 55 4c 28 61 5b 69 5d 5b 6b ][j], MUL(a[i][k
05a0: 5d 2c 62 5b 6b 5d 5b 6a 5d 29 29 3b 0a 20 20 20 ],b[k][j]));.
05b0: 72 65 74 75 72 6e 20 63 3b 0a 7d 0a 0a 2f 2f 20 return c;.}..//
05c0: 77 6f 72 6b 73 20 66 6f 72 20 6e 6f 6e 2d 70 72 works for non-pr
05d0: 69 6d 65 20 4d 4f 44 56 41 4c 0a 4c 4c 20 47 45 ime MODVAL.LL GE
05e0: 4f 28 4c 4c 20 78 5f 2c 20 4c 4c 20 65 29 20 2f O(LL x_, LL e) /
05f0: 2f 20 78 5e 30 20 2b 20 78 5e 31 20 2b 20 2e 2e / x^0 + x^1 + ..
0600: 2e 20 2b 20 78 5e 65 2d 31 0a 7b 0a 20 20 20 76 . + x^e-1.{. v
0610: 65 63 74 6f 72 3c 20 76 65 63 74 6f 72 3c 4c 4c ector< vector<LL
0620: 3e 20 3e 20 76 28 32 2c 20 76 65 63 74 6f 72 3c > > v(2, vector<
0630: 4c 4c 3e 28 32 29 29 3b 0a 20 20 20 76 65 63 74 LL>(2));. vect
0640: 6f 72 3c 20 76 65 63 74 6f 72 3c 4c 4c 3e 20 3e or< vector<LL> >
0650: 20 78 28 32 2c 20 76 65 63 74 6f 72 3c 4c 4c 3e x(2, vector<LL>
0660: 28 32 29 29 3b 0a 20 20 20 76 5b 30 5d 5b 30 5d (2));. v[0][0]
0670: 20 3d 20 76 5b 31 5d 5b 31 5d 20 3d 20 31 3b 0a = v[1][1] = 1;.
0680: 20 20 20 78 5b 30 5d 5b 30 5d 20 3d 20 78 5f 3b x[0][0] = x_;
0690: 20 78 5b 30 5d 5b 31 5d 20 3d 20 30 3b 0a 20 20 x[0][1] = 0;.
06a0: 20 78 5b 31 5d 5b 30 5d 20 3d 20 31 20 3b 20 78 x[1][0] = 1 ; x
06b0: 5b 31 5d 5b 31 5d 20 3d 20 31 3b 0a 20 20 20 66 [1][1] = 1;. f
06c0: 6f 72 28 3b 65 3b 78 3d 4d 41 54 4d 55 4c 28 78 or(;e;x=MATMUL(x
06d0: 2c 78 29 2c 65 3e 3e 3d 31 29 0a 20 20 20 20 20 ,x),e>>=1).
06e0: 20 69 66 28 65 26 31 29 0a 20 20 20 20 20 20 20 if(e&1).
06f0: 20 20 76 20 3d 20 4d 41 54 4d 55 4c 28 76 2c 20 v = MATMUL(v,
0700: 78 29 3b 0a 20 20 20 72 65 74 75 72 6e 20 76 5b x);. return v[
0710: 31 5d 5b 30 5d 3b 0a 7d 0a 0a 2f 2f 20 77 6f 72 1][0];.}..// wor
0720: 6b 73 20 66 6f 72 20 6e 6f 6e 2d 70 72 69 6d 65 ks for non-prime
0730: 20 4d 4f 44 56 41 4c 0a 4c 4c 20 48 59 50 28 4c MODVAL.LL HYP(L
0740: 4c 20 78 5f 2c 20 4c 4c 20 65 29 20 2f 2f 20 65 L x_, LL e) // e
0750: 20 78 5e 30 20 2b 20 28 65 2d 31 29 20 78 5e 31 x^0 + (e-1) x^1
0760: 20 2b 20 2e 2e 2e 20 2b 20 31 20 78 5e 65 2d 31 + ... + 1 x^e-1
0770: 20 3d 20 47 45 4f 28 78 2c 31 29 2b 47 45 4f 28 = GEO(x,1)+GEO(
0780: 78 2c 32 29 2b 2e 2e 2e 2b 47 45 4f 28 78 2c 65 x,2)+...+GEO(x,e
0790: 29 0a 7b 0a 20 20 20 76 65 63 74 6f 72 3c 20 76 ).{. vector< v
07a0: 65 63 74 6f 72 3c 4c 4c 3e 20 3e 20 76 28 33 2c ector<LL> > v(3,
07b0: 20 76 65 63 74 6f 72 3c 4c 4c 3e 28 33 29 29 3b vector<LL>(3));
07c0: 0a 20 20 20 76 65 63 74 6f 72 3c 20 76 65 63 74 . vector< vect
07d0: 6f 72 3c 4c 4c 3e 20 3e 20 78 28 33 2c 20 76 65 or<LL> > x(3, ve
07e0: 63 74 6f 72 3c 4c 4c 3e 28 33 29 29 3b 0a 20 20 ctor<LL>(3));.
07f0: 20 76 5b 30 5d 5b 30 5d 20 3d 20 76 5b 31 5d 5b v[0][0] = v[1][
0800: 31 5d 20 3d 20 76 5b 32 5d 5b 32 5d 20 3d 20 31 1] = v[2][2] = 1
0810: 3b 0a 20 20 20 78 5b 30 5d 5b 30 5d 20 3d 20 78 ;. x[0][0] = x
0820: 5f 3b 20 78 5b 30 5d 5b 31 5d 20 3d 20 30 3b 20 _; x[0][1] = 0;
0830: 78 5b 30 5d 5b 32 5d 20 3d 20 30 3b 0a 20 20 20 x[0][2] = 0;.
0840: 78 5b 31 5d 5b 30 5d 20 3d 20 31 20 3b 20 78 5b x[1][0] = 1 ; x[
0850: 31 5d 5b 31 5d 20 3d 20 31 3b 20 78 5b 31 5d 5b 1][1] = 1; x[1][
0860: 32 5d 20 3d 20 30 3b 0a 20 20 20 78 5b 32 5d 5b 2] = 0;. x[2][
0870: 30 5d 20 3d 20 30 20 3b 20 78 5b 32 5d 5b 31 5d 0] = 0 ; x[2][1]
0880: 20 3d 20 31 3b 20 78 5b 32 5d 5b 32 5d 20 3d 20 = 1; x[2][2] =
0890: 31 3b 0a 20 20 20 65 2b 2b 3b 0a 20 20 20 66 6f 1;. e++;. fo
08a0: 72 28 3b 65 3b 78 3d 4d 41 54 4d 55 4c 28 78 2c r(;e;x=MATMUL(x,
08b0: 78 29 2c 65 3e 3e 3d 31 29 0a 20 20 20 20 20 20 x),e>>=1).
08c0: 69 66 28 65 26 31 29 0a 20 20 20 20 20 20 20 20 if(e&1).
08d0: 20 76 20 3d 20 4d 41 54 4d 55 4c 28 76 2c 20 78 v = MATMUL(v, x
08e0: 29 3b 0a 20 20 20 72 65 74 75 72 6e 20 76 5b 32 );. return v[2
08f0: 5d 5b 30 5d 3b 0a 7d 0a ][0];.}.