:::epigraph
“呃…嗯，我们可以重新开始我们的友谊吗？”
“你什么意思…你是说，重新开始？”
“…”
:::
很久很久以前，小青鱼与他最好的朋友小 一起准备了一场程序设计竞赛。他们准备一共了 道题目，编号为从 到 的整数。第 道题目（）有一个难度评级 。
时间过得很快。距离他们举办的比赛已经过去十五个月了。小青鱼已经不再是 Informatics Olympiad 的选手了，而是转型成为了一名教练。但他们曾有过约定，要一起举办一组系列锦标赛。
而小青鱼没有忘掉它。
现在，小青鱼想要把这 道题目分组为若干场训练活动。为了确保题目的题面中包含的故事背景一致，小青鱼想要把这 道题目划分成若干个区间。一个划分题目的方案可以记为一个整数序列 ，表示共有 场训练活动，其中第 场活动包含所有编号在 和 之间（含两端）的题目。
除此以外，小青鱼不想让某一场活动变得太不平衡。如果一场活动中包含一道困难的题目，那么这个活动就应该包含更多的题目。形式化地，如果题目 在第 个活动中（也就是说，），那么不等式 必须成立。
小青鱼很好奇能够有多少种划分题目的方案可以满足上述所有要求，并把方案数记做 。这个问题对他来说很简单，所以小青鱼很轻松地就算出了答案。
在这些活动的前一天，小青鱼突然意识到这些题目对选手来说太困难了。因此，他想到了一道新的简单题目，其难度评级只有 。他很好奇，对每个 ，如果我们使用如下方式定义序列 ，那么 的值是多少。
因为 的值可以非常大，您只需要输出它对 取模后的结果。
