<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

407. Number of Paths in the Empire
Time limit per test: 0.75 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard

During the period of Tsam dynasty ruling people rarely fought against each other and their neighbours, because they just could not afford themselves such a waste of time. The matter for it is that they were entirely absorbed with solving various problems which were connected with trade, craft, agriculture and other spheres of human activity. In a wide list of problems the ones of tax collection stand out. As one of such problems was posed by Emperor himself, it was of great importance. The problem was to count the number of different paths consisting of exactly m roads. Every path should have started and ended in the capital of Empire. Paths were supposed to cover the same towns and roads any times, moreover they could cover the capital several times. Now you are to solve this problem given information about Empire: there were n country towns situated at the foot of a hill, they formed a circle at the bottom, and the capital was on the top of the hill. The capital was connected to all other towns, and each country town was also connected to other two neighbouring country towns both to the left and to the right. Pic. 1 Empire comprising the capital (index 0) and four country towns (indices 1 — 4).
Input
The only line of input file contains two integers n and m (3 ≤ n ≤ 1000, 0 ≤ m ≤ 5000).
Output
Output the answer without leading zeros.
Example(s)
sample input
sample output
4 3
8

sample input
sample output
3 4
21

Commentary to the first sample test. There are 8 paths in the Empire. 0-1-2-0, 0-2-3-0, 0-3-4-0, 0-4-1-0, 0-2-1-0, 0-3-2-0, 0-4-3-0, 0-1-4-0.

<|response|>
1. Abridged Problem Statement  
We have a “wheel” graph with one capital at node 0 and n peripheral towns (nodes 1…n) forming a cycle. The capital is connected to every town, and each town is also connected to its two cycle‐neighbors. Count the number of walks of exactly m edges that start and end at the capital (node 0), revisiting nodes and edges is allowed. Output the exact count (no modulo).

Constraints:  
• 3 ≤ n ≤ 1000  
• 0 ≤ m ≤ 5000  

2. Key Observations  
• All peripheral towns are symmetric, so instead of tracking each of the n towns separately, merge them into one “supernode.”  
• We only need to track two macro‐states at step k:  
  – State 0: you are at the capital.  
  – State 1: you are at any peripheral town (the supernode).  
• Compute the number of ways to transition between these two states in one step:  
  – From 0 → super: you can pick any of the n towns → n ways  
  – From 0 → 0: impossible → 0 ways  
  – From super → 0: aggregated as 1 way (choosing the spoke back)  
  – From super → super: move along the cycle to one of two neighbors → 2 ways  
• This yields a 2×2 transition matrix  
   A = [ [0, 1],  
       [n, 2] ]  
  so that if v_k = [ways at 0 after k steps, ways at super after k steps], then  
   v_{k+1} = A · v_k.  
• We start with v₀ = [1, 0]. After m steps, v_m = A^m · v₀, and the answer is the first component of v_m.  
• Compute A^m by fast exponentiation in O(log m) matrix multiplications. Use big‐integer arithmetic (C++ boost::multiprecision or Python’s built‐in int).

3. Full Solution Approach  
1. Build the 2×2 matrix A = [[0,1],[n,2]].  
2. Fast‐exponentiate A to the power m using binary exponentiation:  
   • Initialize result = identity matrix I₂.  
   • While p > 0:  
     – If p odd, result = result × A  
     – A = A × A  
     – p >>= 1  
3. Multiply the resulting A^m by the initial vector v₀ = [1,0]^T. The answer is the first entry of v_m = A^m·v₀, which equals (A^m)[0][0].  
4. Print that big integer.

4. C++ Implementation with Detailed Comments  
```cpp
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
// Use boost::multiprecision::cpp_int for arbitrary‐precision integers.
using BigInt = boost::multiprecision::cpp_int;

// Multiply two 2×2 matrices of BigInt.
array<array<BigInt,2>,2> mulMat(
    const array<array<BigInt,2>,2>& A,
    const array<array<BigInt,2>,2>& B)
{
    array<array<BigInt,2>,2> C;
    // Standard matrix multiplication: C[i][j] = sum_k A[i][k] * B[k][j]
    for(int i = 0; i < 2; ++i) {
        for(int j = 0; j < 2; ++j) {
            C[i][j] = 0;
            for(int k = 0; k < 2; ++k)
                C[i][j] += A[i][k] * B[k][j];
        }
    }
    return C;
}

// Fast exponentiation of a 2×2 matrix to non-negative power p.
array<array<BigInt,2>,2> powMat(
    array<array<BigInt,2>,2> base,
    long long p)
{
    // Initialize result as the identity matrix I₂.
    array<array<BigInt,2>,2> result = {{{1,0},{0,1}}};
    while(p > 0) {
        if (p & 1LL) {
            result = mulMat(result, base);
        }
        base = mulMat(base, base);
        p >>= 1;
    }
    return result;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long m;
    cin >> n >> m;

    // Build the transition matrix A = [ [0,1], [n,2] ].
    array<array<BigInt,2>,2> A;
    A[0][0] = 0;   A[0][1] = 1;
    A[1][0] = n;   A[1][1] = 2;

    // Compute A^m.
    auto Am = powMat(A, m);

    // Initial vector v0 = [1, 0]^T. After m steps: v_m = Am * v0.
    // The number of ways to be at the capital is v_m[0] = Am[0][0].
    BigInt answer = Am[0][0];

    // Output the exact result.
    cout << answer << "\n";
    return 0;
}
```

5. Python Implementation with Detailed Comments  
```python
import sys

def matrix_mult_2x2(A, B):
    """
    Multiply two 2×2 matrices A and B.
    A and B are lists of lists: [[a,b],[c,d]].
    Returns the 2×2 product.
    """
    return [
        [
            A[0][0]*B[0][0] + A[0][1]*B[1][0],
            A[0][0]*B[0][1] + A[0][1]*B[1][1]
        ],
        [
            A[1][0]*B[0][0] + A[1][1]*B[1][0],
            A[1][0]*B[0][1] + A[1][1]*B[1][1]
        ]
    ]

def matrix_pow_2x2(A, power):
    """
    Fast exponentiation of 2×2 matrix A to the integer power.
    Uses binary (square‐and‐multiply) method in O(log power) steps.
    """
    # Start with the identity matrix.
    result = [[1, 0], [0, 1]]
    while power > 0:
        if power & 1:
            result = matrix_mult_2x2(result, A)
        A = matrix_mult_2x2(A, A)
        power >>= 1
    return result

def solve(n, m):
    # Build transition matrix A = [[0,1],[n,2]]
    A = [[0, 1],
         [n, 2]]
    # Compute A^m
    Am = matrix_pow_2x2(A, m)
    # Initial vector v0 = [1, 0]^T → after m steps: v_m = Am · v0.
    # The number of ways to return to capital is v_m[0] = Am[0][0].
    return Am[0][0]

def main():
    data = sys.stdin.readline().split()
    if not data:
        return
    n, m = map(int, data)
    # Python ints are arbitrary precision by default.
    print(solve(n, m))

if __name__ == "__main__":
    main()
```