The Lights Going On and Off

Για τα γενέθλιά σας, σας δόθηκε ένα πλέγμα από ~R\;(1 < R < 30)~ σειρές από φώτα, με κάθε σειρά να περιέχει ~L\;(1 \le L < 8)~ φώτα. Τα φώτα μπορούν να βρίσκονται σε μία από δύο καταστάσεις: on (αναμμένα) ή off (σβηστά). Για αυτό το ερώτημα, η πιο πάνω σειρά είναι η σειρά ~R~ και η πιο κάτω σειρά είναι η σειρά ~1~. Επίσης, δίπλα σε όλες τις σειρές εκτός από την πιο πάνω σειρά (τη σειρά ~R~), υπάρχει ένα κουμπί που μπορεί να πατηθεί.

Πατόντας το κουμπί δίπλα σε μια σειρά ~k\;(1 \le k < R)~, πραγματοποιείται μια πράξη "exclusive-or" ("αποκλειστικής διάζευξης") σε κάθε φως της σειράς ~k~, η οποία περιγράφεται παρακάτω. Ας θεωρήσουμε τη στήλη ~i~ της σειράς ~k~, όπου ~1 \le i \le L~. Εάν τα φώτα της στήλης ~i~ της σειράς ~k~ και της στήλης ~i~ της σειράς ~k + 1~ βρίσκονται στην ίδια κατάσταση (δηλαδή και τα δύο on ή και τα δύο off), τότε το πάτημα του κουμπιού που είναι δίπλα στη σειρά ~k~ θα έχει ως αποτέλεσμα το φως στη στήλη ~i~ της σειράς ~k~ να σβήσει (off). Εάν τα φώτα στη στήλη ~i~ της σειράς ~k~ και στη στήλη ~i~ της σειράς ~k + 1~ βρίσκονται σε διαφορετικές καταστάσεις (δηλαδή το ένα είναι on και το άλλο off), τότε το πάτημα του κουμπιού δίπλα στη σειρά ~k~ θα έχει ως αποτέλεσμα το φως στη στήλη ~i~ της σειράς ~k~ να ανάψει (on). Ένα παράδειγμα παρουσιάζεται παρακάτω, για ~L = 4~:

Αριθμοί στηλών	~1~	~2~	~3~	~4~
Σειρά ~k + 1~	on	on	off	off
Σειρά ~k~ πριν πατηθεί το κουμπί	on	off	on	off
Σειρά ~k~ αφού πατηθεί το κουμπί	off	on	on	off

Γνωρίζετε από πριν ποια φώτα είναι αρχικά αναμμένα και ποια είναι αρχικά σβηστά. Πρέπει να υπολογίσετε πόσα διαφορετικά μοτίβα φωτισμού είναι πιθανά για την πιο κάτω σειρά, με οποιαδήποτε ακολουθία πατημάτων κουμπιών.

Είσοδος

Η πρώτη γραμμή της εισόδου θα περιέχει τον ακέραιο ~R~, τον αριθμό των σειρών. Η δεύτερη γραμμή εισόδου της θα περιέχει τον ακέραιο ~L~, τον αριθμό των φώτων ανά γραμμή. Οι επόμενες ~R~ γραμμές της εισόδου θα περιέχουν ~L~ ακέραιους αριθμούς, όπου ο ακέραιος αριθμός θα είναι είτε ~0~ (για να δηλώσει την κατάσταση "off") είτε ~1~ (για να δηλώσει την κατάσταση "on"). Τα ζεύγη διαδοχικών ακεραίων θα χωρίζονται με ένα κενό διάστημα. Αυτές οι ~R~ γραμμές θα δίνονται με σειρά από πάνω προς τα κάτω: δηλαδή, η τρίτη γραμμή της εισόδου θα είναι η περιγραφή της σειράς ~R~, η τέταρτη γραμμή θα είναι η περιγραφή της σειράς ~R - 1~, κ.ο.κ., έως την τελευταία γραμμή που θα περιγράφει την πιο κάτω σειρά.

Έξοδος

Εξάγετε τον αριθμό των πιθανών μοτίβων φωτισμού της κάτω σειράς.

Παράδειγμα

input

4
3
0 0 1
0 1 1
1 0 1
0 0 1

output

4