Superhero#11530
There is a new superhero in the city of Minsk — HyperKirill! Every day he serves the city and prevents crime.
HyperKirill has been saving the city for days. On day number he prevented b_i crimes, and the rate of Hyperruble in Minsk was equal to a_i.
Since the Minsk authorities are grateful to HyperKirill, they decided to support him financially as follows: if the balance of HyperKirill is and the Hyperruble rate is , for each crime prevented, the balance of HyperKirill becomes x \cdot y + x + y.
HyperKirill doesn't have time to count his money, because the city can't save itself! Help him do it. Before he appeared in the city, his balance was .
Since the number may be large, output it modulo 10^7 + 9.
The first line contains non-negative integer (1 \le n \le 10^5) — number of days.
The second line contains non-negative integers a_i (0 \le a_i \le 10^9) — Hyperruble rates.
The third line contains positive integers b_i (1 \le b_i \le 10^9) — the number of crimes prevented.
Output a single integer — the answer to the problem.
Example 1
Example 2
Example 3