Mobitel

Ο μικρός Nikola έμαθε πρόσφατα έναν πίνακα πολλαπλασιασμού. Για να προσπαθήσει να συνεχίσει να μαθαίνει, σκέφτηκε την παρακάτω εργασία.

Έφτιαξε έναν πίνακα μεγέθους ~R \times S~. Σε κάθε πεδίο του πίνακα έγραψε μια ακέραια τιμή και αναρωτήθηκε:
Πόσοι πιθανοί τρόποι υπάρχουν για να φτάσεις από την επάνω αριστερή γωνία στην κάτω δεξιά γωνία του πίνακα, μετακινούμενος σε κάθε βήμα σε ένα πεδίο δεξιά ή κάτω, έτσι ώστε το γινόμενο όλων των αριθμών στο μονοπάτι (συμπεριλαμβανομένου του αρχικού και του τελικού πεδίου) να είναι τουλάχιστον ~N~;

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

Είσοδος

Στην πρώτη γραμμή υπάρχουν οι ακέραιοι αριθμοί ~R~, ~S\;(1 \le R, S \le 300)~ και ~N\;(~1 \le N \le 10^6)~.

Στις επόμενες γραμμές ~R~ υπάρχουν ~S~ ακέραιοι αριθμοί μεταξύ του ~1~ και του ~10^6~, που δηλώνουν τους αριθμούς που είναι γραμμένοι σε κάθε πεδίο του πίνακα.

Έξοδος

Στη μοναδική γραμμή εξόδου τυπώστε το υπόλοιπο του απαιτούμενου αριθμού τρόπων στη μορφή modulo ~10^9 + 7~.

Βαθμολογία

Σε δοκιμαστικές περιπτώσεις συνολικής αξίας 20% των πόντων θα ισχύει ~N \le 300~.
Σε δοκιμαστικές περιπτώσεις συνολικής αξίας 20% των πόντων θα ισχύει ~R, S \le 100~ και όλοι οι αριθμοί στον πίνακα θα είναι μικρότεροι ή ίσοι με 10.
Σε δοκιμαστικές περιπτώσεις συνολικής αξίας επιπλέον 30% θα ισχύει ~R, S \le 100~.

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

input

2 3 200
2 3 4
5 6 7

output

2

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

Υπάρχουν τρεις πιθανοί τρόποι:

• 2->3->4->7 - συνολικό γινόμενο 168
  
• 2->3->6->7 - συνολικό γινόμενο 252
  
• 2->5->6->7 - συνολικό γινόμενο 420

input

3 3 90
2 1 1
45 1 1
1 1 1

output

3

input

2 5 3000
1 2 3 4 5
6 7 8 9 10

output

3