#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cctype>

#include <algorithm>
#include <random>
#include <bitset>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <vector>
#include <chrono>
#include <iostream>
#include <limits>
#include <numeric>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

typedef vector<int> vi;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template <class T>
istream& operator>>(istream& is, vector<T>& v) {
  for (T& x : v)
    is >> x;
  return is;
}

template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  if (!v.empty()) {
    os << v.front();
    for (int i = 1; i < v.size(); ++i)
      os << ' ' << v[i];
  }
  return os;
}

const int P = 1000000007;

struct Simple {
  int n;
  vector<int> fac, ifac, inv;

  void build(int n) {
    this->n = n;
    fac.resize(n + 1);
    ifac.resize(n + 1);
    inv.resize(n + 1);
    fac[0] = 1;
    for (int x = 1; x <= n; ++x)
      fac[x] = fac[x - 1] * (ll)x % P;
    inv[1] = 1;
    for (int x = 2; x <= n; ++x)
      inv[x] = -(P / x) * (ll)inv[P % x] % P + P;
    ifac[0] = 1;
    for (int x = 1; x <= n; ++x)
      ifac[x] = ifac[x - 1] * (ll)inv[x] % P;
  }

  Simple() {
    build(1);
  }

  void check(int k) {
    int nn = n;
    if (k > nn) {
      while (k > nn)
        nn <<= 1;
      build(nn);
    }
  }

  int gfac(int k) {
    check(k);
    return fac[k];
  }

  int gifac(int k) {
    check(k);
    return ifac[k];
  }

  int ginv(int k) {
    check(k);
    return inv[k];
  }

  int binom(int n, int m) {
    if (m < 0 || m > n)
      return 0;
    return gfac(n) * (ll)gifac(m) % P * gifac(n - m) % P;
  }
} simp;

int norm(int x) { return x >= P ? x - P : x; }

void add(int& x, int y) {
  (x += y) >= P ? (x -= P) : 0;
}

void sub(int& x, int y) {
  (x -= y) < 0 ? (x += P) : 0;
}

int mpow(int x, int k, int p = P) {
  int ret = 1;
  while (k) {
    if (k & 1)
      ret = ret * (ll)x % p;
    x = x * (ll)x % p;
    k >>= 1;
  }
  return ret;
}

int main() {
#ifdef LBT
  freopen("test.in", "r", stdin);
  int nol_cl = clock();
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;
  vi dp(3);
  dp[0] = 1;
  int ans = 0;
  function<int(int, int)> f = [&](int n, int k) {
    return simp.ginv(k) * (ll)simp.gifac(n) % P;
  };
  for (int i = 1; i <= n; ++i) {
    vi newDp(3);
    int tot = norm(norm(dp[0] + dp[1]) + dp[2]);
    for (int j = 0; j < 3; ++j)
      newDp[j] = norm(tot + P - dp[j]);
    dp = newDp;
    ans = (ans + dp[1] * (ll)simp.binom(n, i) % P * f(n, i)) % P;
  }
  ans = ans * (ll)simp.gfac(n - 1) % P;
  ans = ans * (ll)mpow(3, P - 1 - n) % P;
  cout << ans;

#ifdef LBT
  LOG("Time: %dms\n", int ((clock()
          -nol_cl) / (double)CLOCKS_PER_SEC * 1000));
#endif
  return 0;
}

### Prompt

Develop a solution in Cpp to the problem described below:

We have a round pizza. Snuke wants to eat one third of it, or something as close as possible to that.

He decides to cut this pizza as follows.

First, he divides the pizza into N pieces by making N cuts with a knife. The knife can make a cut along the segment connecting the center of the pizza and some point on the circumference of the pizza. However, he is very poor at handling knives, so the cuts are made at uniformly random angles, independent from each other.

Then, he chooses one or more consecutive pieces so that the total is as close as possible to one third of the pizza, and eat them. (Let the total be x of the pizza. He chooses consecutive pieces so that |x - 1/3| is minimized.)

