Zenyk the Programmer

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Zenyk knows better than anyone that the easiest way to make a lot of money in IT is to change jobs frequently. That is why over the next \(m\) months, Zenyk will consider \(n\) companies. The monthly salary at company \(i\) is equal to \(a_i\). The chance of passing the interview at company \(i\) is equal to \(p_i\) percent.

Zenyk begins his career journey unemployed. At the beginning of each of the \(m\) months, Zenyk receives interview invitations from each of the \(n\) companies except the one he currently works for. Zenyk takes the interview at each of them. Those companies where Zenyk successfully passed the interview offer him a job. Zenyk can stay at his current company or agree to join one of the companies from which he has offers. The whole process happens very quickly, so Zenyk manages to instantly join the chosen company. At the end of each month, Zenyk receives a salary from the new company if he decided to change jobs, or from the old one if he decided to stay. After that, the process repeats. What is the expected value of Zenyk’s income for \(m\) months under the optimal job-changing strategy?

Input

The first line contains two integers — \(n\) and \(m\).

The next line contains \(n\) integers \(a_i\) — the monthly salary at company \(i\).

The next line contains \(n\) integers \(p_i\) — the probability in percent of passing the interview at company \(i\).

Output

Let \({p \over q}\) be the expected value of Zenyk’s total income. Find \(p \cdot q^{-1} \pmod{998244353}\).

Constraints

\(1 \le n, m \le 10^5\),

\(1 \le a_i \le 10^9\),

\(1 \le p_i \le 100\).

Samples