Repetitivity

Οποιαδήποτε συμβολοσειρά (string) μήκους ~n~ έχει ~2^n~ υποακολουθίες, οι οποίες είναι οι συμβολοσειρές που προκύπτουν αφαιρώντας ένα υποσύνολο των χαρακτήρων. Αλλά αυτές οι υποακολουθίες μπορεί να μην είναι όλες μοναδικές. Για παράδειγμα, η συμβολοσειρά "zoo" έχει μόνο ~6~ μοναδικές υποακολουθίες:

• οι υποακολουθίες "z", "oo" και "zoo" εμφανίζονται μόνο μία φορά,

• η κενή υποακολουθία εμφανίζεται μόνο μία φορά,

• και οι υποακολουθίες "o" και "zo" εμφανίζονται από δύο φορές.

Υποθέστε ότι μία συμβολοσειρά ~S~ έχει ~k~ μοναδικές υποακολουθίες και η ~i~-οστη εμφανίζεται ~f_i~ φορές. Τότε η επαναληψιμότητα του ~S~ ορίζεται ως ~\Sigma_{i=1}^k = f_i^2~. Για παράδειγμα, η επαναληψιμότητα του "zoo" είναι

~1^2 + 1^2 + 1^2 + 1^2 + 2^2 + 2^2 = 12~.

Είσοδος

Κάθε περίπτωση ελέγχου περιέχει μία γραμμή που περιέχει τη συμβολοσειρά ~S~ (με μήκος το πολύ ~10\,000~), ακολουθούμενη από μία γραμμή που περιέχει έναν ακέραιο ~M~ (~2 \le M \le 1\,000\,000\,000~). Μπορείτε να υποθέσετε ότι το ~S~ περιέχει μόνο χαρακτήρες με κωδικούς ASCII μεταξύ του κλειστού διαστήματος [~33, 126~] (είναι όλοι εκτυπώσιμοι, μη-κενοί χαρακτήρες).

Βαθμολογία

Για τις περιπτώσεις ελέγχου αξίας 20% των βαθμών, μπορείτε να υποθέσετε ότι το ~S~ θα έχει μήκος το πολύ ~20~ χαρακτήρες.

Έξοδος

Η έξοδος θα πρέπει να αποτελείται από μία γραμμή, που περιέχει την επαναληψιμότητα του S, ως υπόλοιπο ακέραιας διαίρεσης με το ~M~ (modulo ~M~).

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

input

zoo
10

output

2

input

@#$%
1000000

output

16