Find the expected value of |x - 1/3|. It can be shown that this value is rational, and we ask you to print it modulo 10^9 + 7, as described in Notes.

Constraints

* 2 \leq N \leq 10^6

Input

Input is given from Standard Input in the following format:


N


Output

Print the expected value of |x - 1/3| modulo 10^9 + 7, as described in Notes.

Examples

Input

2


Output

138888890


Input

3


Output

179012347


Input

10


Output

954859137


Input

1000000


Output

44679646

### Response

```cpp
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cctype>

#include <algorithm>
#include <random>
#include <bitset>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <vector>
#include <chrono>
#include <iostream>
#include <limits>
#include <numeric>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

typedef vector<int> vi;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template <class T>
istream& operator>>(istream& is, vector<T>& v) {
  for (T& x : v)
    is >> x;
  return is;
}

template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  if (!v.empty()) {
    os << v.front();
    for (int i = 1; i < v.size(); ++i)
      os << ' ' << v[i];
  }
  return os;
}

const int P = 1000000007;

struct Simple {
  int n;
  vector<int> fac, ifac, inv;

  void build(int n) {
    this->n = n;
    fac.resize(n + 1);
    ifac.resize(n + 1);
    inv.resize(n + 1);
    fac[0] = 1;
    for (int x = 1; x <= n; ++x)
      fac[x] = fac[x - 1] * (ll)x % P;
    inv[1] = 1;
    for (int x = 2; x <= n; ++x)
      inv[x] = -(P / x) * (ll)inv[P % x] % P + P;
    ifac[0] = 1;
    for (int x = 1; x <= n; ++x)
      ifac[x] = ifac[x - 1] * (ll)inv[x] % P;
  }

  Simple() {
    build(1);
  }

  void check(int k) {
    int nn = n;
    if (k > nn) {
      while (k > nn)
        nn <<= 1;
      build(nn);
    }
  }

  int gfac(int k) {
    check(k);
    return fac[k];
  }

  int gifac(int k) {
    check(k);
    return ifac[k];
  }

  int ginv(int k) {
    check(k);
    return inv[k];
  }

  int binom(int n, int m) {
    if (m < 0 || m > n)
      return 0;
    return gfac(n) * (ll)gifac(m) % P * gifac(n - m) % P;
  }
} simp;

int norm(int x) { return x >= P ? x - P : x; }

void add(int& x, int y) {
  (x += y) >= P ? (x -= P) : 0;
}

void sub(int& x, int y) {
  (x -= y) < 0 ? (x += P) : 0;
}

int mpow(int x, int k, int p = P) {
  int ret = 1;
  while (k) {
    if (k & 1)
      ret = ret * (ll)x % p;
    x = x * (ll)x % p;
    k >>= 1;
  }
  return ret;
}

int main() {
#ifdef LBT
  freopen("test.in", "r", stdin);
  int nol_cl = clock();
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;
  vi dp(3);
  dp[0] = 1;
  int ans = 0;
  function<int(int, int)> f = [&](int n, int k) {
    return simp.ginv(k) * (ll)simp.gifac(n) % P;
  };
  for (int i = 1; i <= n; ++i) {
    vi newDp(3);
    int tot = norm(norm(dp[0] + dp[1]) + dp[2]);
    for (int j = 0; j < 3; ++j)
      newDp[j] = norm(tot + P - dp[j]);
    dp = newDp;
    ans = (ans + dp[1] * (ll)simp.binom(n, i) % P * f(n, i)) % P;
  }
  ans = ans * (ll)simp.gfac(n - 1) % P;
  ans = ans * (ll)mpow(3, P - 1 - n) % P;
  cout << ans;

#ifdef LBT
  LOG("Time: %dms\n", int ((clock()
          -nol_cl) / (double)CLOCKS_PER_SEC * 1000));
#endif
  return 0;
}

```