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

---

دزد با مهارت، بالاخره با عمو روبرو شد. عمو که بسیار پول پرست است، پس از دیدن کیسه‌های تیله و تعداد تیله‌های داخل آن، متوجه شد که دزد با مهارت خوبی عمل کرده و دست عمو را بسته. پس عمو تصمیم گرفت که روند خرید تیله از دزد را تغییر دهد.

در ادامه‌ی سوال قبل (تیله‌های توی کیسه) می‌دانیم که $n$ کیسه از تیله روی میز مقابل عمو و دزد روی یک ردیف چیده شده‌ است. این کیسه‌های تیله را به ترتیب با اعداد طبیعی ۱ تا $n$ شماره گذاری کرده‌ایم، کیسه‌ی $i$ام در ردیف، شماره‌ی $i$ دارد. عمو و دزد متوجه شدند که روی هریک از این $n$ کیسه، یک حرف کوچک انگلیسی نوشته شده که هریک صاحب قبلی آن کیسه را مشخص می‌کند. عمو می‌خواهد تعدادی کیسه‌ی پشت سر هم از ردیف را انتخاب کرده و خریداری کند؛ بصورتی که همه‌ی آن کیسه‌ها مال یک صاحب قبلی باشند. (یعنی حرف نوشته‌شده روی همه‌ی آن‌ها یکسان باشد) این کیسه‌هایی که عمو برای خرید انتخاب می‌کند، باید بازه‌ای غیرقابل افزایش باشد؛ یعنی نتوان بازه‌ی پشت سر هم بزرگتری از کیسه‌ها برای خرید انتخاب کرد که شامل بازه‌ی خریداری شده باشد.

برای مثال اگر ۵ کیسه روی میز باشد و دنباله‌ی "صاحب‌ها"ی آن‌ها برابر با aabcd باشد، عمو ۴ حالت برای انتخاب بازه‌ی برای خرید دارد: دو کیسه‌ی اول، کیسه‌ی سوم، کیسه‌ی چهارم و یا کیسه‌ی پنجم. اگر ۳ کیسه روی میز باشد و دنباله‌ی "صاحب‌ها" برابر "aba" باشد نیز عمو ۳ حالت برای انتخاب بازه‌ برای خرید دارد: همه‌ی بازه‌های شامل تنها یک کیسه.

عمو دید که حداکثر ۱۰۰ انتخاب برای بازه‌‌ی خرید دارد؛ پس بعنوان یک فرد پول‌پرست شروع به چانه‌زنی کرد که "الان توی دزد، اومدی یجوری این کیسه‌ها رو چیدی که من مجبور شم بین این تعداد گزینه انتخاب کنم! تو منو محدود کردی، و انتظار پول داری؟!"

دزد پس از شنیدن این گفته‌ی عمو، هول شد و شروع کرد به استدلال برای اینکه این کار از قصد نبوده! دزد با جابجا کردن کیسه‌ها بطوری که تعداد انتخاب‌های عمو تغییری نکند، تلاش می‌کرد که عمو را قانع کند.

برای مثال اگر دنباله‌ی "صاحب‌ها" برابر aabcd باشد، دزد شروع به توضیح میکند که "اگر دقت کنید اگر من کیسه‌ها را طوری می‌چیدم که دنباله‌ی aacbd درست میشد هنوز هم شما ۴ انتخاب داشتید عموی بزرگ. aadbc هم! baacd هم!" و ...

عمو دید که دزد بیخیال ماجرا نمی‌شود و تا همه‌ی حالت‌ها برای دنباله "صاحب‌ها" را نساخته، به تغییر چینش کیسه‌ها ادامه می‌دهد. پس چون وقت طلاست و عمو پول پرست است، از شما می‌خواهد که با ورودی گرفتن دنباله‌ی "صاحب‌ها"، بگویید با عوض کردن ترتیب کیسه‌ها چند دنباله‌ی "صاحب‌ها" میتوان بوجود آورد که انتخاب‌های عمو در آن‌ها برابر دنباله‌ی اولیه باشد.

چون این عدد ممکن است بسیار بزرگ باشد و در نتیجه عمو نتواند بخواندش، او از شما خواسته که باقی‌مانده‌ی جواب را بر 1000003 (که تعداد کلید گنج‌های عمو است) اعلام کنید.

ورودی

در تنها سطر ورودی یک رشته از حروف کوچک انگلیسی آمده‌است که نمایانگر دنباله‌ی "صاحب‌ها"ی کیسه‌های روی میز است.

طول این دنباله حداکثر $500\ 000$ است.

تضمین می‌شود که عمو حداکثر ۱۰۰ انتخاب برای بازه‌ی خرید دارد.

خروجی

در تنها سطر خروجی باقی‌مانده‌ی جواب را بر 1000003 اعلام چاپ کنید.

مثال

ورودی نمونه ۱

aabcd

خروجی نمونه ۱

24

ورودی نمونه ۲

bzzooeerep

خروجی نمونه ۲

7200

ورودی نمونه ۳

aba

خروجی نمونه ۳

1