Counting Problem

See the 2 X 2 board above. AekdyCoin gets a N X N chessboard recently. But he think the color of the chessman is too dull (Only White and Black!).So AekdyCoin buys different kind of chessmen with different color, say blue, pink, yellow …Now AekdyCoin buys K kind of chessmen with different color, and the number of each kind is exactly Ai.


Now AekdyCoin begins to play with these chessmen. He wants to put all the chessmen he bought on the board, and of course every grid could only contain one single chessman.The Figure 2 shows a valid situation ,in this figure, AekdyCoin bought two kind of chessmen and the number of each is one.

As we know, AekdyCoin is very clever. So he think about this question:What is the number of ways he could put all chessmen he bought on the N X N board?

After a several seconds , AekdyCoin gets a perfect idea about how to solve this problem. What about you?

Two situation are regard the same in Figure 3, but the different in Figure 4.

But the ways that you can get by flip or circumrotate is not regard as the same!

The input consists of several test cases, but no more than 20.

There are two integers N, M in the first line of each case indicate the size of the board and M. You should output the remainder of answer after divided by M. (1<=N <=5000, 1<=M<=2*10^9)

The next line contain only one integer K indicates the kind of the chessmen AekdyCoin bought. (1<=k<=100)

Then the next line has exactly K integer where the i-th integer Ai indicate the number of the i-th kind of chessmen AekdyCoin bought.(1<=Ai<=5000)

Output a single line indicates the reaminder of answer after divided by M.

2 100
1
1
2 100
1
2

4
6

2009 Multi-University Training Contest 12 - Host by FZU