Саймонд $x$ анхны тоо ба сөрөг биш бүхэл тоонууд $a_1$, $a_2$, $a_3$, ... $a_n$ өгөгджээ.

Тэр цаасан гэж тоо бичээд нэгтгэн нэг энгийн бутархай болгоход $t$ тоо нь $x^{a_1 + a_2 + ... + a_n}$ тоотой тэнцүү байлаа.

Саймон энэ бутархайг хурааж бичихийг хүссэн тул түүнд $s$, $t$ хоёр тооны хамгийн их ерөнхий хуваагчийг олж өгнө үү. ХИЕХ нь маш их тоо гарах боломжтой тул $1000000007$-д ($10^9 + 7$) хуваасан үлдэгдлийг хэвлээрэй.

Оролт

Эхний мөрөнд хоёр эерэг бүхэл тоо $n$, $x$ буюу байна. ($1 ≤ n ≤ 10^5$, $2 ≤ x ≤ 10^9$)

Хоёр дахь мөрөнд хоосон зайгаар тусгаарлагдсан $n$ ширхэг $a_1$, $a_2$, ... $a_n$ тоонууд байрлана. ($0 ≤ a_1 ≤ a_2 ≤ ... ≤ a_n ≤ 10^9$).

Гаралт

Хариу болох ганц тоог $1000000007$-д хуваасан үлдэгдэл.

In the first sample . Thus, the answer to the problem is $8$.

In the second sample, . The answer to the problem is $27$, as $351 = 1327$, $729 = 2727$.

In the third sample the answer to the problem is $1073741824 mod 1000000007 = 73741817$.

In the fourth sample . Thus, the answer to the problem is $1$.