题目描述

众所周知石老板是一个憨憨，Ta 有一次写程序的时候写了这样的函数：

void calc(int s) {
    double l = a, r = b;
    int cnt = 0;
    while(cnt != s) {
        double mid = (l + r) / 2;
        if(check(mid)) l = mid;
        else r = mid;
        cnt ++;
    }
    cout << (l + r) / 2;
}

其中 check 函数被只会随机返回 $0$ 或者 $1$，其返回 $0$ 和 $1$ 的概率分别为 $P_0$ 和 $P_1$，上面的程序只会执行 $s$ 次。现在给定 $s$, $l,r$ 的初始值 $a,b$ 以及 $P_0,P_1$，不考虑浮点数误差的情况下，你需要输出 石老板 这个程序输出的答案的 期望值 对于 998244353 取模后的答案是多少。

注意，$a>b$ 也是可能的。

输入格式:

第一行五个整数 $a, b, s,P_0,P_1$·

其中 $0 \leq P_0,P_1 \leq 100$

表示 check 返回 $0$ 的概率是 $P_0\%$ ，返回 $1$ 的概率是 $P_1 \%$，保证 $P_0 + P_1 = 100$。

输出格式：

一行，一个整数表示上面的函数输出答案的期望值对于 998244353 取模后的结果。

输入样例：

1 2 1 50 50

输出样例：

499122178

样例解释：

因为得到的结果的期望是 1.5，其对于 998244353 取模后的结果即 499122178

样例输入

32676 511511 20 50 50

样例输出

499394270

ex_issue3.in/ex_issue3.ans​ 表示下面的 $s \leq 10^7$ 的数据

数据范围：

对于 $20 \%$ 的数据保证：$s \leq 20$

对于另外 $12 \%$ 的数据保证： $P_0 = P_1 = 50$ 并且 $s \leq 10^7$

对于另外 $28 \%$ 的数据保证：$s \leq 10^7$

对于 $100 \%$ 的数据保证： $1 \leq a , b < 998244353,1\le s \leq 10^{18}$, $P_0 + P_1 = 100, 0 \leq P_0,P_1 \leq 100$

样例下载