Bomboni

Η Iva λατρεύει τα ζαχαρωτά! Μπροστά της είναι ένα πεδίο ~n~ επί ~n~ γεμάτο με ζαχαρωτά και εμπόδια. Η Iva είναι αυτή τη στιγμή στο πιο πάνω αριστερά κελί του πεδίου και κινούμενη μόνο κάτω και δεξιά θα κινηθεί στο πιο κάτω δεξιά. Το κελί στο οποίο βρίσκεται αυτή τη στιγμή η Iva δεν περιέχει εμπόδιο.

Σε κάθε κελί, υπάρχει είτε ένα εμπόδιο είτε ένα ζαχαρωτό με έναν αριθμό γραμμένο πάνω του. Η Iva θα φάει όλα τα ζαχαρωτά που θα πάρει στη διαδρομή της (συμπεριλαμβανομένου και του ζαχαρωτού στο πρώτο και στο τελευταίο κελί) και έπειτα θα πολλαπλασιάσει όλους τους αριθμούς που είναι γραμμένοι πάνω τους. Η Iva γνωρίζει ότι ο αγαπημένος της αριθμός είναι το ~k~ και θέλει το αποτέλεσμα του πολλαπλασιασμόυ των αριθμών που είναι γραμμένοι στα γλυκά που έχει φάει να διαιρείται με το ~k~. Θέλει να ξέρει πόσα τέτοια μονοπάτια υπάρχουν. Επειδή ο αριθμός αυτός μπορεί να είναι τεράστιος, την ενδιαφέρει ως υπόλοιπο ακέραιας διαίρεσης με το ~9~~9~~8~~2~~4~~4~~3~~5~~3~.

Είσοδος

Η πρώτη γραμμή περιέχει δύο ακέραιους ~n~ και ~k~ (~1~ ~\le~ ~n~ ~\le~ ~500~, ~1~ ~\le~ ~k~ ~\le~ ~10^6~), οι οποίοι δηλώνουν το μέγεθος του πεδίου και τον αγαπημένο αριθμό τη Iva.

Σε καθεμία από τις επόμενες ~n~ γραμμές, υπάρχουν ~n~ αριθμοί που περιγράφουν την ~i~-οστή σειρά του πεδίου (~-1~ ~\le~ ~a_{ij}~ ~\le~ ~10^6~). Αν ~a_{ij}~ = ~-1~, τότε εκείνο το κελί περιέχει ένα εμπόδιο, αλλιώς ~1~ ~\le~ ~a_{ij}~ ~\le~ ~10^6~ και εκείνο το κελί περιέχει ένα ζαχαρωτό με εκείνο τον αριθμό.

Έξοδος

Εκτυπώστε μια γραμμή με τον απαιτούμενο αριθμό από το πρόβλημα.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	13	~n~,~k~,~a_{ij}~ ~\le~ ~20~
2	17	~n~,~k~ ~\le~ ~20~
3	33	~k~ ~\le~ ~20~
4	47	Κανένας επιπλέον περιορισμός.

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

input

2 2
3 2
1 4

output

2

input

3 6
5 2 -1
7 3 6
-1 3 1

output

3

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

Υπάρχουν τρία πιθανά μονοπάτια ώστε το αποτέλεσμα να διαιρείται με το ~6~: ~5~ ~\cdot~ ~2~ ~\cdot~ ~3~ ~\cdot~ ~3~ ~\cdot~ ~1~, ~5~ ~\cdot~ ~2~ ~\cdot~ ~3~ ~\cdot~ ~6~ ~\cdot~ ~1~, ~5~ ~\cdot~ ~7~ ~\cdot~ ~3~ ~\cdot~ ~6~ ~\cdot~ ~1~.