Програмчлалын олимпиадын бодлогын архив

Энтүүд бол Элфүүдтэй адил үхэшгүй мөнх амьтад юм. Тэд анх ярьж чаддаггүй байгаад Элфүүдээр хэл заалгасан байна. Элфүүд тэдэнд хэлээ заахын тулд дараах аргыг боловсруулжээ. Хамгийн анх хэл сурсан Энт "тийм", "үгүй" гэсэн хоёр үг л сурсан. Хэл сурсан Энт хэл мэдэхгүй хөгшин, залуу хоёр Энтүүдийг сонгон авч өөрийн мэддэг бүх үгээ заана. Үүний дараа тэр хоёр Энтэд Элфүүд үргэлжлүүлэн хэл заадаг. Элфүүдээс хэл сурсан Энт бүр хэл мэдэхгүй хөгшин, залуу хоёр Энтийг сонгон авч өөрийн мэддэг бүх үгээ заагаад Элфүүдэд дамжуулан өгөх гэх мэтчилэн үргэлжилнэ. Залуу Ентүүд өөрсдийн анхны багш Энтээсээ сурсан үгийн тоогоор шинэ үгийг Элфүүдээс сурна. Харин хөгшин Энтүүд Элфүүдээс зөвхөн нэг үгийг л нэмж сурдаг. Элфүүдээр хэл заалгасан Энт үлдсэн амьдралдаа дахиж нэг ч үг сурч чадахгүй. Яг өгөгдсөн тооны үг мэддэг Энт хэд байх вэ? Энэ тоо нь маш их байж болох учраас хариуг P модулиар гаргана.

Input

Нэг мөрөнд, зайгаар тусгаарлагдан K ба P эерэг бүхэл тоонууд өгөгдөнө (K ≤ 10⁷; P ≤ 10⁹)

Output

Яг K ширхэг үг мэддэг Энтүүдийн тоог P тоонд хуваасны үлдэгдлийг гаргана

Example

Input:
4 10

Output:
2