Background

The “legendary expert” (shen ben) appearing in this problem: _lgswdn.

After getting AK in NOI, lgd became unstoppable. Before long, he entered the national team and came to the IOI arena.

Problem Description

After 6 ms, lgd solved the last problem using the following

Persistent nondeterministic-state AC automaton with block decomposition to maintain segment balance, cactus optimization, min-cost max-flow, preprocessing, Möbius inversion on mixed graphs, Mo's algorithm with fancy dancing links, DSU, Fenwick tree with segment tree (Chairman Tree), preprocessing, dynamic DP, divide and conquer, FFT to compute the inverse of a polynomial, exponential of a logarithmic function, and plug DP on min-cost circulation using persistent DSU merging.

algorithm, and AK’ed IOI. Then he got bored and started making problems for himself.

One of the problems is as follows:

There are $n$ students standing in a circle, and one of them is holding a ball. Each time, the student holding the ball can pass it to one of the two adjacent students on the left or right (either direction). How many different passing methods are there such that the ball, starting from lgd’s hands, after being passed $m$ times, returns to lgd’s own hands? Two passing methods are considered different if and only if the sequences formed by the students who receive the ball, in receiving order, are different.

After hearing about this problem, you hope to solve it so that you will not be looked down upon by lgd. Since lgd is kind, he allows you to only report the answer modulo $720000054000001$.

lgd also gave you another piece of code when he handed you this problem, but it is unknown what it is for.

typedef long long i64;
typedef unsigned long long u64;
typedef __uint128_t u128;
struct Mod64 {
  Mod64() : n(0) {}
  Mod64(u64 n) : n(init(n)) {}
  static u64 modulus() { return mod; }
  static u64 init(u64 w) { return reduce(u128(w) * r2); }
  static void setmod(u64 m) {
    mod = m;
    inv = 1;
    for (int i = 0; i < 6; ++i) inv *= 2 + inv * m;
    r2 = -u128(m) % m;
  }
  static u64 reduce(u128 x) {
    u64 y = (x + u128(u64(x) * inv) * mod) >> 64;
    return i64(y) > mod ? y - mod : y;
  }
  Mod64& operator+=(Mod64 rhs) {
    n += rhs.n - mod;
    if (i64(n) < 0) n += mod;
    return *this;
  }
  Mod64& operator-=(Mod64 rhs) {
    if (n < rhs.n)
      n += mod - rhs.n;
    else
      n -= rhs.n;
    return *this;
  }
  Mod64 operator-() const {
    if (!n) return *this;
    Mod64 rhs;
    rhs.n = mod - n;
    return rhs;
  }
  Mod64 operator+(Mod64 rhs) const { return Mod64(*this) += rhs; }
  Mod64 operator-(Mod64 rhs) const { return Mod64(*this) -= rhs; }
  Mod64& operator*=(Mod64 rhs) {
    n = reduce(u128(n) * rhs.n);
    return *this;
  }
  Mod64 operator*(Mod64 rhs) const { return Mod64(*this) *= rhs; }
  u64 get() const { return reduce(n); }
  static u64 mod, inv, r2;
  u64 n;
};
u64 Mod64::mod, Mod64::inv, Mod64::r2;

Input Format

This problem has multiple test cases.

For each test case, one line contains two positive integers $n,m$, with the meaning as described in the statement.

Output Format

For each test case, output one non-negative integer per line, representing the answer.

5 7
5 5
5 4
5 5
5 9

14
2
6
2
72

100000 998684
100000 998671
100000 998110

513030267786335
0
570065615362699

Hint

This problem uses bundled tests.

This problem has multiple test cases.

Please pay attention to the impact of constant factors on runtime efficiency and memory usage.

The constraints are shown in the table below.

Special Property A: all input $n$ are the same.

For $100\%$ of the data, $n\in\{10,13,100,10^3,10^4,10^5,2\times10^5,6\times10^5,10^6,6\times10^6\}$.

Translated by ChatGPT 5