← 返回题目列表

AtCoder · ttpc2019_i

I. 我讨厌P

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

配点 : 100 点

問題文

\mathbb{N}为所有正整数的集合, 定义f:\mathbb{N}\rightarrow\mathbb{N} 如下。 给定

f(x):=\begin{cases}f\left(\frac xP\right)&\text{if}\quad x\equiv 0 \pmod{P}\\x&\text{otherwise}\end{cases}

整数 (P,Q,L,R) ,在一行中打印以下值。 请输出

\text{ans}=\displaystyle\left(\prod_{i=L}^{R}f(i)\right) \ \bmod Q

制約

  • 所有输入均为整数
  • 2\leq P, Q \leq 10^7
  • 1\leq L\leq R\leq 10^{18}

入力

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

P Q
L R

出力

\displaystyle\left(\prod_{i=L}^{R}f(i)\right) \ \bmod Q \ 的值。


入力例 1

2 5
6 9

出力例 1

4
  • f(6)\times f(7)\times f(8)\times f(9)=3\times 7\times 1\times 9=189 因此,要输出的值为 请注意 189 \bmod 5=4 。

入力例 2

3 3
57 61

出力例 2

1
  • f(57)=19 。

入力例 3

65536 2
7 9

出力例 3

0

入力例 4

7878 78787
1234 56789

出力例 4

14334

入力例 5

2 4
1 81357343004

出力例 5

1