Таньд $n$ ширхэг давхцаагүй бүхэл $a_{1}, a_{2}, ..., a_{n}$ тоонууд өгөгдөнө. Та эдгээрээс хамгийн ихдээ $k$-г устгаж болно. Хамгийн бага модуль $m$ $(m > 0)$-ийг олно. Ингэснээр үлдсэн бүхэл хос тоо бүр $(a_{i}, a_{j})$ нь дараах нөхцөлыг дагана. Үүнд:

.

Оролт

Эхний мөрөнд бүхэл $n$ ба $k$ ($1  ≤ n  ≤ 5000, 0 ≤ k ≤ 4$) тоонууд агуулагдана. Мөн дээр дурьдсан нөхцөлийг дагана.

Хоёр дахь мөрөнд $n$ ширхэг давхцаагүй бүхэл $a_{1}, a_{2}, ..., a_{n}$ $(0 ≤ a_{i} ≤ 10^{6})$ тоонууд агуулагдана.

Гаралт

Эерэг бүхэл нэг тоо хэвлэнэ. Уг тоо нь хамгийн бага модуль $m$ юм.