Honi

Από ένα σωρό προτεινόμενων εργασιών, οι συντάκτες του COCI πρέπει να επιλέξουν αυτές που θα εμφανιστούν στον επόμενο γύρο.
Η δυσκολία μιας εργασίας περιγράφεται με έναν ακέραιο αριθμό στο εύρος ~1~ έως ~N~. Για ορισμένες εργασίες, ωστόσο, δεν είναι εύκολο να προσδιοριστεί ακριβώς η δυσκολία τους. Οι συντάκτες του COCI αποφάσισαν ότι αυτές οι εργασίες μπορούν να θεωρηθούν ότι έχουν μία από τις δύο διαδοχικές δυσκολίες. Για παράδειγμα, κάποια εργασία μπορεί να θεωρηθεί ότι έχει δυσκολία είτε ~3~ είτε ~4~.
Ο επόμενος γύρος COCI θα περιέχει ακριβώς ~N~ εργασίες. Για κάθε δυσκολία, θα υπάρχει ακριβώς μία εργασία με αυτή τη δυσκολία. Φυσικά, καμία εργασία δεν θα εμφανιστεί δύο φορές.
Βρείτε τον αριθμό των διαφορετικών τρόπων με τους οποίους οι συντάκτες μπορούν να επιλέξουν εργασίες για τον επόμενο γύρο. Λέμε ότι δύο τρόποι είναι διαφορετικοί αν για κάποια δυσκολία, ανατεθεί διαφορετική εργασία σε αυτή τη δυσκολία.
Εφόσον το αναμενόμενο αποτέλεσμα μπορεί να είναι πολύ μεγάλο, εξάγετε τον αριθμό των τρόπων modulo (το υπόλοιπο της διαίρεσης με) ~1\,000\,000\,007~.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον ακέραιο αριθμό ~N\;(2 \leq N \leq 100\,000)~.
Η δεύτερη γραμμή εισόδου περιέχει ~N~ ακέραιους όχι μεγαλύτερους από ~10^9~. Ο ~i~-οστός αριθμός σε αυτή τη γραμμή είναι ίσος με τον αριθμό των εργασιών σε ένα σωρό που έχουν δυσκολία ακριβώς ~i~.
Η τρίτη γραμμή εισόδου περιέχει ~N-1~ ακέραιους όχι μεγαλύτερους από ~10^9~. Ο ~i~-οστός αριθμός σε αυτή τη γραμμή είναι ίσος με τον αριθμό των εργασιών σε ένα σωρό που έχουν δυσκολία είτε ~i~ είτε ~i+1~.

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου πρέπει να περιέχει τον απαιτούμενο αριθμό τρόπων modulo (το υπόλοιπο της διαίρεσης με) ~1\,000\,000\,007~.

Παραδείγματα

input

3
3 0 1
0 1

output

3

input

4
1 5 3 0
0 2 1

output

33