D. Модулын Арифметик

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Ямар ч ухаалаг сургуулийн хүүтэй таарч тохирдог Кэвин Сан Бовиниа мужийн их сургуульд (BGU) Иван тариаланчийн доор үнээний сэтгэл судлал, үнээний интеграл болон үнээний нууц бичээс тайлах хичээл үзэж байгаа ажээ.Математикийн Олимпиадын хичээл(MoO) дээрээ Кэвин нэгэн ойлгомжгүй функц-тай тэгшитгэлтэй тулгарсан бөгөөд таны тусламж түүнд хэрэг болжээ.Тогтвортой 2 бүхэл тоо $k$ болон сондгой анхны тоо $p$-ын хувьд,функц-тай тэгшитгэл нь дараах байдалтай байна

зарим функцийн хувьд байх юм.(Энэ тэгшитгэл нь $0$-ээс $p - 1$ завсар дахь ямар ч бүхэл тоо $x$-ын хувьд биелэх юм.)

Гэнэт $f$ нь олон янзын функц байж болохыг мэджээ.Тиймээс бодлогыг бодохын оронд,Кэвин таныг тэгшитгэлийг хангах ялгаатай $f$ функцийн тоог олохыг хүсжээ.Хариу нь маш том тоо гарч болох учраас та хариултаа $10^{9} + 7$ модулаар бодож гаргана уу.

Оролт

Ганц мөрөнд зайгаар тусгаарлагдсан 2 бүхэл тоо $p$ болон $k$ ($3 ≤ p ≤ 1 000 000$, $0 ≤ k ≤ p - 1$) өгөгдөнө.Мөн $p$ нь сондгой анхны тоо байна.

Гаралт

Ялгаатай $f$ функцийн тоог $10^{9} + 7$ модулаар бодсон ганц бүхэл тоог хэвлэнэ.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
3 2
Гаралт
3
Оролт
5 4
Гаралт
25

Тэмдэглэл

Эхний жишээнд, $p = 3$ ба $k = 2$ байна. Дараах функц-ууд нь нөхцөлийг хангана:

  1. $f(0) = 0$, $f(1) = 1$, $f(2) = 2$.
  2. $f(0) = 0$, $f(1) = 2$, $f(2) = 1$.
  3. $f(0) = f(1) = f(2) = 0$.
Сэтгэгдлүүдийг ачааллаж байна...