Migrated from Lutece 2741 洛水神女

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

你有没有听说过一条叫做洛水的河？传说洛水有神名宓妃，是绝美的女神，曹植《洛神赋》所言即是此神。

不过这个题和洛水没什么关系，和洛神也没什么关系。

现在 rainy 有很多只刚出生的猫猫，这些猫猫和普通的猫猫不一样，第 $i$ 只猫猫只有在每次过完生日时才会有 $P_i$ 的概率死掉，在其他时候绝对不会死。

rainy 想知道这这些猫猫的期望寿命之和。

不过由于 rainy 也不完全想知道，所以你只需要给出这个期望值对 $10^9+7$ 取模的结果就可以了。

Input

第一行两个整数 $n,x\ (1\le n\le 5\times10^5, 0\le x\le 10^7)$，表示有 $n$ 只猫猫。

由于输入量较大，猫猫的死亡概率用以下这种方法给出：

首先定义如下所示的函数，其中 pair 是 STL 中的二元组，不影响正确性的情况下你可以将其改为其他形式。

pair<int, int> nextPair(int &x) {
    int a, b;
    x ^= x << 13; x ^= x >> 17; x ^= x << 5; x %= 10000000; a = x;
    x ^= x << 13; x ^= x >> 17; x ^= x << 5; x %= 10000000; b = x;
    b = max(b, 1); a = max(a % b, 1);
    return make_pair(a, b);
}

使用此函数，以读入的 $x$ 作为初始值调用 $n$ 次后你应该会有 $n$ 个 pair<int, int>，记为 $p_1,p_2,\dots,p_n$，将 $p_i$ 记为 $(a_i,b_i)$。

那么每只猫猫的死亡概率 $P_i$ 可以表示为 $\frac{a_i}{b_i}$。

Output

输出一行一个整数，表示答案。

Samples

1 1

282743244

Note

众所周知的是，虽然刚出生的那一天确实也能算生日，但是我们不会说刚出生的猫猫过生日了。

如果你对寿命的定义有所疑问的话，不妨将其定义为猫猫过生日的次数。

Resources

2022 UESTC ICPC Training for Math and Geometry