Filialimiz talabasi Murodjon tub sonlarni topishda turli xil algoritmlar o`rgandi. U endi juda katta tub sonlarni ham tezda topa oladi. Endi u o`z bilimiga ishongan holda do`sti Qudrat uchun topshiriq tayorlashga kirishdi va uzoq hisob – kitoblardan so`ng topshiriqni tayorladi. U Qudratga qiymati juda katta bo`lgan p tub son aytadi. Qudrat esa shunday k son aytishi kerakki quyidagi ifodadan butun musbat son chiqishi kerak.

Murod shunga ishonadiki bu ifodani yagona qiymat qanoatlantiradi. Javob yetarlicha katta bo`lishi mumkin. Shuning uchun javobni 1e9+7 ga bo`lgandagi qoldiqi so`raladi.

Qudratga ifodani qiymatini topishda yordam bering

Kiruvchi ma`luotlar

 p – tub son. (3 <= p <= 10¹⁰⁰⁰)

Chiquvchi ma`lumotlar:

Ifodani qanoatlantiruvchi yagona k sonini 1e9 + 7 ga bo`lgandagi qoldig`ini chiqaring.