Necklaces

SwarOSKI necklaces are beautifully designed. Each necklace has N beads, and each bead has a color. If you unhook the necklace, you will get one straight necklace string of N beads. The necklace string can be partitioned into G partitions such that each partition consists of only beads of the same color, and adjacent partitions have different colors. Each partition contains either K-1, K, or K+1 beads, and at least 1 beads. Moreover, if we observe carefully, the colors among the partitions follow some ordering, and they may repeat. Finally, there are an equal number of partitions with the same color.

For example, let there be C = 2 colors and the ordering be: A B.

Given N, K, and C, determine how many valid SwarOSKI necklace configurations can be formed.

Input

Input begins with 3 integers: N K C (1 ≤ N ≤ 1,000; 1 ≤ K ≤ 20; 2 ≤ C ≤ 10) denoting the number of beads of the necklace, K as in the problem statement, and the number of colors, respectively. The next line contains C integers: Ai (1 ≤ Ai ≤ 100) denoting the beads' color in order. You may safely assume that all colors are different.

Output

Output in a line an integer representing the output for the given input in scientific notation, i.e.

A.BCD x 10^E

where A ∈ {0-9}; B,C,D ∈ {0-9}; E ≥ 0; A,B,C,D,E are integers. If A = 0, then B = C = D = E = 0. The output should be rounded to the nearest integer.

Examples

inputExample #1
10 3 2
2 5
output
1.000 x 10^1
explanation
There are 10 possibilities:
2 2 5 5 2 2 2 2 5 5
2 2 5 5 2 2 2 5 5 5
2 2 5 5 2 2 5 5 5 5
2 2 2 5 5 2 2 2 5 5
2 2 2 5 5 2 2 5 5 5
2 2 5 5 5 2 2 2 5 5
2 2 5 5 5 2 2 5 5 5
2 2 2 2 5 5 2 2 5 5
2 2 2 5 5 5 2 2 5 5
2 2 5 5 5 5 2 2 5 5
Each of those is a SwarOSKI necklace with N = 10, K = 3, and C = 2 with the ordering be (2, 5).


End of Problem