Zoltan

Ο φίλος του Marton, ο Cero, έχει μια σειρά από ~N~ θετικούς ακέραιους. Στην αρχή, ο Cero γράφει τον πρώτο αριθμό στον πίνακα. Στη συνέχεια γράφει τον δεύτερο αριθμό στα αριστερά ή στα δεξιά του πρώτου αριθμού. Μετά από αυτό, γράφει τον τρίτο αριθμό στα αριστερά ή στα δεξιά όλων των αριθμών που γράφτηκαν μέχρι τώρα, κ.ο.κ.

Ο Marton ρώτησε τον Cero ποιο ήταν το μήκος της μεγαλύτερης δυνατής αυστηρά αυξανόμενης ακολουθίας (όχι απαραίτητα διαδοχικών στοιχείων).

Θέλει επίσης να μάθει τον αριθμό τέτοιων μεγάλων αυστηρά αυξανόμενων υποακολουθιών. Πιο συγκεκριμένα, αν το μήκος της μεγαλύτερης αυξανόμενης υποακολουθίας είναι ~M~, θέλει να μάθει το άθροισμα των αριθμών των αυστηρά αυξανόμενων υπακολουθιών μήκους ~M~ για κάθε πιθανή ακολουθία που μπορεί να κατασκευάσει ο Cero. Οι ακολουθίες είναι διαφορετικές εάν κατασκευάζονται χρησιμοποιώντας διαφορετική σειρά κινήσεων και οι υπακολουθίες σε μια κατασκευασμένη ακολουθία είναι διαφορετικές εάν διαφέρουν σε τουλάχιστον μία θέση.

Δεδομένου του γεγονότος ότι ο αριθμός τέτοιων υποακολουθιών μπορεί να είναι εξαιρετικά μεγάλος, ο Marton θα είναι ικανοποιημένος με την τιμή αυτού του αριθμού σε μορφή υπολοίπου ακέραιας διαίρεσης με το ~10^9 + 7~.

Ο Cero δεν έχει πραγματικά χρόνο αυτή τη στιγμή για να μάθει τις απαντήσεις στις ερωτήσεις του Marton, επομένως σας ζητά να το κάνετε για αυτόν.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον ακέραιο αριθμό ~N\;(1 \le N \le 2 * 10^5)~.
Η ακόλουθη γραμμή περιέχει ~N~ ακέραιους αριθμούς χωρισμένους με διαστήματα που αντιπροσωπεύουν τα στοιχεία του πίνακα του Cera. Κάθε αριθμός στην είσοδο θα είναι μικρότερος ή ίσος του ~10^9~.

Έξοδος

Πρέπει να εξάγετε, σε μία γραμμή, το μήκος της μεγαλύτερης αυστηρά αυξανόμενης υποακολουθίας και τον αριθμό των αυστηρά αυξανόμενων υποακολουθιών αυτού του μήκους, σε μορφή υπολοίπου ακέραιας διαίρεσης με το ~10^9 + 7~, αντίστοιχα.

Βαθμολογία

Σε δοκιμαστικές περιπτώσεις αξίας 30% των συνολικών πόντων, θα ισχύει ~N \le 20~.
Σε δοκιμαστικές περιπτώσεις αξίας 50% των συνολικών πόντων, θα ισχύει ~N \le 1\,000~.

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

input

2
1 1

output

1 4

Επεξήγηση του 1ου παραδείγματος:

Η μεγαλύτερη αυστηρά αυξανόμενη υποακολουθία που μπορεί να ληφθεί είναι μήκους 1 και υπάρχουν 4 από αυτές.
Η πρώτη δυνατή κατασκευή: σημειώνει το πρώτο 1, το δεύτερο 1 προς τα δεξιά: η ακολουθία που προκύπτει είναι 1,1; υπάρχουν δύο αυστηρά αυξανόμενες υποακολουθίες μήκους 1: 1 1 και 1 1. Η δεύτερη δυνατή κατασκευή: σημειώνει το πρώτο 1, το δεύτερο 1 προς τα αριστερά: η ακολουθία που προκύπτει είναι 1,1; υπάρχουν δύο αυστηρά αυξανόμενες υποακολουθίες μήκους 1: 1 1 & 1 1.

input

4
2 1 3 4

output

4 1

Επεξήγηση του 2ου παραδείγματος:

Η μεγαλύτερη αυστηρά αυξανόμενη υποακολουθία που μπορεί να ληφθεί είναι μήκους 4.
Μπορεί να ληφθεί μόνο εάν κατασκευάσει την ακολουθία ~1\;2\;3\;4~. Σε αυτήν την κατασκευή, είναι η μόνη αυστηρά αυξανόμενη υποακολουθία μήκους 4, οπότε ο αριθμός αυτών είναι 1.