You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

辰辰得到了一些石子，非常开心。但他妈妈却让他全送人，他很不高兴，他想通过分裂石子使得其价值最小。

Description

辰辰有 $n$ 个石子，第 $i$ 个石子重量为 $a_i$，每个石子的价值是它重量的平方，即 $a_i\times a_i$，他可以进行 $m$ 次分裂操作，具体的，他可以将一个重量 $x$ 的石子劈成两个重量为 $\left \lfloor \frac{x}{2} \right \rfloor$ 的石子。其中 $\left \lfloor \frac{x}{2} \right \rfloor$ 表示 $x$ 除 $2$ 下取整。

他想通过这 $m$ 次分裂，使得所有石子的价值之和最小（注意分裂成的石子仍能继续分裂）。

Format

Input

由于输入量巨大，所以无需读入序列，只需读入四个正整数 $n,m,k,p,q$，其中 $n,m$ 如题意，数列生成代码如下。

Output

一行一个正整数，表示最小的价值之和，注意答案可能过大，请对 $998244853$ 取模。

Samples

6 6 6 6 6

611848849

Limitation

$1\le n,m\le10^7,1\le a_i\le 10^9$

注意：此题没有部分分，请不要渴望着用 $O(nlog_2n)$ 的算法骗取分数，请用 $O(nlog_wa_i)$ 复杂度的算法（$w$ 请取一个大一点的数字）。

此题可能略微卡常，请大家 register，inline 全用上，如果你用 STL 容器，请尽量手写（其实我特意卡了，但我保证不让各位手撕平衡树）。

关于取模（大佬勿看）：

• 就是 %
• $x+y$%$p=(x$%$p+y$%$p)$%$p$ （所以你可以一边加一边取模）

数列生成代码：

scanf("%lld%lld%lld%lld%lld", &n, &m, &k, &q, &p);
a[1] = k;
for (int i = 2; i <= n; ++ i) a[i] = (a[i - 1] * q + p) % 1000000000 + 1;

注意：数列生成代码的变量都是 long long 类型的。

如果你认为你的程序复杂度正确但是超时，可以在头文件下加上这个：

#define fastcall __attribute__((optimize("-O3")))
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")

一般能优化几百毫秒，本题时限已开到 std 的两倍以上。

注意：上面这一坨参加 $csp$ 和在洛谷提交时千万不要加，否则会爆零两行泪。

$csp$ 自动开 O2，洛谷可以选择开 O2。