Codeforces Round #804 (Div. 2)
5 өдрийн дараа |
C. Анхны тоо
хугацааны хязгаарлалт 1 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Саймонд $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$-д хуваасан үлдэгдэл.
Орчуулсан: gmunkhbaatarmn
Жишээ тэстүүд
Оролт
2 2 2 2
Гаралт
8
Оролт
3 3 1 2 3
Гаралт
27
Оролт
2 2 29 29
Гаралт
73741817
Оролт
4 5 0 0 0 0
Гаралт
1
Тэмдэглэл
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$.