Superqəhrəman

Minsk şəhərində yeni bir super qəhrəman ortaya çıxdı — HiperKirill! O, hər gün şəhərin rifahı üçün çalışır və cinayətlərin qarşısını alır.

HiperKirill artıq $n$ gündür ki, şəhəri xilas edir. $i$-ci gündə o, $b_i$ cinayətin qarşısını aldı və həmin gün Minskdə HiperRublun məzənnəsi $a_i$ idi.

Minsk hakimiyyəti HiperKirillə təşəkkür etmək üçün ona maliyyə dəstəyi göstərmək qərarına gəldi: əgər HiperKirillin balansı $x$, HiperRublun məzənnəsi isə $y$-dirsə, onda bir cinayətin qarşısını almaqla HiperKirillin balansı $x\cdot y+x+y$-ə çevriləcək.

HiperKirillin pulunu hesablamağa vaxtı yoxdur, çünki şəhər öz-özünə xilas olmayacaq! Ona bu işdə kömək edin. Şəhərə gəlməzdən əvvəl onun balansı $0$ idi.

Çünki rəqəm böyük ola bilər, onu $10^7+9$ modulu ilə çıxarın.

Giriş verilənləri

Birinci sətirdə tam ədəd $n(1\le n\le 10^5)$ — günlərin sayı verilir.

İkinci sətir $n$ tam ədədi $a_i(0\le a_i\le 10^9)$ — HiperRublun məzənnələrini ehtiva edir.

Üçüncü sətir $n$ tam ədədi $b_i(1\le b_i\le 10^9)$ — qarşısı alınan cinayətlərin sayını ehtiva edir.

Çıxış verilənləri

Yeganə tam ədəd çıxarın — məsələnin cavabı.

Nümunələr