Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

F. Special Matrices

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputAn *n* × *n* square matrix is special, if:

- it is binary, that is, each cell contains either a 0, or a 1;
- the number of ones in each row and column equals 2.

You are given *n* and the first *m* rows of the matrix. Print the number of special *n* × *n* matrices, such that the first *m* rows coincide with the given ones.

As the required value can be rather large, print the remainder after dividing the value by the given number *mod*.

Input

The first line of the input contains three integers *n*, *m*, *mod* (2 ≤ *n* ≤ 500, 0 ≤ *m* ≤ *n*, 2 ≤ *mod* ≤ 10^{9}). Then *m* lines follow, each of them contains *n* characters — the first rows of the required special matrices. Each of these lines contains exactly two characters '1', the rest characters are '0'. Each column of the given *m* × *n* table contains at most two numbers one.

Output

Print the remainder after dividing the required value by number *mod*.

Examples

Input

3 1 1000

011

Output

2

Input

4 4 100500

0110

1010

0101

1001

Output

1

Note

For the first test the required matrices are:

011

101

110

011

110

101

In the second test the required matrix is already fully given, so the answer is 1.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/10/2018 06:27:03 (d1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|