Problem 382: Generating Polygons

Project Euler Problem 382 Solution

EulerSolve provides an optimized solution for Project Euler Problem 382, Generating Polygons, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary The side lengths are generated by $$s_1=1,\quad s_2=2,\quad s_3=3,\quad s_n=s_{n-1}+s_{n-3}\quad (n\ge 4).$$ Because $s_{n-3}\gt 0$, the sequence is strictly increasing, so every subset of $\{s_1,\dots,s_n\}$ has a unique largest selected side. Let $f(n)$ be the number of nonempty subsets that can be arranged into a nondegenerate polygon. The solver computes $f(10^{18}) \bmod 10^9$. Mathematical Approach Step 1: Reduce Polygon Feasibility to One Inequality For any finite set of positive side lengths, a polygon exists if and only if the largest side is smaller than the sum of all remaining sides. If a subset has largest side $s_n$, then it is bad exactly when the other chosen sides have total length at most $s_n$. This immediately turns the geometric problem into a counting problem about subset sums. Step 2: Count Bad Subsets by Their Largest Index Define $b_n$ as the number of subsets of $\{s_1,\dots,s_{n-1}\}$ whose sum is at most $s_n$: $$b_n=\#\left\{A\subseteq \{1,\dots,n-1\}:\sum_{i\in A}s_i\le s_n\right\}.$$ Every non-polygon subset of $\{s_1,\dots,s_n\}$ has a unique largest element $s_k$, and after removing that largest side the remaining subset contributes to $b_k$....

Detailed mathematical approach

Problem Summary

The side lengths are generated by

$$s_1=1,\quad s_2=2,\quad s_3=3,\quad s_n=s_{n-1}+s_{n-3}\quad (n\ge 4).$$

Because $s_{n-3}\gt 0$, the sequence is strictly increasing, so every subset of $\{s_1,\dots,s_n\}$ has a unique largest selected side. Let $f(n)$ be the number of nonempty subsets that can be arranged into a nondegenerate polygon. The solver computes $f(10^{18}) \bmod 10^9$.

Mathematical Approach

Step 1: Reduce Polygon Feasibility to One Inequality

For any finite set of positive side lengths, a polygon exists if and only if the largest side is smaller than the sum of all remaining sides. If a subset has largest side $s_n$, then it is bad exactly when the other chosen sides have total length at most $s_n$.

This immediately turns the geometric problem into a counting problem about subset sums.

Step 2: Count Bad Subsets by Their Largest Index

Define $b_n$ as the number of subsets of $\{s_1,\dots,s_{n-1}\}$ whose sum is at most $s_n$:

$$b_n=\#\left\{A\subseteq \{1,\dots,n-1\}:\sum_{i\in A}s_i\le s_n\right\}.$$

Every non-polygon subset of $\{s_1,\dots,s_n\}$ has a unique largest element $s_k$, and after removing that largest side the remaining subset contributes to $b_k$. Therefore the bad subsets are counted exactly once by $\sum_{k=1}^{n} b_k$, and

$$\boxed{f(n)=\left(2^n-1\right)-\sum_{k=1}^{n} b_k.}$$

This identity is the core formula used by all three implementations.

Step 3: Exact Subset-Sum Counting for the Initial Terms

The C++ reference solution builds the first values of $b_n$ with an exact memoized counter. Let

$$P_i=\sum_{k=1}^{i}s_k,\qquad C(i,L)=\#\left\{A\subseteq \{1,\dots,i\}:\sum_{k\in A}s_k\le L\right\}.$$

The recursion implemented in ExactCounter is

$$ C(i,L)= \begin{cases} 1, & i=0,\\ 2^i, & L\ge P_i,\\ C(i-1,L), & s_i\gt L,\\ C(i-1,L)+C(i-1,L-s_i), & s_i\le L. \end{cases} $$

Then $b_n=C(n-1,s_n)$. The exact values produced by the local code are

$$ (b_1,b_2,b_3,b_4,b_5,b_6,b_7,b_8)=(1,2,4,6,11,20,36,67). $$

These eight terms form the base state for the fast solver.

