АСМ-1 гаригийн судалгааны багийнхан Мулзанчуудыг (энэ нь толгой дээрээ антеннгүй амьтдыг хэлдэг гэнэ) судлахаар дэлхий дээр иржээ.

Эдгээр зоригт аялагчдын нисдэг таваг нь $3$ хэсгээс тогтдог гэнэ. Эдгээр нь гинжин холбоотой буюу $1$-р хэсэг $2$-той, $2$-р хэсэг $1$, $3$-тай, $3$-р хэсэг $2$-той холбогдсон. Хэсгүүдийн хооронд зөвхөн холбоосоор дамжин явж болдог.

Нисдэг тавагт $1$-с $n$ цолтой нийт $n$ харь гаригийнхан байгаа. Уг хөлгийн дүрмэнд $a$, $b$ (хоорондоо холбогдсон) хэсгийн хооронд зөвхөн хамгийн том цолтой хүн л шилжиж болно гэж байдаг ажээ. Нэг шилжилт яг $1$ минут явагддаг бөгөөд нэг шилжилт явагдаж байх зуур өөр шилжилж хийж болохгүй.

Хэрвээ $A$ тоо нь $B$-с их бол $A$ цолтой хүн нь $B$-с илүү том цолтой гэж үзнэ.

Яг одоо хөлгийн бүх гишүүд $3$-р хэсэгт байгаа. Одоо тэд бүгд $1$-р хэсэгт очих хэрэгтэй болжээ. Хөлгийн CFR-140 нэртэй гишүүн шилжүүлэлтэнд зарцуулах хамгийн бага хугацааг (минутаар) олохыг хүсчээ.

CFR-140-д тусалж бүх гишүүдийг $3$-р хэсгээс $1$-р хэсэгрүү шилжүүлэхэд зарцуулах хамгийн бага хугацааг олно уу. Хариу маш том байж болох тул $m$-д хуваасан үлдэгдлийг хэвлээрэй.

Оролт

Нэг мөрөнд гишүүдийн тоо $n$, модуль авах тоо $m$ ($1 ≤ n, m ≤ 10^9$) өгөгдөнө.

Гаралт

Бодлогын хариуг $m$-д хуваахад гарах үлдэгдлийг хэвлэ.

In the first sample the only crew member moves from segment 3 to segment 2, and then from segment 2 to segment 1 without any problems. Thus, the whole moving will take two minutes.

To briefly describe the movements in the second sample we will use value , which would correspond to an alien with rank $i$ moving from the segment in which it is at the moment, to the segment number $j$. Using these values, we will describe the movements between the segments in the second sample: , , , , , , , , , , , , , , , , , , , , , , , , , ; In total: the aliens need 26 moves. The remainder after dividing $26$ by $8$ equals $2$, so the answer to this test is $2$.