Superqəhrəman#11530
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 gündür ki, şəhəri xilas edir. -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ı , HiperRublun məzənnəsi isə -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ı idi.
Çünki rəqəm böyük ola bilər, onu 10^7 + 9 modulu ilə çıxarın.
Birinci sətirdə tam ədəd n~(1 \le n \le 10^5) — günlərin sayı verilir.
İkinci sətir tam ədədi a_i~(0 \le a_i \le 10^9) — HiperRublun məzənnələrini ehtiva edir.
Üçüncü sətir tam ədədi b_i~(1 \le b_i \le 10^9) — qarşısı alınan cinayətlərin sayını ehtiva edir.
Yeganə tam ədəd çıxarın — məsələnin cavabı.
Nümunə 1
Nümunə 2
Nümunə 3