Problem 422: Sequence of Points on a Hyperbola

Project Euler Problem 422 Solution

EulerSolve provides an optimized solution for Project Euler Problem 422, Sequence of Points on a Hyperbola, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary The sequence defines rational points $P_n=(x_n,y_n)$ on one fixed hyperbola. If $$x_n=\frac{a_n}{b_n},\qquad y_n=\frac{c_n}{d_n}$$ are written in lowest terms with positive denominators, the required value is the checksum $$C_n \equiv a_n+b_n+c_n+d_n \pmod{10^9+7}.$$ The hard part is that the target index is enormous, so a direct rational simulation of the recurrence is useless. The implementations instead extract a closed form for the point coordinates and evaluate that form purely modulo $10^9+7$. Mathematical Approach Step 1: A Rational Parameter of the Hyperbola The implementations begin with the auxiliary sequence $$u_1=100,\qquad u_2=-\frac{75}{2},\qquad u_n=\frac{25u_{n-2}}{u_{n-1}}\qquad (n\ge 3).$$ The point coordinates are then reconstructed by $$x_n=\frac{3u_n^2+2500}{25u_n},\qquad y_n=\frac{4u_n^2-1875}{25u_n}.$$ These formulas immediately yield two useful linear combinations: $$3x_n+4y_n=u_n,\qquad 4x_n-3y_n=\frac{625}{u_n}.$$ Multiplying them gives $$\boxed{(3x_n+4y_n)(4x_n-3y_n)=625,}$$ so every $P_n$ lies on the same hyperbola. The sequence $u_n$ is therefore a rational parameter of that curve....

Detailed mathematical approach

Problem Summary

The sequence defines rational points $P_n=(x_n,y_n)$ on one fixed hyperbola. If

$$x_n=\frac{a_n}{b_n},\qquad y_n=\frac{c_n}{d_n}$$

are written in lowest terms with positive denominators, the required value is the checksum

$$C_n \equiv a_n+b_n+c_n+d_n \pmod{10^9+7}.$$

The hard part is that the target index is enormous, so a direct rational simulation of the recurrence is useless. The implementations instead extract a closed form for the point coordinates and evaluate that form purely modulo $10^9+7$.

Mathematical Approach

Step 1: A Rational Parameter of the Hyperbola

The implementations begin with the auxiliary sequence

$$u_1=100,\qquad u_2=-\frac{75}{2},\qquad u_n=\frac{25u_{n-2}}{u_{n-1}}\qquad (n\ge 3).$$

The point coordinates are then reconstructed by

$$x_n=\frac{3u_n^2+2500}{25u_n},\qquad y_n=\frac{4u_n^2-1875}{25u_n}.$$

These formulas immediately yield two useful linear combinations:

$$3x_n+4y_n=u_n,\qquad 4x_n-3y_n=\frac{625}{u_n}.$$

Multiplying them gives

$$\boxed{(3x_n+4y_n)(4x_n-3y_n)=625,}$$

so every $P_n$ lies on the same hyperbola. The sequence $u_n$ is therefore a rational parameter of that curve.

Step 2: Remove the Constant Factor $25$

Set

$$q_n=\frac{u_n}{25}.$$

Then the recurrence simplifies to

$$q_1=4,\qquad q_2=-\frac{3}{2},\qquad q_n=\frac{q_{n-2}}{q_{n-1}}\qquad (n\ge 3).$$

This normalized form is the key observation: only the primes $2$ and $3$ appear, so the whole problem becomes a recurrence on exponents and signs.

Step 3: Exponent Recurrences Become Fibonacci and Lucas

Write each term as

$$q_n=\varepsilon_n\,2^{a_n}3^{b_n},\qquad \varepsilon_n\in\{-1,+1\},$$

where negative exponents simply mean factors in the denominator. Taking $2$-adic and $3$-adic valuations in

$$q_n=\frac{q_{n-2}}{q_{n-1}}$$

