24ος ΠΔΠ Καμπ (κοινά)
Παράθεση συμβολοσειρών (concat)

Δίνεται ένα σύνολο \(A = \lbrace a_1, \ldots , a_N \rbrace\) αποτελούμενο από \(N\) μη κενές συμβολοσειρές, διαφορετικές μεταξύ τους, αποτελούμενες από τα μικρά γράμματα του λατινικού αλφαβήτου. Δίνεται επίσης μία μη κενή συμβολοσειρά \(\beta\) στο ίδιο αλφάβητο. Ζητείται να υπολογισθεί με πόσους διαφορετικούς τρόπους μπορεί να παραχθεί η συμβολοσειρά \(\beta\) ως παράθεση οσοδήποτε πολλών συμβολοσειρών του συνόλου \(A\). Σημειώνεται ότι κάθε συμβολοσειρά του συνόλου \(A\) μπορεί να χρησιμοποιηθεί οσεσδήποτε φορές χρειαστεί για την παραγωγή της \(\beta\).

Επειδή το πλήθος των διαφορετικών τρόπων μπορεί να είναι πολύ μεγάλο, ζητείται να υπολογίσετε το υπόλοιπο της διαίρεσής του με τον αριθμό \(3.141.592.653.589.793\). (Προσέξτε ότι για να αναπαρασταθεί ο αριθμός αυτός στο δυαδικό σύστημα δεν επαρκούν \(32\) bit.)

Αρχεία Εισόδου (concat.in):

Η πρώτη γραμμή της εισόδου θα περιέχει το πλήθος \(N\) των συμβολοσειρών του συνόλου \(A\). Οι επόμενες \(N\) γραμμές θα περιέχουν τις \(N\) συμβολοσειρές \(a_1, \ldots, a_N\). Η τελευταία γραμμή θα περιέχει τη συμβολοσειρά \(\beta\). Κάθε γραμμή που περιέχει συμβολοσειρά θα αποτελείται από ένα ή περισσότερα διαδοχικά μικρά γράμματα του λατινικού αλφαβήτου, χωρίς κενά διαστήματα στην αρχή, στο τέλος ή ενδιάμεσα, και θα τελειώνει με το χαρακτήρα αλλαγής γραμμής.

Αρχεία Εξόδου (concat.out):

Η έξοδος πρέπει να αποτελείται από μία γραμμή που να περιέχει ακριβώς έναν ακέραιο αριθμό, το πλήθος των τρόπων με τους οποίους μπορεί η συμβολοσειρά \(\beta\) να παραχθεί ως παράθεση οσοδήποτε πολλών συμβολοσειρών του συνόλου \(A\), modulo \(3.141.592.653.589.793\). Σε περίπτωση που η συμβολοσειρά \(\beta\) δεν μπορεί να παραχθεί με κανέναν τρόπο, η έξοδος πρέπει να είναι \(0\).

Παραδείγματα Αρχείων Εισόδου - Εξόδου:

1^o

concat.in	concat.out
2 a b abaabbb	1

2^o

concat.in	concat.out
4 a b aa bb abaabbb	6

Εξήγηση 2^ου παραδείγματος: Για το παράδειγμα εισόδου 2, οι \(6\) δυνατοί τρόποι να παραχθεί η συμβολοσειρά \(\texttt{abaabbb}\) είναι:

• \(\texttt{a + b + a + a + b + b + b}\),
• \(\texttt{a + b + a + a + b + bb}\),
• \(\texttt{a + b + a + a + bb + b}\),
• \(\texttt{a + b + aa + b + b + b}\),
• \(\texttt{a + b + aa + b + bb}\),
• \(\texttt{a + b + aa + bb + b}\).

3^o

concat.in	concat.out
3 a aa aaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa	98950096

Περιορισμοί:

• \(1 \leq N \leq 1.000\).
• Κάθε μία από τις συμβολοσειρές \(a_1, \ldots , a_N\) θα έχει το πολύ \(1.000\) χαρακτήρες.
• Η συμβολοσειρά \(\beta\) θα έχει το πολύ \(1.000.000\) χαρακτήρες.
• Όριο χρόνου εκτέλεσης: \(1\) sec.
• Όριο μνήμης: \(64\) MB.