Step 4: Use the Verified Order-8 Recurrence

From the exact sequence one obtains the linear recurrence embedded in all three source files:

$$ b_n=3b_{n-1}-2b_{n-2}+2b_{n-3}-5b_{n-4}+b_{n-5}+b_{n-6}+3b_{n-7}-2b_{n-8}, \qquad n\ge 9. $$

The C++ program does not merely assume this relation: it recomputes $b_n$ exactly up to $n=60$ and checks that the recurrence matches every term from $n=9$ onward. That validation step is the reason the mathematical description should treat this recurrence as a verified fact coming from the local solution, not as an unsupported guess.

Step 5: Augment the State with the Prefix Sum

We need $B_n=\sum_{k=1}^{n} b_k$, not just $b_n$. So the solver stores the 9-component state

$$ v_n= \begin{bmatrix} b_n\\ b_{n-1}\\ b_{n-2}\\ b_{n-3}\\ b_{n-4}\\ b_{n-5}\\ b_{n-6}\\ b_{n-7}\\ B_n \end{bmatrix}. $$

With the recurrence coefficients in the first row, simple shifts in rows $2$ through $8$, and one extra cumulative row, we get

$$v_{n+1}=Tv_n,$$

where

$$ T= \begin{bmatrix} 3 & -2 & 2 & -5 & 1 & 1 & 3 & -2 & 0\\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\ 3 & -2 & 2 & -5 & 1 & 1 & 3 & -2 & 1 \end{bmatrix}. $$

The starting vector is

$$ v_8= \begin{bmatrix} 67\\ 36\\ 20\\ 11\\ 6\\ 4\\ 2\\ 1\\ 147 \end{bmatrix}, \qquad 147=1+2+4+6+11+20+36+67. $$

For $n\gt 8$, binary exponentiation gives $v_n=T^{\,n-8}v_8$ modulo $10^9$. The last component is $B_n$.

Step 6: Final Formula and Checkpoints

Once $B_n$ is known, the answer is

$$\boxed{f(n)\equiv 2^n-1-B_n \pmod{10^9}.}$$

A small example shows the decomposition clearly. For $n=5$, the sequence is $(1,2,3,4,6)$, the exact counter gives

$$ (b_1,b_2,b_3,b_4,b_5)=(1,2,4,6,11), $$

and therefore

$$ f(5)=2^5-1-(1+2+4+6+11)=31-24=7. $$

The C++ validation also checks the Project Euler checkpoints

$$f(10)=501,\qquad f(25)=18635853.$$

Running the local solver for the target input yields

$$f(10^{18}) \equiv 697003956 \pmod{10^9}.$$

How the Code Works

The C++ file contains both the exact validator and the fast solver. ExactCounter computes $b_n$ by memoized subset-sum counting and confirms the recurrence on $n\le 60$. The function prefix_sum_b_mod handles the eight base terms directly, then switches to 9 by 9 matrix exponentiation. Negative recurrence coefficients are normalized modulo $10^9$ before being inserted into the transition matrix. Finally, solve_mod computes $2^n \bmod 10^9$, subtracts $1$ and the prefix sum $B_n$, and normalizes the result.

The Python and Java files are compact translations of the same fast path: identical base values, identical recurrence coefficients, the same 9-state transition, and the same final congruence.

Complexity Analysis

The exact subset-sum validator is used only on small $n$, so it does not affect the asymptotic cost of the real computation. The production path performs binary exponentiation on a fixed $9\times 9$ matrix, giving $O(9^3\log n)$ time with dense multiplication and $O(9^2)$ memory. Since $9$ is constant, this is effectively $O(\log n)$ time and constant auxiliary space.

Footnotes and References

Problem page: https://projecteuler.net/problem=382
Polygon existence criterion: Wikipedia — Polygon
Matrix exponentiation for linear recurrences: cp-algorithms — Fibonacci Numbers
Local reference implementation with exact validation and checkpoints: solutionsCpp/Euler382.cpp
Compact fast-path implementations: solutionsPython/Euler382.py and solutionsJava/Euler382.java

