Một cây \(k\)-phân đầy đủ gồm \(h\) tầng là cây gồm \(\frac{k^{h} - 1}{k - 1}\) nút được sinh ra theo cách như sau:

• Tầng thứ nhất: chỉ có nút gốc, được đánh số là \(1\).
• Tầng thứ \(i\) \((1 < i \leq h)\): xét lần lượt các nút thuộc tầng \(i – 1\) theo thứ tự tăng dần, với mỗi nút \(u\) thuộc tầng \(i − 1\), tạo ra \(k\) con của \(u\) ở tầng \(i\), \(k\) nút con này được đánh số liên tiếp và tăng dần. Cách làm này đảm bảo nếu \(u\) và \(v\) cùng thuộc tầng \(i − 1\) và \(u \leq v\) thì các con của \(u\) sẽ được đánh số nhỏ hơn các con của \(v\).

Dưới đây là một ví dụ về cây tam phân \((k = 3)\) gồm \(4\) tầng \((h = 4)\):

Trong số \(\frac{k^{h} - 1}{k - 1}\) nút, có \(n\) nút đặc biệt là \(p_{1}, p_{2}, \ldots, p_{n}\). Chúng ta cần chọn ra một số ít nhất các cạnh, để \(n\) nút đặc biệt này được liên thông với nhau. Bạn hãy xác định số cạnh ít nhất cần chọn.

Input

• Dòng đầu tiên chứa số nguyên \(k, h\) và \(n\) \((2 \leq k \leq 10, 2 \leq h \leq 18, 2 \leq n \leq 500000)\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(p_{1}, p_{2}, \ldots, p_{n}\) là các nút đặc biệt. Dữ liệu đảm bảo \(p\) đôi một khác nhau.

Output

• Ghi ra duy nhất một số là số cạnh ít nhất cần chọn.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(2 \leq k, h \leq 5\).
• Subtask \(2\) (\(20\%\) số điểm): \(2 \leq k, h \leq 8, n = 2\).
• Subtask \(3\) (\(20\%\) số điểm): \(2 \leq k, h \leq 8, n = 3\).
• Subtask \(4\) (\(20\%\) số điểm): \(2 \leq n \leq 50000\).
• Subtask \(5\) (\(20\%\) số điểm): không có ràng buộc gì thêm.

Example

3 4 5
12 13 14 15 16

8