gives the linear recurrences

$$a_n=a_{n-2}-a_{n-1},\qquad b_n=b_{n-2}-b_{n-1},$$

with initial values

$$a_1=2,\ a_2=-1,\qquad b_1=0,\ b_2=1.$$

Now define

$$A_n=(-1)^{n+1}a_n,\qquad B_n=(-1)^n b_n.$$

Then both sequences satisfy the ordinary Fibonacci recurrence

$$A_n=A_{n-1}+A_{n-2},\qquad B_n=B_{n-1}+B_{n-2}.$$

The initial values identify them uniquely as

$$A_n=L_{n-1},\qquad B_n=F_{n-1},$$

where $F_k$ and $L_k$ are the Fibonacci and Lucas numbers with

$$F_0=0,\ F_1=1,\qquad L_0=2,\ L_1=1.$$

Therefore

$$a_n=(-1)^{n+1}L_{n-1},\qquad b_n=(-1)^nF_{n-1}.$$

The sign follows the same recurrence: from $q_n=q_{n-2}/q_{n-1}$ we get

$$\varepsilon_n=\varepsilon_{n-2}\varepsilon_{n-1},\qquad \varepsilon_1=+1,\ \varepsilon_2=-1,$$

$$\varepsilon_n=(-1)^{F_{n-1}}.$$

Step 4: Closed Forms for $u_n$, $x_n$, and $y_n$

Let $k=n-1$ and define

$$\sigma=(-1)^{F_k}.$$

Then the normalized recurrence has the exact solution

$$q_n=\sigma\begin{cases} \dfrac{2^{L_k}}{3^{F_k}}, & n \text{ odd},\\[6pt] \dfrac{3^{F_k}}{2^{L_k}}, & n \text{ even}. \end{cases}$$

Multiplying by $25$ gives the auxiliary parameter

$$u_n=25q_n=25\sigma\begin{cases} \dfrac{2^{L_k}}{3^{F_k}}, & n \text{ odd},\\[6pt] \dfrac{3^{F_k}}{2^{L_k}}, & n \text{ even}. \end{cases}$$

To make the coordinate formulas symmetric, define $(\alpha,\beta)$ by parity:

$$n \text{ odd}: \alpha=2^{L_k},\ \beta=3^{F_k},\qquad n \text{ even}: \alpha=3^{F_k},\ \beta=2^{L_k}.$$

Then in both cases $u_n=25\sigma\alpha/\beta$, and substitution into the coordinate formulas yields

$$\boxed{x_n=\sigma\frac{3\alpha^2+4\beta^2}{\alpha\beta},\qquad y_n=\sigma\frac{4\alpha^2-3\beta^2}{\alpha\beta}.}$$

This is the exact algebraic form used by the modular solver.

Step 5: Reduce the Fractions to Lowest Terms

The checksum uses reduced fractions, so we must know the common factors of each raw numerator with the raw denominator $\alpha\beta$.

For odd $n$, $\alpha$ is a power of $2$ and $\beta$ is a power of $3$. When $n\ge 3$, $\alpha$ is divisible by $8$ and $\beta$ is divisible by $3$. Then:

$$3\alpha^2+4\beta^2\ \text{is divisible by}\ 12,$$

but after dividing by $12$ the result is odd and not divisible by $3$, so no larger common factor with $\alpha\beta$ remains. By contrast,

$$4\alpha^2-3\beta^2\equiv 1 \pmod 3,\qquad 4\alpha^2-3\beta^2\equiv 5 \pmod 8,$$

so it is coprime to $\alpha\beta$. Hence

$$\gcd(3\alpha^2+4\beta^2,\alpha\beta)=\begin{cases}4,&n=1,\\12,&n\ge 3\text{ odd},\end{cases}\qquad \gcd(4\alpha^2-3\beta^2,\alpha\beta)=1\ \text{for odd }n.$$