Problem 382 source code

C++

#include <array>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <limits>
#include <stdexcept>
#include <string>
#include <unordered_map>
#include <vector>

namespace {

using u64 = std::uint64_t;
using i64 = std::int64_t;
using u128 = __uint128_t;
using i128 = __int128_t;

constexpr u64 kDefaultN = 1'000'000'000'000'000'000ULL;
constexpr u64 kMod = 1'000'000'000ULL;
constexpr int kOrder = 8;
constexpr std::array<i64, kOrder> kRecurrence = {3, -2, 2, -5, 1, 1, 3, -2};
constexpr int kValidationN = 60;

struct Options {
    u64 n = kDefaultN;
    bool run_checkpoints = true;
};

bool parse_u64_after_prefix(const std::string& arg,
                            const std::string& prefix,
                            u64& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }

    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    u64 parsed = 0ULL;
    for (const char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        const u64 digit = static_cast<u64>(c - '0');
        if (parsed > (std::numeric_limits<u64>::max() - digit) / 10ULL) {
            return false;
        }
        parsed = parsed * 10ULL + digit;
    }

    value = parsed;
    return true;
}

bool parse_arguments(const int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_u64_after_prefix(arg, "--n=", options.n)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return true;
}

u64 mod_norm(const i128 value, const u64 mod) {
    i128 x = value % static_cast<i128>(mod);
    if (x < 0) {
        x += static_cast<i128>(mod);
    }
    return static_cast<u64>(x);
}

u64 add_mod(const u64 a, const u64 b, const u64 mod) {
    const u64 sum = a + b;
    if (sum >= mod || sum < a) {
        return sum % mod;
    }
    return sum;
}

u64 mul_mod(const u64 a, const u64 b, const u64 mod) {
    return static_cast<u64>((static_cast<u128>(a) * static_cast<u128>(b)) %
                            static_cast<u128>(mod));
}

u64 pow_mod(u64 base, u64 exp, const u64 mod) {
    if (mod == 1ULL) {
        return 0ULL;
    }

    u64 result = 1ULL % mod;
    base %= mod;
    while (exp > 0ULL) {
        if ((exp & 1ULL) != 0ULL) {
            result = mul_mod(result, base, mod);
        }
        base = mul_mod(base, base, mod);
        exp >>= 1U;
    }
    return result;
}

struct Key {
    int i = 0;
    u64 limit = 0ULL;

    bool operator==(const Key& other) const {
        return i == other.i && limit == other.limit;
    }
};

struct KeyHash {
    std::size_t operator()(const Key& key) const {
        const std::size_t h1 = std::hash<int>{}(key.i);
        const std::size_t h2 = std::hash<u64>{}(key.limit);
        return h1 ^ (h2 + 0x9e3779b97f4a7c15ULL + (h1 << 6U) + (h1 >> 2U));
    }
};

class ExactCounter {
public:
    explicit ExactCounter(const int max_n) : s_(static_cast<std::size_t>(max_n + 1), 0ULL),
                                             prefix_(static_cast<std::size_t>(max_n + 1), 0U) {
        if (max_n < 3) {
            throw std::runtime_error("ExactCounter requires max_n >= 3.");
        }

        s_[1] = 1ULL;
        s_[2] = 2ULL;
        s_[3] = 3ULL;
        for (int n = 4; n <= max_n; ++n) {
            s_[n] = s_[n - 1] + s_[n - 3];
        }
        for (int i = 1; i <= max_n; ++i) {
            prefix_[i] = prefix_[i - 1] + static_cast<u128>(s_[i]);
        }
    }

    const std::vector<u64>& sequence() const {
        return s_;
    }

    u128 count_subsets_leq(const int i, const u64 limit) {
        if (i <= 0) {
            return 1U;
        }

        if (static_cast<u128>(limit) >= prefix_[i]) {
            return static_cast<u128>(1U) << i;
        }

        const Key key{i, limit};
        const auto it = memo_.find(key);
        if (it != memo_.end()) {
            return it->second;
        }

        u128 result = 0U;
        if (s_[i] > limit) {
            result = count_subsets_leq(i - 1, limit);
        } else {
            result = count_subsets_leq(i - 1, limit) + count_subsets_leq(i - 1, limit - s_[i]);
        }

        memo_.emplace(key, result);
        return result;
    }

private:
    std::vector<u64> s_;
    std::vector<u128> prefix_;
    std::unordered_map<Key, u128, KeyHash> memo_;
};

