#P14109. [JAG 2023 Summer Camp #2] Tea time in the grand garden
[JAG 2023 Summer Camp #2] Tea time in the grand garden
题目描述
适宜的温度变化对于冲泡美味的茶至关重要。Noli 被传授了一个美味茶的配方。
该配方由一个长度为 的非负整数序列 表示。她必须相应地改变温度。
升高温度是项艰苦的工作。配方 的成本由以下 定义。
Noli 忘记了她被传授的配方。她只记得 ,并且成本是 。
有多少种可能的配方可以考虑?请找出可能的配方数量除以 的余数。
注意,当对于任意 , 的值不同时,两个配方被认为是不同的。
输入格式
输入满足以下约束:
- 所有输入均为整数。
输出格式
输出可能的配方数量除以 的余数。请在输出末尾添加换行符。
输入输出样例 #1
输入 #1
2 2
输出 #1
5
输入输出样例 #2
输入 #2
100 0
输出 #2
1
输入输出样例 #3
输入 #3
300 300
输出 #3
527212271
输入输出样例 #4
输入 #4
200000 200000
输出 #4
885086300
说明/提示
在样例输入 1 中,有五种可能的序列 :