For even $n$, the roles of powers of $2$ and $3$ are reversed. Then $3\alpha^2+4\beta^2$ is odd and congruent to $1 \pmod 3$, so it is already reduced. The other numerator has exactly one factor $3$, and for $n\ge 4$ exactly two factors of $2$:

$$\gcd(3\alpha^2+4\beta^2,\alpha\beta)=1\ \text{for even }n,$$

$$\gcd(4\alpha^2-3\beta^2,\alpha\beta)=\begin{cases}6,&n=2,\\12,&n\ge 4\text{ even}.\end{cases}$$

These fixed divisors are exactly the small reductions used before the checksum is formed.

Step 6: Worked Example at $n=7$

This index is one of the implementation checkpoints. Here $k=6$, so

$$F_6=8,\qquad L_6=18,\qquad \sigma=(-1)^8=1.$$

Because $7$ is odd, we take

$$\alpha=2^{18}=262144,\qquad \beta=3^8=6561.$$

Then

$$x_7=\frac{3\alpha^2+4\beta^2}{\alpha\beta}=\frac{206330617092}{1719926784}=\frac{17194218091}{143327232},$$

where the reduction factor is $12$, and

$$y_7=\frac{4\alpha^2-3\beta^2}{\alpha\beta}=\frac{274748766781}{1719926784},$$

which is already reduced. These are exactly the rational checkpoint values used to verify the formula.

Step 7: Pure Modular Evaluation for Huge $n$

Let $M=10^9+7$. Since $M$ is prime and neither $2$ nor $3$ is divisible by $M$, Fermat's little theorem allows exponent reduction modulo

$$M-1=10^9+6.$$

So the implementation computes $F_k$ and $F_{k+1}$ modulo $M-1$, then derives

$$L_k=2F_{k+1}-F_k.$$

The Fibonacci pair is obtained by fast doubling:

$$F_{2m}=F_m(2F_{m+1}-F_m),\qquad F_{2m+1}=F_m^2+F_{m+1}^2.$$

Once $F_k$ and $L_k$ are known modulo $M-1$, the powers $2^{L_k}$ and $3^{F_k}$ are computed modulo $M$. Division by $4$, $6$, or $12$ is replaced by multiplication with modular inverses:

$$a^{-1}\equiv a^{M-2}\pmod M.$$

The sign is also cheap: Fibonacci parity has period $3$, so $F_k$ is even exactly when $k\equiv 0\pmod 3$. Therefore $\sigma=+1$ in that case and $\sigma=-1$ otherwise.

How the Code Works

The C++, Python, and Java implementations all follow the same pipeline. They compute $k=n-1$, obtain $F_k$ and $F_{k+1}$ by fast doubling modulo $10^9+6$, recover $L_k$, choose the correct parity branch for $(\alpha,\beta)$, form the two raw numerators and the common raw denominator modulo $10^9+7$, divide by the known reduction factors with modular inverses, and finally add the four reduced pieces. The C++ implementation also checks the formula against exact rational arithmetic for small indices, which confirms that the modular shortcut is mathematically exact.

Complexity Analysis

Fast doubling computes Fibonacci data in $O(\log n)$ time. Modular exponentiation also costs $O(\log M)$, which is constant-sized compared with the growth of $n$. The overall solver therefore runs in $O(\log n)$ time and $O(1)$ memory. That is why an index as large as $11^{14}$ is completely feasible.

Footnotes and References

Problem page: https://projecteuler.net/problem=422
Fibonacci numbers: Wikipedia — Fibonacci number
Lucas numbers: Wikipedia — Lucas number
Hyperbola: Wikipedia — Hyperbola
Modular multiplicative inverse: Wikipedia — Modular multiplicative inverse

Problem 422 source code

C++

#include <algorithm>
#include <atomic>
#include <cstdint>
#include <iostream>
#include <mutex>
#include <string>
#include <thread>
#include <utility>
#include <vector>

#include <boost/multiprecision/cpp_int.hpp>

