const int n = 2;
struct Mat {
  int m[n][n];
  Mat(int x = 0) {
    memset(m, 0, sizeof m);
    for (int i = 0; i < n; i++) m[i][i] = x;
  }
  int* operator[](int y) { return m[y]; }
  const int* operator[](int y) const { return m[y]; }
};
Mat operator*(const Mat &a, const Mat &b) {
  Mat res;
  for (int i = 0; i < n; i++)
  for (int j = 0; j < n; j++) {
    ll sum = 0;
    for (int k = 0; k < m; k++)
      sum += a[i][k] * b[k][j];
    res[i][j] = sum % MOD;
  }
  return res;
}

Mat a; ll b;
Mat res = 1;
for (; b; b >>= 1, a = a * a)
  if (b & 1) res = res * a;