2023 年上海市大学生程序设计竞赛 - 七月赛

A. 狗吃骨头

单点时限: 2.0 sec

内存限制: 512 MB

有 $m$ 只狗吃骨头,共有 $N$ ($N$ 未知) 根骨头,且 $N$ 不是 $m$ 的倍数。把所有 $m$ 只狗编号 $1\sim m$。

  • 第 $1$ 只狗偷偷跑过去,吃了一根骨头,然后发现剩下的骨头数量非 0 且恰好能等分成 $m$ 份,于是又吃掉了其中一份(=剩余总数的 $\frac 1 m$ )后离开。
  • 第 $2$ 只狗也跑过去吃了一根,又发现剩下的骨头数量非 0 且也能恰好等分成 $m$ 份,于是又吃掉了其中一份(=剩余总数的 $\frac 1 m$ )后离开。
  • 以此类推,第 $i$ 只狗吃掉一根后,会发现剩下的骨头的数量非 0 且是 $m$ 的倍数,于是又吃掉了其中一份(=剩余总数的 $\frac 1 m$ )后离开。
  • 最后一只狗吃掉一根后,会发现剩下的骨头的数量非 0 且是 $m$ 的倍数,于是又吃掉了一份。

如果要让 $m$ 只狗全部按照上述规律(ie. 先吃一根,再吃一份)吃骨头,则该堆骨头至少有多少根?答案对 998244353 取模。

输入格式

一行一个整数 $m (2 \le m \le 10^{17})$

输出格式

一行一个整数 $N\%998244353$,如题目描述

样例

Input
15
Output
567381124
Input
7
Output
823537

提示

当 $m=2$ 时,最少需要 $7$ 根骨头。

  • 第一只狗吃一根 $7-1=6$
  • 第一只狗吃一份 $6 \times \frac 1 2 = 3$
  • 第二只狗吃一根 $3-1 = 2$
  • 第二只狗吃一份 $2 \times \frac 1 2 = 1$