{"problem":{"name":"lgdAKIOI","description":{"content":"6ms 后，lgd 写对了最后一题的 ```plain 可持久化非确定状态AC自动分块维护线段平衡仙人掌优化最小费用最大流预处理混合图上莫比乌斯反演莫队带花舞蹈链并查集树状数组套主席树预处理动态DP分治FFT求多项式逆元对数函数的指数函数用可持久化并查集合并最小费用循环流上插头DP ``` 算法，AK 了 IOI。于是他闲着无聊，开始给自己出题。 有一题是这样的： $n$ 个同学站成一个圆圈","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8442"},"statements":[{"statement_type":"Markdown","content":"6ms 后，lgd 写对了最后一题的\n\n```plain\n可持久化非确定状态AC自动分块维护线段平衡仙人掌优化最小费用最大流预处理混合图上莫比乌斯反演莫队带花舞蹈链并查集树状数组套主席树预处理动态DP分治FFT求多项式逆元对数函数的指数函数用可持久化并查集合并最小费用循环流上插头DP\n```\n算法，AK 了 IOI。于是他闲着无聊，开始给自己出题。\n\n有一题是这样的：\n\n$n$ 个同学站成一个圆圈，其中的一个同学手里拿着一个球。每一次，手里有球的同学可以把球传给自己左右的两个同学中的一个（左右任意）。那么有多少种不同的传球方法可以使得从 lgd 手里开始传的球，传了 $m$ 次以后，又回到 lgd 自己手里呢？两种传球方法被视作不同的方法，当且仅当这两种方法中，接到球的同学按接球顺序组成的序列是不同的。\n\n你听说这道题之后，希望把它做出来，以不遭到 lgd 的鄙视。由于 lgd 比较仁慈，他允许你只告诉他答案取模 $720000054000001$ 的余数就好了。\n\n## Input\n\n此题有多组数据。\n\n对于每组数据，一行两个正整数 $n,m$，含义如题。\n\n## Output\n\n对于每组数据，一行一个自然数表示答案。\n\n[samples]\n\n## Background\n\n本题中出现的神犇：[_lgswdn](https://www.luogu.com.cn/user/180652)\n\nAK 完 NOI 后，lgd 一路势不可挡，不久便进入了国家队，来到了 IOI 赛场。\n\n## Note\n\n**本题采用捆绑测试。**\n\n**本题有多组数据。**\n\n**请注意常数因子带来的程序效率及空间占用上的影响。**\n\n数据范围如下表所示。\n\n|数据点编号|$n$|$m$|数据组数|分值|特殊性质|子任务编号|\n|----|----|----|----|----|----|----|\n|$1\\sim6$|$=100$|$\\le100$|$\\le5$|$5$|A|0|\n|$7\\sim12$|$=10^5$|$\\le10^6$|$\\le5$|$15$|A|1|\n|$13\\sim18$|$=10^6$|$\\le2\\times10^6$|$\\le5$|$10$|A|2|\n|$19\\sim24$|$=2\\times10^5$|$\\le10^{1000}$|$\\le5$|$20$|A|3|\n|$25\\sim30$|$\\le6\\times10^6$|$\\le10^{30}$|$\\le50$|$20$||4|\n|$31\\sim36$|$\\le6\\times10^6$|$\\le10^{10^4}$|$\\le2500$|$30$||5|\n\n特殊性质 A：所有输入的 $n$ 全部相同。\n\n对于 $100\\%$ 的数据，$n\\in\\{10,13,100,10^3,10^4,10^5,2\\times10^5,6\\times10^5,10^6,6\\times10^6\\}$。\n\n---\n\nlgd 把这题交给你的时候同时给了你另外一段代码，不过有什么用就不知道了。\n\n```cpp\ntypedef long long i64;\ntypedef unsigned long long u64;\ntypedef __uint128_t u128;\nstruct Mod64 {\n  Mod64() : n(0) {}\n  Mod64(u64 n) : n(init(n)) {}\n  static u64 modulus() { return mod; }\n  static u64 init(u64 w) { return reduce(u128(w) * r2); }\n  static void setmod(u64 m) {\n    mod = m;\n    inv = 1;\n    for (int i = 0; i < 6; ++i) inv *= 2 + inv * m;\n    r2 = -u128(m) % m;\n  }\n  static u64 reduce(u128 x) {\n    u64 y = (x + u128(u64(x) * inv) * mod) >> 64;\n    return i64(y) > mod ? y - mod : y;\n  }\n  Mod64& operator+=(Mod64 rhs) {\n    n += rhs.n - mod;\n    if (i64(n) < 0) n += mod;\n    return *this;\n  }\n  Mod64& operator-=(Mod64 rhs) {\n    if (n < rhs.n)\n      n += mod - rhs.n;\n    else\n      n -= rhs.n;\n    return *this;\n  }\n  Mod64 operator-() const {\n    if (!n) return *this;\n    Mod64 rhs;\n    rhs.n = mod - n;\n    return rhs;\n  }\n  Mod64 operator+(Mod64 rhs) const { return Mod64(*this) += rhs; }\n  Mod64 operator-(Mod64 rhs) const { return Mod64(*this) -= rhs; }\n  Mod64& operator*=(Mod64 rhs) {\n    n = reduce(u128(n) * rhs.n);\n    return *this;\n  }\n  Mod64 operator*(Mod64 rhs) const { return Mod64(*this) *= rhs; }\n  u64 get() const { return reduce(n); }\n  static u64 mod, inv, r2;\n  u64 n;\n};\nu64 Mod64::mod, Mod64::inv, Mod64::r2;\n```","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8442","tags":["洛谷原创","O2优化","洛谷月赛"],"sample_group":[["5 7\n5 5\n5 4\n5 5\n5 9","14\n2\n6\n2\n72"],["100000 998684\n100000 998671\n100000 998110","513030267786335\n0\n570065615362699"]],"created_at":"2026-03-03 11:09:25"}}