struct Mat9 {
    std::array<std::array<u64, 9>, 9> a{};
};

Mat9 identity9() {
    Mat9 id;
    for (int i = 0; i < 9; ++i) {
        id.a[static_cast<std::size_t>(i)][static_cast<std::size_t>(i)] = 1ULL;
    }
    return id;
}

Mat9 mat_mul(const Mat9& lhs, const Mat9& rhs, const u64 mod) {
    Mat9 out;
    for (int i = 0; i < 9; ++i) {
        for (int k = 0; k < 9; ++k) {
            const u64 lv = lhs.a[static_cast<std::size_t>(i)][static_cast<std::size_t>(k)];
            if (lv == 0ULL) {
                continue;
            }
            for (int j = 0; j < 9; ++j) {
                const u64 rv = rhs.a[static_cast<std::size_t>(k)][static_cast<std::size_t>(j)];
                if (rv == 0ULL) {
                    continue;
                }
                const u64 add = mul_mod(lv, rv, mod);
                u64& cell = out.a[static_cast<std::size_t>(i)][static_cast<std::size_t>(j)];
                cell = add_mod(cell, add, mod);
            }
        }
    }
    return out;
}

std::array<u64, 9> mat_vec_mul(const Mat9& m, const std::array<u64, 9>& v, const u64 mod) {
    std::array<u64, 9> out{};
    for (int i = 0; i < 9; ++i) {
        u64 acc = 0ULL;
        for (int j = 0; j < 9; ++j) {
            const u64 prod = mul_mod(m.a[static_cast<std::size_t>(i)][static_cast<std::size_t>(j)],
                                     v[static_cast<std::size_t>(j)],
                                     mod);
            acc = add_mod(acc, prod, mod);
        }
        out[static_cast<std::size_t>(i)] = acc;
    }
    return out;
}

std::array<u64, 9> apply_mat_pow(Mat9 base,
                                 u64 exp,
                                 std::array<u64, 9> vec,
                                 const u64 mod) {
    Mat9 acc = identity9();
    while (exp > 0ULL) {
        if ((exp & 1ULL) != 0ULL) {
            acc = mat_mul(base, acc, mod);
        }
        base = mat_mul(base, base, mod);
        exp >>= 1U;
    }
    return mat_vec_mul(acc, vec, mod);
}

u64 prefix_sum_b_mod(const u64 n, const u64 mod) {
    constexpr std::array<u64, kOrder> kBase = {1ULL, 2ULL, 4ULL, 6ULL, 11ULL, 20ULL, 36ULL,
                                                67ULL};

    if (n == 0ULL) {
        return 0ULL;
    }

    if (n <= static_cast<u64>(kOrder)) {
        u64 sum = 0ULL;
        for (u64 i = 0ULL; i < n; ++i) {
            sum = add_mod(sum, kBase[static_cast<std::size_t>(i)] % mod, mod);
        }
        return sum;
    }

    u64 s8 = 0ULL;
    for (const u64 v : kBase) {
        s8 = add_mod(s8, v % mod, mod);
    }

    std::array<u64, 9> state{
        kBase[7] % mod, kBase[6] % mod, kBase[5] % mod, kBase[4] % mod, kBase[3] % mod,
        kBase[2] % mod, kBase[1] % mod, kBase[0] % mod, s8};

    Mat9 trans;
    for (int j = 0; j < kOrder; ++j) {
        trans.a[0][static_cast<std::size_t>(j)] = mod_norm(static_cast<i128>(kRecurrence[j]), mod);
    }
    for (int r = 1; r < kOrder; ++r) {
        trans.a[static_cast<std::size_t>(r)][static_cast<std::size_t>(r - 1)] = 1ULL;
    }
    for (int j = 0; j < kOrder; ++j) {
        trans.a[8][static_cast<std::size_t>(j)] = mod_norm(static_cast<i128>(kRecurrence[j]), mod);
    }
    trans.a[8][8] = 1ULL;

    const std::array<u64, 9> advanced = apply_mat_pow(trans, n - 8ULL, state, mod);
    return advanced[8];
}

