• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

---

رادزینکا دوبرامیل ویچشسلافوویچ (Rodzyanko Dobromil Vyacheslavovich) که یک فرد تنبل طماع است، باید درس تربیت بدنی را پاس کند.

رادزینکا در دانشگاه تربیت دبیر زیولکوفسکی ایالت کالوگا (Tziolkovsky Kaluga State Pedagogical University) تحصیل میکند. همانطور که می‌دانید آزمون درس تربیت بدنی در این دانشگاه بسیار سخت گیرانه گرفته می‌شود، بصورتی که همه‌ی دانشجوها مقدار زیادی تمرین می‌کنند تا بتوانند از آن آزمون سخت گذر کنند.

رادزینکا بدلیل تنبلی‌اش، قاعدتاً نمی‌تواند از پس این آزمون برآید. پس تلاش‌می‌کند که هرگونه حقه‌ای به کار گیرد تا بدون تلاش این درس یک واحدی را پاس کند. آزمون نهایی تربیت بدنی در این ترم، دوی استقامت است. دانشجویان باید $a$ متر دور زمین دو‌ و میدانی دانشگاه بدوند. این زمین $n$ متر طول دارد و شامل یک خط شروع است. کنار زمین $n$ خط کشیده شده‌است که هر دو تای آن ۱ متر با هم فاصله دارند و کنار هر خط فاصله‌ی نقطه‌ی شروع تا آن خط را نوشته است. بعنوان مثال، در کنار نقطه‌ی شروع، یک خط است که در کنار آن ۰ نوشته شده است. یک متر پیش از نقطه‌ی شروع نیز یک خط هست که در کنار آن مقدار $n - 1$ نوشته شده است. رادزینکا با کمی دقت متوجه شد که می‌تواند به جای $a$ متر، به مقدار باقی‌مانده‌ی $a$ پس از تقسیم بر $n$ متر ($a\ mod\ n$ متر) بدود و به جایی برسد که در نهایت باید آنجا متوقف شود!

استاد تربیت بدنی این ترم، کاستاماروف لفانتونویچ (Kostomarov Lev Antonovich)، بسیار دقیق و سخت‌گیر است و برای تقلب جریمه‌های سنگینی می‌گذارد. اگر فردی که باید $x$ متر بدود به هر دلیلی این کار را انجام ندهد، باید بار دیگر امتحان بدهد و این‌بار $x^x$ متر بدود!

رادزینکا هنگام دادن آزمون، با خیال راحت $a\ mod\ n$ متر می‌دود تا به کنار خط هدفش برسد. اما کاستاماروف دقیق‌تر از این حرف‌ها است و متوجه تقلب او می‌شود. پس با داد و بیداد، رادزینکا را به نقطه‌ی شروع می‌فرستد و به او می‌گوید که این بار باید $a^a$ متر بدود. رادزینکای سرخورده، به نقطه‌ی شروع می‌رود و دوباره دو را شروع می‌کند، و به کنار خط $a^a\ mod\ n$ می‌رود؛ اما باز هم کاستاماروف مچش را می‌گیرد و با چک و لگد، او را دوباره به نقطه ی شروع می‌برد که دوی ماراتن $(a^a)^{a^a}$ متری‌اش را آغاز کند.

اکنون رادزینکا گیج شده و نمی‌تواند محاسبه کند که کجا باید توقف کند! شما مقدار $(a^a)^{a^a} \ mod \ n$ را به او بگویید تا یک بار دیگر برای فریب کاستاماروف تلاش کند.

ورودی

در تنها سطر ورودی دو عدد $a$ و $n$ آمده است که با یک فاصله از هم جدا شده‌اند و به ترتیب نمایانگر مقدار اولیه‌ی دویدن در امتحان و طول زمین دو و میدانی دانشگاه تربیت دبیر زیولکوفسکی ایالت کالوگا است.

$$1 \le a \le 1000$$ $$2 \le n \le 1000$$

خروجی

در تنها سطر خروجی یک عدد چاپ کنید که نمایانگر خطی است که رادزینکا پس از ۲ بار تقلب، در انتهای امتحان باید کنارش بایستد.

مثال

ورودی نمونه ۱

2 1000

خروجی نمونه ۱

256

ورودی نمونه ۲

2 5

خروجی نمونه ۲

1