using boost::multiprecision::cpp_int;
using namespace std;

namespace {

constexpr int64_t MOD = 1'000'000'007LL;
constexpr int64_t MOD_EXP = MOD - 1;

int64_t mul_mod(int64_t a, int64_t b, int64_t mod) {
  return static_cast<int64_t>((__int128)a * b % mod);
}

int64_t mod_pow(int64_t base, int64_t exp, int64_t mod) {
  int64_t result = 1 % mod;
  int64_t cur = (base % mod + mod) % mod;
  while (exp > 0) {
    if (exp & 1LL) {
      result = mul_mod(result, cur, mod);
    }
    cur = mul_mod(cur, cur, mod);
    exp >>= 1LL;
  }
  return result;
}

int64_t mod_inv(int64_t x) { return mod_pow(x, MOD - 2, MOD); }

pair<int64_t, int64_t> fib_pair_mod(uint64_t n, int64_t mod) {
  if (n == 0) {
    return {0, 1 % mod};
  }
  auto [a, b] = fib_pair_mod(n >> 1, mod); // a=F(k), b=F(k+1)
  int64_t two_b_minus_a = (2 * b - a) % mod;
  if (two_b_minus_a < 0) {
    two_b_minus_a += mod;
  }
  int64_t c = mul_mod(a, two_b_minus_a, mod);                 // F(2k)
  int64_t d = (mul_mod(a, a, mod) + mul_mod(b, b, mod)) % mod; // F(2k+1)
  if (n & 1ULL) {
    return {d, (c + d) % mod};
  }
  return {c, d};
}

uint64_t pow_u64(uint64_t base, uint32_t exp) {
  uint64_t result = 1;
  while (exp > 0) {
    if (exp & 1U) {
      result *= base;
    }
    base *= base;
    exp >>= 1U;
  }
  return result;
}

struct Rational {
  cpp_int num;
  cpp_int den;

  Rational() : num(0), den(1) {}
  Rational(long long n) : num(n), den(1) {}
  Rational(cpp_int n, cpp_int d) : num(std::move(n)), den(std::move(d)) {
    normalize();
  }

  static cpp_int abs_int(cpp_int v) {
    if (v < 0) {
      v = -v;
    }
    return v;
  }

  static cpp_int gcd_int(cpp_int a, cpp_int b) {
    a = abs_int(a);
    b = abs_int(b);
    while (b != 0) {
      cpp_int t = a % b;
      a = b;
      b = t;
    }
    return a;
  }