u64 solve_mod(const u64 n, const u64 mod) {
    const u64 sum_b = prefix_sum_b_mod(n, mod);
    const u64 pow2 = pow_mod(2ULL, n, mod);
    i128 ans = static_cast<i128>(pow2) - 1 - static_cast<i128>(sum_b);
    return mod_norm(ans, mod);
}

u64 to_u64(const u128 x) {
    return static_cast<u64>(x);
}

void run_checkpoints() {
    ExactCounter exact(kValidationN);
    const auto& s = exact.sequence();

    std::vector<u128> b_exact(static_cast<std::size_t>(kValidationN + 1), 0U);
    for (int n = 1; n <= kValidationN; ++n) {
        b_exact[static_cast<std::size_t>(n)] = exact.count_subsets_leq(n - 1, s[n]);
    }

    for (int n = 9; n <= kValidationN; ++n) {
        i128 rhs = 0;
        for (int j = 0; j < kOrder; ++j) {
            rhs += static_cast<i128>(kRecurrence[static_cast<std::size_t>(j)]) *
                   static_cast<i128>(b_exact[static_cast<std::size_t>(n - 1 - j)]);
        }
        const u128 lhs = b_exact[static_cast<std::size_t>(n)];
        if (rhs < 0 || static_cast<u128>(rhs) != lhs) {
            throw std::runtime_error("Derived linear recurrence failed validation.");
        }
    }

    const auto f_exact = [&](const int n) -> u128 {
        u128 sum_b = 0U;
        for (int i = 1; i <= n; ++i) {
            sum_b += b_exact[static_cast<std::size_t>(i)];
        }
        return (static_cast<u128>(1U) << n) - 1U - sum_b;
    };

    const u64 f5 = to_u64(f_exact(5));
    const u64 f10 = to_u64(f_exact(10));
    const u64 f25 = to_u64(f_exact(25));
    if (f5 != 7ULL || f10 != 501ULL || f25 != 18'635'853ULL) {
        throw std::runtime_error("Problem statement checkpoints failed.");
    }

    for (int n = 1; n <= kValidationN; ++n) {
        const u64 fast = solve_mod(static_cast<u64>(n), kMod);
        const u64 slow = static_cast<u64>(f_exact(n) % static_cast<u128>(kMod));
        if (fast != slow) {
            throw std::runtime_error("Fast modular solver mismatch on validation range.");
        }
    }
}

}  // namespace

int main(int argc, char** argv) {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }

    try {
        if (options.run_checkpoints) {
            run_checkpoints();
        }
    } catch (const std::exception& ex) {
        std::cerr << "Checkpoint failure: " << ex.what() << '\n';
        return 1;
    }

    const u64 answer = solve_mod(options.n, kMod);
    std::cout << "f(" << options.n << ") mod 10^9 = " << answer << '\n';
    std::cout << "Last 9 digits: " << std::setw(9) << std::setfill('0') << answer << '\n';
    return 0;
}

Python

