Супергерой

В городе Минск появился новый супергерой — ГиперКирилл! Каждый день он служит на благо города и предотвращает преступления.

ГиперКирилл спасает город уже на протяжении $n$ дней. В день под номером $i$ он предотвратил $b_i$ преступлений, а курс Гиперрубля в Минске был равен $a_i$.

Так как власти Минска благодарны ГиперКириллу, они решили финансово поддержать его следующим образом: если баланс ГиперКирилла равен $x$, а курс Гиперрубля равен $y$, то за одно предотвращенное преступление баланс ГиперКирилла станет равен $x\cdot y+x+y$.

ГиперКириллу некогда считать свои деньги, ведь город сам себя не спасёт! Помогите ему это сделать. Перед появлением в городе, его баланс был равен $0$.

Так как число может оказаться большим, выведите его по модулю $10^7+9$.

Входные данные

В первой строке вводится целое неотрицательное число $n(1\le n\le 10^5)$ — количество дней.

Вторая строка содержит $n$ целых неотрицательных чисел $a_i(0\le a_i\le 10^9)$ — курсы Гиперрубля.

Третья строка содержит $n$ целых неотрицательных чисел $b_i(1\le b_i\le 10^9)$ — количества предотвращенных преступлений.

Выходные данные

Выведите единственное целое число — ответ на задачу.

Примеры