题目背景

本题中出现的神犇：_lgswdn

AK 完 NOI 后，lgd 一路势不可挡，不久便进入了国家队，来到了 IOI 赛场。

题目描述

6ms 后，lgd 写对了最后一题的

可持久化非确定状态AC自动分块维护线段平衡仙人掌优化最小费用最大流预处理混合图上莫比乌斯反演莫队带花舞蹈链并查集树状数组套主席树预处理动态DP分治FFT求多项式逆元对数函数的指数函数用可持久化并查集合并最小费用循环流上插头DP

算法，AK 了 IOI。于是他闲着无聊，开始给自己出题。

有一题是这样的：

$n$ 个同学站成一个圆圈，其中的一个同学手里拿着一个球。每一次，手里有球的同学可以把球传给自己左右的两个同学中的一个（左右任意）。那么有多少种不同的传球方法可以使得从 lgd 手里开始传的球，传了 $m$ 次以后，又回到 lgd 自己手里呢？两种传球方法被视作不同的方法，当且仅当这两种方法中，接到球的同学按接球顺序组成的序列是不同的。

你听说这道题之后，希望把它做出来，以不遭到 lgd 的鄙视。由于 lgd 比较仁慈，他允许你只告诉他答案取模 $720000054000001$ 的余数就好了。

输入格式

此题有多组数据。

对于每组数据，一行两个正整数 $n,m$，含义如题。

输出格式

对于每组数据，一行一个自然数表示答案。

5 7
5 5
5 4
5 5
5 9

14
2
6
2
72

100000 998684
100000 998671
100000 998110

513030267786335
0
570065615362699

提示

本题采用捆绑测试。

本题有多组数据。

请注意常数因子带来的程序效率及空间占用上的影响。

数据范围如下表所示。

数据点编号	$n$	$m$	数据组数	分值	特殊性质	子任务编号
$1\sim6$	$=100$	$\le100$	$\le5$	$5$	A	0
$7\sim12$	$=10^5$	$\le10^6$		$15$		1
$13\sim18$	$=10^6$	$\le2\times10^6$		$10$		2
$19\sim24$	$=2\times10^5$	$\le10^{1000}$		$20$		3
$25\sim30$	$\le6\times10^6$	$\le10^{30}$	$\le50$			4
$31\sim36$		$\le10^{10^4}$	$\le2500$	$30$		5

特殊性质 A：所有输入的 $n$ 全部相同。

对于 $100\%$ 的数据，$n\in\{10,13,100,10^3,10^4,10^5,2\times10^5,6\times10^5,10^6,6\times10^6\}$。

---

lgd 把这题交给你的时候同时给了你另外一段代码，不过有什么用就不知道了。

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 = m;
    for (int i = 0; i < 5; ++i) inv *= 2 - inv * m;
    r2 = -u128(m) % m;
  }
  static u64 reduce(u128 x) {
    u64 y = u64(x >> 64) - u64((u128(u64(x) * inv) * mod) >> 64);
    return i64(y) < 0 ? 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*=(Mod64 rhs) {
    n = reduce(u128(n) * rhs.n);
    return *this;
  }
  Mod64 operator*(Mod64 rhs) const { return Mod64(*this) *= rhs; }
  Mod64 operator+(Mod64 rhs) const { return Mod64(*this) += rhs; }
  Mod64 operator-(Mod64 rhs) const { return Mod64(*this) -= rhs; }
  u64 get() const { return reduce(n); }
  static u64 mod, inv, r2;
  u64 n;
  friend ostream& operator<<(ostream& out, Mod64 x) { return out << x.get(); }
};
u64 Mod64::mod, Mod64::inv, Mod64::r2;