Chia hai tập p mũ k

Cho $n$ số có dạng $p^{k_1},p^{k_2},\dots ,p^{k_n}$ (cùng cơ số $p$). Bạn cần chia $n$ số này thành hai tập hợp rời nhau (mỗi số thuộc đúng một tập, và hợp của hai tập bằng toàn bộ dãy) sao cho chênh lệch tuyệt đối giữa tổng hai tập là nhỏ nhất.

Gọi giá trị chênh lệch nhỏ nhất là $D$. Hãy in ra $Dmod({10}^9+7)$.

Lưu ý. Bạn phải tối thiểu hoá $D$ trước, rồi mới lấy phần dư. Ví dụ nếu $D=2$ nhưng có một cách chia khác cho chênh lệch ${10}^9+8$ thì đáp án vẫn là $2$, không phải $1$.

Dữ liệu vào

Dòng đầu chứa số nguyên $t$ — số bộ test.

Với mỗi bộ test:

• Dòng thứ nhất chứa hai số nguyên $n$ và $p$.
• Dòng thứ hai chứa $n$ số nguyên $k_1,k_2,\dots ,k_n$.

Dữ liệu ra

Với mỗi bộ test, in ra một số nguyên trên một dòng — chênh lệch nhỏ nhất modulo ${10}^9+7$.

Ràng buộc

• $1\le t\le {10}^5$
• $1\le n,p\le {10}^6$
• $0\le k_i\le {10}^6$
• Tổng $n$ trên tất cả các bộ test không vượt quá ${10}^6$.

Ví dụ