区间里的幂之和

题目描述

给定 a、L、R、m，求 (a^L+a^(L+1)+…+a^R) mod m，区间包含L和R。

输入格式

一行输入 a、L、R、m，满足 0≤a≤10^9、1≤L≤R≤10^18、1≤m≤2×10^5。

输出格式

输出区间幂和的标准余数。

样例

输入

2 1 2026 7

输出

2