Супергерой#11530
У місті Центроград з'явився новий супергерой — ГіперКирило! Щодня він служить на благо міста, запобігаючи злочинам.
ГіперКирило вже рятує місто протягом днів. У день під номером він запобіг b_i злочинам, а курс Гіперкоїна у Центрограді становив a_i.
Влада Центрограда, вдячна ГіперКирилу, вирішила підтримати його фінансово таким чином: якщо баланс ГіперКирила дорівнює , а курс Гіперкоїна дорівнює , то за кожен запобігнутий злочин баланс ГіперКирила стане рівним x \cdot y + x + y.
ГіперКирило не має часу рахувати свої гроші, адже місто саме себе не врятує! Допоможіть йому. Перед тим, як з'явитися у місті, його баланс був .
Оскільки число може виявитися великим, виведіть його за модулем 10^7 + 9.
У першому рядку вводиться ціле число (1 \le n \le 10^5) — кількість днів.
Другий рядок містить цілих чисел a_i (0 \le a_i \le 10^9) — курси Гіперкоїна.
Третій рядок містить цілих чисел b_i (1 \le b_i \le 10^9) — кількості запобігнутих злочинів.
Виведіть одне ціле число — відповідь на задачу.
Приклад 1
Приклад 2
Приклад 3