[ABC178C] Ubiquity
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
[ABC178C] Ubiquity
题面翻译
有一个长为 的数列 ,其中对于每个 都有 ,并保证数列中至少有一个 为 且至少有一个 为 。输入 ,输出满足条件的序列的个数对 取模之后的余数。
题目描述
長さ の整数の列 であって以下の条件をすべて満たすものはいくつありますか。
- なる が存在する。
- なる が存在する。
ただし、答えはとても大きくなる可能性があるので、 で割った余りを出力してください。
输入格式
入力は以下の形式で標準入力から与えられる。
输出格式
答えを で割った余りを出力せよ。
样例 #1
样例输入 #1
2
样例输出 #1
2
样例 #2
样例输入 #2
1
样例输出 #2
0
样例 #3
样例输入 #3
869121
样例输出 #3
2511445
提示
制約
- は整数
Sample Explanation 1
数列,の つが条件をすべて満たします。