  void normalize() {
    if (den == 0) {
      throw runtime_error("Zero denominator in Rational.");
    }
    if (den < 0) {
      num = -num;
      den = -den;
    }
    cpp_int g = gcd_int(num, den);
    num /= g;
    den /= g;
  }
};

Rational operator+(const Rational &a, const Rational &b) {
  return Rational(a.num * b.den + b.num * a.den, a.den * b.den);
}

Rational operator-(const Rational &a, const Rational &b) {
  return Rational(a.num * b.den - b.num * a.den, a.den * b.den);
}

Rational operator*(const Rational &a, const Rational &b) {
  return Rational(a.num * b.num, a.den * b.den);
}

Rational operator/(const Rational &a, const Rational &b) {
  return Rational(a.num * b.den, a.den * b.num);
}

struct ExactPoint {
  Rational x;
  Rational y;
};

Rational exact_u_n(uint64_t n) {
  if (n == 1) {
    return Rational(100);
  }
  if (n == 2) {
    return Rational(-75, 2);
  }

  Rational u_im2(100);
  Rational u_im1(cpp_int(-75), cpp_int(2));
  Rational u_i;
  for (uint64_t i = 3; i <= n; ++i) {
    u_i = Rational(25) * u_im2 / u_im1; // u_i = 25*u_{i-2}/u_{i-1}
    u_im2 = u_im1;
    u_im1 = u_i;
  }
  return u_im1;
}

ExactPoint exact_point(uint64_t n) {
  Rational u = exact_u_n(n);
  Rational uu = u * u;
  Rational x = (Rational(3) * uu + Rational(2500)) / (Rational(25) * u);
  Rational y = (Rational(4) * uu - Rational(1875)) / (Rational(25) * u);
  return {x, y};
}

int64_t cpp_mod(const cpp_int &v, int64_t mod) {
  cpp_int r = v % mod;
  if (r < 0) {
    r += mod;
  }
  return static_cast<int64_t>(r);
}

int64_t exact_checksum_mod(uint64_t n) {
  ExactPoint p = exact_point(n);
  int64_t a = cpp_mod(p.x.num, MOD);
  int64_t b = cpp_mod(p.x.den, MOD);
  int64_t c = cpp_mod(p.y.num, MOD);
  int64_t d = cpp_mod(p.y.den, MOD);
  return (a + b + c + d) % MOD;
}

int64_t solve_checksum_mod(uint64_t n) {
  if (n == 0) {
    throw runtime_error("n must be >= 1");
  }

  const uint64_t k = n - 1;
  auto [fk_mod, fk1_mod] = fib_pair_mod(k, MOD_EXP); // F_k, F_{k+1}
  const int64_t F = fk_mod;
  int64_t L = (2 * fk1_mod - fk_mod) % MOD_EXP; // Lucas_k
  if (L < 0) {
    L += MOD_EXP;
  }

  const int sign = (k % 3ULL == 0ULL) ? +1 : -1; // (-1)^{F_k}

  const int64_t two_pow_L = mod_pow(2, L, MOD);
  const int64_t three_pow_F = mod_pow(3, F, MOD);

  int64_t alpha;
  int64_t beta;
  int64_t g1;
  int64_t g2;

  if (n & 1ULL) {
    // odd n: alpha=2^L, beta=3^F
    alpha = two_pow_L;
    beta = three_pow_F;
    g1 = (n == 1 ? 4 : 12);
    g2 = 1;
  } else {
    // even n: alpha=3^F, beta=2^L
    alpha = three_pow_F;
    beta = two_pow_L;
    g1 = 1;
    g2 = (n == 2 ? 6 : 12);
  }

  const int64_t alpha2 = mul_mod(alpha, alpha, MOD);
  const int64_t beta2 = mul_mod(beta, beta, MOD);

  int64_t n1 = (3 * alpha2 + 4 * beta2) % MOD; // for x numerator (pre-reduction)
  int64_t n2 = (4 * alpha2 - 3 * beta2) % MOD; // for y numerator (pre-reduction)
  if (n2 < 0) {
    n2 += MOD;
  }

  const int64_t d_base = mul_mod(two_pow_L, three_pow_F, MOD); // 2^L * 3^F

  int64_t a = mul_mod(n1, mod_inv(g1), MOD);
  int64_t b = mul_mod(d_base, mod_inv(g1), MOD);
  int64_t c = mul_mod(n2, mod_inv(g2), MOD);
  int64_t d = mul_mod(d_base, mod_inv(g2), MOD);

  if (sign < 0) {
    a = (MOD - a) % MOD;
    c = (MOD - c) % MOD;
  }

  return (a + b + c + d) % MOD;
}

bool same_fraction(const Rational &r, long long num, long long den) {
  return r.num == num && r.den == den;
}

bool validate_given_points() {
  struct Check {
    uint64_t n;
    long long x_num;
    long long x_den;
    long long y_num;
    long long y_den;
  };

  const vector<Check> checks = {
      {3, -19, 2, -229, 24},
      {4, 1267, 144, -37, 12},
      {7, 17194218091LL, 143327232LL, 274748766781LL, 1719926784LL},
  };

  for (const auto &ch : checks) {
    ExactPoint p = exact_point(ch.n);
    if (!same_fraction(p.x, ch.x_num, ch.x_den) ||
        !same_fraction(p.y, ch.y_num, ch.y_den)) {
      cerr << "Checkpoint failed at n=" << ch.n << "\n";
      cerr << "Expected x=" << ch.x_num << "/" << ch.x_den << ", y=" << ch.y_num
           << "/" << ch.y_den << "\n";
      cerr << "Got x=" << p.x.num << "/" << p.x.den << ", y=" << p.y.num << "/"
           << p.y.den << "\n";
      return false;
    }
  }

  if (solve_checksum_mod(7) != 806236837LL) {
    cerr << "Checkpoint failed: checksum(n=7) mismatch.\n";
    return false;
  }

  return true;
}

bool validate_parallel_exact_vs_fast(int max_n) {
  atomic<int> next_n{1};
  atomic<bool> ok{true};
  mutex err_mutex;
  vector<string> errors;

  int thread_count = static_cast<int>(thread::hardware_concurrency());
  if (thread_count <= 0) {
    thread_count = 4;
  }
  thread_count = min(thread_count, max_n);
  thread_count = max(thread_count, 1);

  auto worker = [&]() {
    while (true) {
      int n = next_n.fetch_add(1);
      if (n > max_n) {
        break;
      }
      int64_t fast_val = solve_checksum_mod(static_cast<uint64_t>(n));
      int64_t exact_val = exact_checksum_mod(static_cast<uint64_t>(n));
      if (fast_val != exact_val) {
        ok.store(false);
        lock_guard<mutex> lock(err_mutex);
        errors.push_back("Mismatch at n=" + to_string(n) + ": fast=" +
                         to_string(fast_val) + ", exact=" +
                         to_string(exact_val));
      }
    }
  };

  vector<thread> threads;
  threads.reserve(thread_count);
  for (int i = 0; i < thread_count; ++i) {
    threads.emplace_back(worker);
  }
  for (auto &t : threads) {
    t.join();
  }

  if (!ok.load()) {
    for (const string &s : errors) {
      cerr << s << "\n";
    }
    return false;
  }
  return true;
}

bool validate_all() {
  if (!validate_given_points()) {
    return false;
  }
  if (!validate_parallel_exact_vs_fast(15)) {
    return false;
  }
  return true;
}

} // namespace

