← 返回题目列表

AtCoder · tkppc6_2_a

A. 睁眼与闭眼

中文机器翻译题面 查看原题

配点 : 300 点

問題文

(1,2,\ldots,N) 查找满足以下条件的 P 的数量, 请打印除以998244353 后的余数。

  • 全部 i\ (2 \leq i \leq N) ,以下条件之一成立。
    • 全部 j\ (1 \leq j \lt i) , 当我输入P_j \lt P_i
    • 全部 j\ (1 \leq j \lt i) , 当我输入P_j \gt P_i

制約

  • 2 \leq N \leq 10^{18}
  • N 是一个整数

入力

输入是按以下格式从标准输入给出的。

N

出力

满足问题陈述中的条件的数字序列 打印除以 P 的数量 我们将其表示为 998244353 后的余数。


入力例 1

2

出力例 1

2

(1,2) 得到的序列为 (1,2) 和 按字典顺序比较 (2,1) 可以得到第 2 两者都满足问题陈述中的条件。


入力例 2

659636104093210683

出力例 2

512716103

998244353 后的余数。

原案: 企鹅人