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 n days. On day number i he prevented bi crimes, and the rate of Hyperruble in Minsk was equal to ai.
Since the Minsk authorities are grateful to HyperKirill, they decided to support him financially as follows: if the balance of HyperKirill is x and the Hyperruble rate is y, the balance of HyperKirill will be x⋅y+x+y for one crime prevented.
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 0.
Since the number may be large, output it modulo 107+9.
The first line contains non-negative integer n (1≤n≤105) — number of days.
The second line contains n non-negative integers ai (0≤ai≤109) — Hyperruble courses.
The third line contains n non-negative integers bi (1≤bi≤109) — the number of crimes prevented.
Output a single integer — the answer to the problem.