int main(int argc, char **argv) {
  uint64_t n = pow_u64(11, 14);
  bool run_validation = true;

  for (int i = 1; i < argc; ++i) {
    string arg = argv[i];
    if (arg == "--no-validate") {
      run_validation = false;
    } else {
      n = stoull(arg);
    }
  }

  if (run_validation) {
    if (!validate_all()) {
      return 1;
    }
    cout << "Validation passed (P3, P4, P7, checksum(7), and n<=15 cross-check)."
         << "\n";
  }

  const int64_t answer = solve_checksum_mod(n);
  cout << answer << "\n";
  cout << "Answer: " << answer << "\n";
  return 0;
}

Python

def mod_pow(base, exp, mod):
    return pow(base, exp, mod)

def mod_inv(x, mod):
    return pow(x, mod - 2, mod)

def fib_pair_mod(n, mod):
    if n == 0:
        return 0, 1
    a, b = fib_pair_mod(n >> 1, mod)
    c = a * (2 * b - a) % mod
    d = (a * a + b * b) % mod
    if n & 1:
        return d, (c + d) % mod
    return c, d

def solve_checksum_mod(n):
    MOD = 1000000007
    MOD_EXP = MOD - 1
    
    k = n - 1
    fk_mod, fk1_mod = fib_pair_mod(k, MOD_EXP)
    F = fk_mod
    L = (2 * fk1_mod - fk_mod) % MOD_EXP
    
    sign = 1 if (k % 3 == 0) else -1
    
    two_pow_L = mod_pow(2, L, MOD)
    three_pow_F = mod_pow(3, F, MOD)
    
    if n & 1:
        alpha = two_pow_L
        beta = three_pow_F
        g1 = 4 if n == 1 else 12
        g2 = 1
    else:
        alpha = three_pow_F
        beta = two_pow_L
        g1 = 1
        g2 = 6 if n == 2 else 12
        
    alpha2 = (alpha * alpha) % MOD
    beta2 = (beta * beta) % MOD
    
    n1 = (3 * alpha2 + 4 * beta2) % MOD
    n2 = (4 * alpha2 - 3 * beta2) % MOD
    
    d_base = (two_pow_L * three_pow_F) % MOD
    
    a = (n1 * mod_inv(g1, MOD)) % MOD
    b = (d_base * mod_inv(g1, MOD)) % MOD
    c = (n2 * mod_inv(g2, MOD)) % MOD
    d = (d_base * mod_inv(g2, MOD)) % MOD
    
    if sign < 0:
        a = (-a) % MOD
        c = (-c) % MOD
        
    return str((a + b + c + d) % MOD)

