给定一个从下标 0 开始的无限周期二进制字符串 $S$。这意味着 $S = TTTT \dots$，其中 $T$ 是字符串 $S$ 的周期。例如，若 $T = 101$，则 $S = 101101101101 \dots$。
$S[l, r]$ 是 $S$ 的子串。我们将 $S[l, r]$ 视为二进制数，并将其值定义为 $f[l, r]$。
请计算满足以下条件的长度为 $k$ 的二进制字符串 $T$ 的数量：$f[l, r] \equiv x \pmod p$。
结果可能非常大，请输出结果对 $10^9 + 7$ 取模后的值。
输入格式
输入包含不超过 162 组测试数据，以一行五个零作为结束。
对于每组测试数据，包含一行五个数字 $p$ ($2 < p < 10^{18}$，$p$ 为质数)、$x$ ($0 \le x < p$)、$l$、$r$ ($0 \le l \le r \le 10^{18}$) 和 $k$ ($1 \le k \le 10^{18}$)。
输出格式
对于每组测试数据，输出答案对 $10^9 + 7$ 取模后的结果。
样例
样例输入 1
3 0 1 2 1 233 23 2333 23333 23 233 1 1 2 23 0 0 0 0 0
样例输出 1
2 36003 2097152