{"problem":{"name":"[GDKOI2024 提高组] 鸡","description":{"content":"对于一个非负整数序列 $a$，定义它对应的独立集序列 $f(a)$： - 假设将 $a_i$ 改为 $0$，此时选出若干个两两不相邻的数使得它们的和最大，则 $f(a)_i$ 表示和的最大值。 现在给定 $n, m$，求有多少个长度为 $b$ 的非负整数序列 $b$ 满足以下条件： - 存在至少一个长度为 $n$，值域为 $[0, m]$ 的非负整数序列 $a$ 使得 $f(a) = b$。","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":"LGP10082"},"statements":[{"statement_type":"Markdown","content":"对于一个非负整数序列 $a$，定义它对应的独立集序列 $f(a)$：\n\n- 假设将 $a_i$ 改为 $0$，此时选出若干个两两不相邻的数使得它们的和最大，则 $f(a)_i$ 表示和的最大值。\n\n现在给定 $n, m$，求有多少个长度为 $b$ 的非负整数序列 $b$ 满足以下条件：\n\n- 存在至少一个长度为 $n$，值域为 $[0, m]$ 的非负整数序列 $a$ 使得 $f(a) = b$。\n\n答案对给定的质数 $\\textit{MOD}$ 取模。\n\n## Input\n\n共一行，三个数，表示 $n, m, \\textit{MOD}$。\n\n## Output\n\n共一行，一个数，表示答案。\n\n[samples]\n\n## Note\n\n**本题使用子任务捆绑测试。**\n\n对于 $100\\%$ 的数据，$1 \\leq n, m \\leq 3 \\times 10^3$，$n \\geq 2$，$10^9 < \\textit{MOD} < 1.01 \\times 10^9$，$\\textit{MOD}$ 为质数。\n\n- Subtask 1（10%）：$n, m \\leq 5$。\n- Subtask 2（15%）：$n \\leq 300$，$m = 1$。\n- Subtask 3（25%）：$n \\leq 300$，$m ≤ 5$。\n- Subtask 4（20%）：$n, m \\leq 50$。\n- Subtask 5（15%）：$n, m \\leq 300$。\n- Subtask 6（15%）：无特殊限制。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10082","tags":["2024","广东","O2优化"],"sample_group":[["3 1 1000000007","6"],["4 2 1000000007","47"],["20 24 1000000007","901565358"],["123 234 1000000009","141754844"],["1234 2345 1004535809","576196526"]],"created_at":"2026-03-03 11:09:25"}}