def solve():
    kMod = 1000000000
    kOrder = 8
    kRecurrence = [3, -2, 2, -5, 1, 1, 3, -2]
    
    def zero_mat():
        return [[0]*9 for _ in range(9)]
        
    def mat_mul(a, b):
        c = zero_mat()
        for i in range(9):
            for k in range(9):
                if a[i][k] == 0: continue
                for j in range(9):
                    if b[k][j] == 0: continue
                    c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % kMod
        return c

    def apply_mat_pow(base, exp, vec):
        acc = zero_mat()
        for i in range(9): acc[i][i] = 1
        
        while exp > 0:
            if exp & 1:
                acc = mat_mul(base, acc)
            base = mat_mul(base, base)
            exp >>= 1
            
        out = [0]*9
        for i in range(9):
            s = 0
            for j in range(9):
                s = (s + acc[i][j] * vec[j]) % kMod
            out[i] = s
        return out

    def mod_norm(val):
        return val % kMod

    kBase = [1, 2, 4, 6, 11, 20, 36, 67]
    n = 1000000000000000000
    
    s8 = sum(kBase) % kMod
    state = [
        kBase[7]%kMod, kBase[6]%kMod, kBase[5]%kMod, kBase[4]%kMod,
        kBase[3]%kMod, kBase[2]%kMod, kBase[1]%kMod, kBase[0]%kMod, s8
    ]
    
    trans = zero_mat()
    for j in range(kOrder):
        trans[0][j] = mod_norm(kRecurrence[j])
    for r in range(1, kOrder):
        trans[r][r-1] = 1
    for j in range(kOrder):
        trans[8][j] = mod_norm(kRecurrence[j])
    trans[8][8] = 1
    
    advanced = apply_mat_pow(trans, n - 8, state)
    sum_b = advanced[8]
    
    pow2 = pow(2, n, kMod)
    ans = (pow2 - 1 - sum_b) % kMod
    return str(ans)

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

Java

public class Euler382 {
    private static final long kMod = 1000000000L;
    private static final int kOrder = 8;
    private static final long[] kRecurrence = { 3, -2, 2, -5, 1, 1, 3, -2 };
    private static final long[] kBase = { 1, 2, 4, 6, 11, 20, 36, 67 };

    private static long[][] matMul(long[][] a, long[][] b) {
        long[][] c = new long[9][9];
        for (int i = 0; i < 9; ++i) {
            for (int k = 0; k < 9; ++k) {
                if (a[i][k] == 0)
                    continue;
                for (int j = 0; j < 9; ++j) {
                    if (b[k][j] == 0)
                        continue;
                    c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % kMod;
                }
            }
        }
        return c;
    }

    private static long modNorm(long val) {
        long x = val % kMod;
        if (x < 0)
            x += kMod;
        return x;
    }

    private static long[] applyMatPow(long[][] base, long exp, long[] vec) {
        long[][] acc = new long[9][9];
        for (int i = 0; i < 9; ++i)
            acc[i][i] = 1;

        while (exp > 0) {
            if ((exp & 1) != 0) {
                acc = matMul(base, acc);
            }
            base = matMul(base, base);
            exp >>= 1;
        }

        long[] out = new long[9];
        for (int i = 0; i < 9; ++i) {
            long s = 0;
            for (int j = 0; j < 9; ++j) {
                s = (s + acc[i][j] * vec[j]) % kMod;
            }
            out[i] = s;
        }
        return out;
    }

    private static long powMod(long base, long exp) {
        long res = 1;
        base %= kMod;
        while (exp > 0) {
            if ((exp & 1) != 0)
                res = (res * base) % kMod;
            base = (base * base) % kMod;
            exp >>= 1;
        }
        return res;
    }

    public static String solve() {
        long n = 1000000000000000000L;
        long s8 = 0;
        for (long v : kBase) {
            s8 = (s8 + v) % kMod;
        }

        long[] state = {
                kBase[7] % kMod, kBase[6] % kMod, kBase[5] % kMod, kBase[4] % kMod,
                kBase[3] % kMod, kBase[2] % kMod, kBase[1] % kMod, kBase[0] % kMod, s8
        };

        long[][] trans = new long[9][9];
        for (int j = 0; j < kOrder; ++j) {
            trans[0][j] = modNorm(kRecurrence[j]);
        }
        for (int r = 1; r < kOrder; ++r) {
            trans[r][r - 1] = 1;
        }
        for (int j = 0; j < kOrder; ++j) {
            trans[8][j] = modNorm(kRecurrence[j]);
        }
        trans[8][8] = 1;

        long[] advanced = applyMatPow(trans, n - 8, state);
        long sumB = advanced[8];

        long pow2 = powMod(2, n);
        long ans = modNorm(pow2 - 1 - sumB);
        return String.valueOf(ans);
    }

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