Зеник-програміст

Limits: 2 sec., 256 MiB

Зеник, як ніхто інший знає, що найлегший спосіб багато заробляти у ІТ — це часто міняти роботу. Саме тому Зеник протягом наступних \(m\) місяців розгляне \(n\) компаній. Місячна зарплата в компанії \(i\) рівна \(a_i\). Шанс пройти інтерв’ю у компанію \(i\) рівний \(p_i\) у відсотках.

Зеник починає свою кар’єрну подорож непрацевлаштованим. На початку кожного з \(m\) місяців Зеник отримує запрошення на співбесіди від кожної з \(n\) компаній крім тієї, у якій він працює зараз. Зеник проходить інтерв’ю у кожну з них. Ті компанії, в які Зеник успішно пройшов інтерв’ю, пропонують йому роботу. Зеник може залишитись у своїй поточній компанії або погодитись приєднатись до однієї з компаній, від яких має пропозиції. Увесь процес відбувається дуже швидко, тому Зеник встигає миттєво приєднатись до вибраної компанії. Наприкінці кожного місяця Зеник отримує зарплату від нової компанії, якщо він вирішив змінити роботу, або від старої, якщо він вирішив залишитись. Після цього процес повторюється. Яке математичне очікування доходу Зеника за \(m\) місяців при правильній стратегії зміни роботи?

Input

У першому рядку задано два цілих числа — \(n\) та \(m\).

У наступному рядку задано \(n\) цілих чисел \(a_i\) — місячна заробітня плата в компанії \(i\).

У наступному рядку задано \(n\) цілих чисел \(p_i\) — ймовірність у відсотках пройти співбесіду у компанію \(i\).

Output

Нехай \(p \over q\) — математичне очікування сумарного доходу Зеника. Знайдіть \(p \cdot q^{-1} (mod\ 998244353)\).

Constraints

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

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

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

Samples