Voda

Ο Mirko, ο τρελός υδραυλικός, προσλήφθηκε για να κατασκευάσει ένα δίκτυο ύδρευσης μεταξύ δύο τοποθεσιών σε μια πόλη. Ο χάρτης της πόλης μπορεί να αναπαρασταθεί ως πλέγμα ~R \times S~. Ορισμένα κελιά δεν είναι κατάλληλες για τοποθέτηση σωλήνων νερού. Οι θέσεις που χρειάζεται να συνδεθεί ο Mirko τοποθετούνται ακριβώς πάνω από το επάνω αριστερό κελί του πλέγματος και ακριβώς κάτω από το κάτω δεξιό κελί.
Κάθε κατάλληλο κελί Mirko μπορεί είτε να το αφήσει άδειο είτε να το χρησιμοποιήσει για την τοποθέτηση ενός από τους παρακάτω 6 τύπους σωλήνων:

Βρείτε τον αριθμό των τρόπων με τους οποίους μπορούν να τοποθετηθούν σωλήνες για τη σύνδεση των δύο θέσεων με έναν συνεχή σωλήνα (δεν πρέπει να χυθεί νερό). Όλα τα τοποθετημένα εξαρτήματα σωλήνα πρέπει να χρησιμοποιούνται.
Έξοδος της λύσης modulo 10007.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τους ακέραιους ~R~ και ~S\;(2 \leq R,\;S \leq 10)~, τον αριθμό των γραμμών και στηλών του πλέγματος πόλεων, αντίστοιχα. Κάθε μία από τις επόμενες ~R~ γραμμές περιέχει ακριβώς ~S~ χαρακτήρες: "." εάν το κελί είναι κατάλληλο για τοποθέτηση σωλήνων και "#" εάν όχι.

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου πρέπει να περιέχει τον απαιτούμενο αριθμό τρόπων modulo(το υπόλοιπο της διαίρεσης με) 10007.

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

input

2 3
...
.#.

output

1

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

αυτή είναι η μόνη δυνατή λύση:

input

3 3
...
...
...

output

12