def solve():
    return solve_checksum_mod(11**14)

if __name__ == '__main__':
    print(solve())

Java

public class Euler422 {
    private static final long MOD = 1000000007L;
    private static final long MOD_EXP = MOD - 1L;

    private static long modPow(long base, long exp, long mod) {
        long result = 1;
        long cur = (base % mod + mod) % mod;
        while (exp > 0) {
            if ((exp & 1) != 0) {
                result = (result * cur) % mod;
            }
            cur = (cur * cur) % mod;
            exp >>= 1;
        }
        return result;
    }

    private static long modInv(long x) {
        return modPow(x, MOD - 2, MOD);
    }

    private static class Pair {
        long a, b;

        Pair(long a, long b) {
            this.a = a;
            this.b = b;
        }
    }

    private static Pair fibPairMod(long n, long mod) {
        if (n == 0)
            return new Pair(0, 1 % mod);
        Pair p = fibPairMod(n >> 1, mod);
        long a = p.a, b = p.b;

        long twoBMinusA = (2 * b - a) % mod;
        if (twoBMinusA < 0)
            twoBMinusA += mod;

        long c = (a * twoBMinusA) % mod;
        long d = ((a * a) % mod + (b * b) % mod) % mod;

        if ((n & 1) != 0) {
            return new Pair(d, (c + d) % mod);
        }
        return new Pair(c, d);
    }

    public static String solve() {
        long n = 1;
        for (int i = 0; i < 14; i++)
            n *= 11;

        long k = n - 1;
        Pair p = fibPairMod(k, MOD_EXP);
        long F = p.a;
        long L = (2 * p.b - p.a) % MOD_EXP;
        if (L < 0)
            L += MOD_EXP;

        int sign = (k % 3 == 0) ? 1 : -1;

        long twoPowL = modPow(2, L, MOD);
        long threePowF = modPow(3, F, MOD);

        long alpha, beta;
        long g1, g2;

        if ((n & 1) != 0) {
            alpha = twoPowL;
            beta = threePowF;
            g1 = (n == 1) ? 4 : 12;
            g2 = 1;
        } else {
            alpha = threePowF;
            beta = twoPowL;
            g1 = 1;
            g2 = (n == 2) ? 6 : 12;
        }

        long alpha2 = (alpha * alpha) % MOD;
        long beta2 = (beta * beta) % MOD;

        long n1 = (3 * alpha2 + 4 * beta2) % MOD;
        long n2 = (4 * alpha2 - 3 * beta2) % MOD;
        if (n2 < 0)
            n2 += MOD;

        long dBase = (twoPowL * threePowF) % MOD;

        long a = (n1 * modInv(g1)) % MOD;
        long b = (dBase * modInv(g1)) % MOD;
        long c = (n2 * modInv(g2)) % MOD;
        long d = (dBase * modInv(g2)) % MOD;

        if (sign < 0) {
            a = (MOD - a) % MOD;
            c = (MOD - c) % MOD;
        }

        long ans = (a + b + c + d) % MOD;
        return String.valueOf(ans);
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}