Description

所有由节点0-K组成，且以0为根的不同的树，(注意共有 K +1个节点)，如果放在一起，就会形成一个 K -迷幻森林。我们记做 F~K~ （当K取不同值时可以得到不同的迷幻森林）。

我们定义：一棵有根树的叶子，就是度为1的非根节点。

在这题中，我们研究的是一个迷幻森林中所有树的叶子个数 Sum ( F~K~ )。

给出 P , L , R , A 。

在 *L * ≤ K * ≤ R中求： Sum ( F~K~ ) = A * (mod P ) 的不同的K有多少个。

Format

Input

每个数据只有一行，为四个正整数P L R A 。 其中P为质数。

Output

对每一个数据输出一行，即答案。

Samples

【样例输入1】
3 1 3 1
【样例输入2】

【样例输出1】
2

【样例输出2】
641

Limitation

【数据说明】 100%的数据满足 0 ≤ A < P ≤ 105；1 ≤ L ≤ R ≤ ­1018