dinhhuubaonam123 chế tạo một cỗ máy tạo xâu. Máy dùng bảng chữ cái gồm \(A\) ký tự \(\{1, 2, \dots, A\}\) để tạo ra xâu độ dài chính xác \(n\). Tuy nhiên, do skill issue, máy không thể tạo bất kỳ xâu nào chứa xâu \(P\) (với \(|P| = m\)) như một xâu con liên tiếp.

Đếm số xâu hợp lệ mà máy có thể tạo, lấy phần dư với \(10^9 + 7\).

Input

• Dòng 1: ba số nguyên \(n\), \(A\), \(m\).

• Dòng 2: \(m\) số nguyên \(P_1, P_2, \dots, P_m\) (\(1 \leq P_i \leq A\)).

• \(1 \leq n \leq 10^{18}\)

• \(2 \leq A \leq 9\)
• \(1 \leq m \leq 6\)

Output

• Một số nguyên: đáp án modulo \(10^9 + 7\).

Example

3 2 2
1 2

4