class SquareFreeString():
	def isSquareFree(self,s):
		return any((lambda w: len(w)%2 == 0 and w[:len(w)/2] == w[len(w)/2:])(s[i:i+j]) for j in range(1,len(s)+1) for i in range(len(s)-j+1)) * "No" or "Yes"

  public static int getMinimalSize(int[] a) {
    int n = a.length;
    int[] b = new int[n];
    for (int i = 0; i < n; ++i)
      b[i] = a[i];

    Arrays.sort(b);

    int ans = n;
    for (int i = 0; i < n; ++i)
      if (a[i] == b[i])
        --ans;

    return ans;
  }

  public static String get(int n, int m) {
    long full = (1l << m) - 1;
    long mask = full;

    for (int i = 0; i <= n; ++i) {
      int win;
      if (Integer.bitCount(i) % 2 == 1 || mask != full)
        win = 1;
      else
        win = 0;

      mask = ((mask << 1) | win) & full;
    }
    
    return (mask & 1) == 1 ? "Alice" : "Bob";
  }

class PartisanGame():
	def getWinner(self,n,a,b):
		a = list(a)
		b = list(b)
		if n == 0: return "Bob"
		MAXK = 5
		lw = (1<<(MAXK<<1))
		def getNext(mask):
			amask = mask >> MAXK
			bmask = mask & ((1<<MAXK)-1)
			winA = not all(bmask&(1<<(MAXK-w)) for w in a)
			winB = not all(amask&(1<<(MAXK-w)) for w in b)
			amask = (amask>>1) | (winA << (MAXK-1))
			bmask = (bmask>>1) | (winB << (MAXK-1))
			return (amask << MAXK) | bmask
			
		def mult(p,q):
			return [p[q[i]] for i in xrange(lw)]

		perm = [getNext(i) for i in xrange(lw)]
		ret = [i for i in xrange(lw)]

		n += 1
		while n > 0:
			if n % 2 == 1:
				ret = mult(ret, perm)
			perm = mult(perm, perm)
			n >>= 1

		return (ret[lw-1] >> (2*MAXK-1)) * "Alice" or "Bob"

public static long count(String s, String p) {
    int n = s.length();
    int m = p.length();
    long[][] d = new long[n + 1][n + 1];

    d[0][0] = 1;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j <= i; ++j) {
        int l = j;
        int r = n - 1 - (i - j);

        if (l >= m || s.charAt(i) == p.charAt(l))
          d[i + 1][j + 1] += d[i][j];

        if (r >= m || s.charAt(i) == p.charAt(r))
          d[i + 1][j] += d[i][j];
      }
    }

    long ans = 0;
    for (int j = 0; j <= n; ++j)
      ans += d[n][j];

    return ans;
  }

  public static String getKth(String s, long k) {
    --k;
    int n = s.length();
    String ans = "";

    for (int i = 0; i < n; ++i) {
      for (char c = 'a'; c <= 'z'; ++c) {
        String p = ans + Character.toString(c);

        long cnt = count(s, p); 
        if (cnt <= k) {
          k -= cnt;
        } else {
          ans = ans + Character.toString(c);
          break;
        }
      }
    }
    
    return ans;
  }

  public static int add(int x, int y) {
    x += y;
    if (x >= mod)
      x -= mod;
    return x;
  }

  public static int sub(int x, int y) {
    x -= y;
    if (x < 0)
      x += mod;
    return x;
  }

  public static int mul(int x, int y) {
    long p = (long) x * (long) y % mod;
    return (int) p;
  }

  public static int binpow(int x, int to) {
    int y = 1;
    while (to > 0) {
      if ((to & 1) == 1)
        y = mul(x, y);
      x = mul(x, x);
      to >>= 1;
    }
    return y;
  }

  public static int inv(int x) {
    assert(x != 0);
    return binpow(x, mod - 2);
  }

  private static class Matrix {
    int n;
    int[][] a;

    public Matrix(int size) {
      n = size;
      a = new int[n][n];
    } 

    public Matrix one() {
      Matrix ans = new Matrix(n);
      for (int i = 0; i < n; ++i)
        ans.a[i][i] = 1;
      return ans;
    }

    public Matrix mul(Matrix other) {
      Matrix ans = new Matrix(n);
      for (int i = 0; i < n; ++i)
        for (int k = 0; k < n; ++k)
          for (int j = 0; j < n; ++j)
            ans.a[i][j] = add(ans.a[i][j], FibonacciStringSum.mul(a[i][k], other.a[k][j]));
      return ans;
    }
  }

  public static Matrix binpow(Matrix x, int to) {
    Matrix y = x.one();
    while (to > 0) {
      if ((to & 1) == 1)
        y = y.mul(x);
      x = x.mul(x);
      to >>= 1;
    }
    return y;
  }

  public static int[] getCoefficients(int n) {
    int[] a = new int [2 * n + 1];
    a[0] = 1;
    for (int i = 0; i < n; ++i) {
      for (int j = 2 * n; j >= 0; --j) {
        int nw = sub(0, a[j]);
        if (j >= 1)
          nw = sub(nw, a[j - 1]);
        if (j >= 2)
          nw = add(nw, a[j - 2]);
        a[j] = nw;
      }
    }
    return a;
  }

  public static int[] getSequence(int cnt, int a, int b) {
    int[] fact = new int[cnt + 1];
    int[] ans = new int[cnt];
    fact[0] = 1;
    for (int i = 1; i < fact.length; ++i)
      fact[i] = mul(i, fact[i - 1]);

    BiFunction<Integer, Integer, Integer> binom = (Integer n, Integer k) -> {
      if (n < 0 || k < 0 || n < k)
        return 0;
      int res = fact[n];
      res = mul(res, inv(fact[k]));
      res = mul(res, inv(fact[n - k]));
      return res;
    };

    for (int n = 0; n < cnt; ++n) {
      for (int k = 0; 2 * k - 1 <= n; ++k) {
        int bon = binom.apply(n - k + 1, k);
        bon = mul(bon, binpow(k, b));
        bon = mul(bon, binpow(n - k, a));
        ans[n] = add(ans[n], bon);
      }
    }

    return ans;
  }

  public static int get(int n, int a, int b) {
    int m = a + b + 1;
    int[] c = getCoefficients(m);
    int depth = c.length - 1;

    Matrix A = new Matrix(depth);
    for (int i = 0; i < depth; ++i)
      A.a[0][i] = sub(0, c[depth - i - 1]);
    for (int i = 1; i < depth; ++i)
      A.a[i][i - 1] = 1;

    A = binpow(A, n);

    int[] seq = getSequence(depth, a, b);

    int ans = 0;
    for (int i = 0; i < depth; ++i)
      ans = add(ans, mul(A.a[depth - 1][i], seq[depth - i - 1]));

    return ans;
  }