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.

• AAABBBAAABBB is a SwarOSKI necklace of length N = 12, K = 3 (K = 2 or K = 4 is also a valid one), and 4 partitions; 2 partitions for each color.
• AABBAABBAABB is a SwarOSKI necklace of length N = 12, K = 2 (K = 1 or K = 3 is also a valid one), and 6 partitions; 3 partitions for each color.
• AAABBAAABBBABB is a SwarOSKI necklace of length N = 13, K = 2, and 6 partitions. Notice that each partition has either 1, 2, or 3 beads; 3 partitions for each color.
• AAAAABBBB is a SwarOSKI necklace of length N = 9, K = 5 (K = 4 is also a valid one), and 2 partitions; 1 partition for each color.
• BBAAABBBAA is NOT a SwarOSKI necklace as it does not follow the colors ordering (A B).
• AAABBBBAAAA is NOT a SwarOSKI necklace as there are an unequal number of partitions for each color (2 A-partitions, and 1 B-partition).
• ABBAAABBBBAAAAABBBBBB is NOT a SwarOSKI necklace as there is no satisfying K.

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

 input Example #1 10 3 22 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