Sažetak

Ένας άγνωστος πίνακας ~x~ αποτελείται από ~N~ ακέραιους αριθμούς. Η ~K~-σύνοψη αυτού του πίνακα προκύπτει με διαίρεση του πίνακα σε τμήματα μήκους ~K~ και άθροιση των στοιχείων σε κάθε τμήμα. Εάν το \(Ν\) δεν διαιρείται με το \(Κ\), το τελευταίο τμήμα της διαίρεσης θα έχει λιγότερα από στοιχεία \(Κ\).

Με άλλα λόγια, η σύνοψη ~K~ είναι ένας πίνακας όπου τα στοιχεία είναι, αντίστοιχα: ~(x[1]\;+\;\ldots\;+\;x[K]),\;(x[K+1]\;+\;\ldots\;+\;x[2K])~, και ούτω καθεξής, όπου το τελευταίο άθροισμα που περιέχει ~x[N]~ μπορεί να έχει λιγότερα από ~K~ αθροίσματα. Για παράδειγμα, η 5-σύνοψη ενός πίνακα 13 στοιχείων έχει τρία στοιχεία (άθροισμα στοιχείων ~1.-5.~, άθροισμα στοιχείων ~6.-10.~, άθροισμα στοιχείων ~11.-13.~).

Είναι σαφές ότι δεν μπορούμε να ανακατασκευάσουμε τα στοιχεία του αρχικού πίνακα από τη σύνοψη ~K~, αλλά αυτό θα μπορούσε να είναι δυνατό αν γνωρίζαμε αρκετές ~K~-συνόψεις για διαφορετικά ~K~. Γράψτε ένα πρόγραμμα που, δεδομένου μήκους ~N~ και ορισμού ~K_1,\;K_2,\;\ldots,\;K_M~, θα προβλέψει πόσα στοιχεία του αρχικού πίνακα θα μπορούσαμε να προσδιορίσουμε μοναδικά αν γνωρίζαμε όλες τις ~K_i~-περιλήψεις του πίνακα. (Δεν είναι δύσκολο να δείξουμε ότι ο αριθμός των ανακατασκευασμένων στοιχείων είναι ανεξάρτητος από το περιεχόμενο των συνόψεων.)

Είσοδος

Η πρώτη γραμμή περιέχει τους ακέραιους αριθμούς ~N~ και ~M\;(3 \le N \le 10^9,\;1 \le M \le 10)~, το μήκος του πίνακα και τον αριθμό των K-περιλήψεων.
Η δεύτερη γραμμή περιέχει τους διακριτούς ακέραιους αριθμούς ~K_1,\;K_2,\;\ldots,\;K_M\; (2 \le K_i < N)~.

Έξοδος

Πρέπει να τυπώσετε τον απαιτούμενο αριθμό των ανακατασκευασμένων στοιχείων.

Βαθμολογία

Σε δοκιμαστικές περιπτώσεις αξίας 40% των συνολικών πόντων, θα ισχύει \(N​\le 5\,000\,000\).

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

input

3 1
2

output

1

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

Μπορούμε να προσδιορίσουμε ένα στοιχείο: ~x[3]~.

input

6 2
2 3

output

2

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

Μπορούμε να προσδιορίσουμε τα ~x[3]~ και ~x[4]~.

input

123456789 3
5 6 9

output

10973937