+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۱۰۰ مگابایت ---------- در شهر کانتیننتال، هتلی وجود دارد که به ریاست پیکلوویچ، همه خلافکار‌ها و آدم‌های خطرناک در آن ساکن هستند به طوری که اگر کسی بخواهد به آن وارد شود، اسم خود را به نگهبان داده و نگهبان با بررسی فراوان در لیست خود، به او اجازه ورود می‌دهد. هیچ‌کس جرئت نزدیک شدن به این هتل را نداشت تا اینکه یک گروه به سرکردگی الکس تصمیم گرفتند به این هتل نفوذ کنند. افراد الکس تصمیم گرفتند که اسم‌های خود را رمز کنند به صورتی که بین آن حروف اضافه‌تری قرار بدهند اما از شانس بد الکس، خلافکار‌ها این موضوع را متوجه شده‌اند و در تلاش‌اند که اسم رمزنگاری نشده این گروه را پیدا کنند. آن‌ها این کار را به این صورت در نظر می‌گیرند که از اسم رمزگذاری شده، زیررشته‌هایی به اندازه اسم واقعی می‌سازند و ارزش آن را محاسبه می‌کنند. ارزش هر زیر رشته برابر است با مجموع تکرار حروف آن. هرکدام که ارزش بالاتری داشت به احتمال بیشتری اسم واقعی است و آن‌ها به دنبال آن هستند. **توجه کنید که به طرز عجیبی اسم واقعی افراد الکس حروف تکراری ندارد!** برنامه‌ای بنویسید که به خلافکارها کمک کند تا اسم نفوذی را پیدا کنند =))))) # ورودی ورودی شامل دو خط است که در خط اول اسم رمزنگاری شده به حروف کوچک انگلیسی (s) و در خط دوم طول اسم واقعی (n) می آید. $$1 \le s.length \le 2 * 10^5$$ $$1 \le n \le s.length $$ # خروجی خروجی برنامه شامل یک خط است که در آن تعداد زیررشته‌ها با بیشترین ارزش را برمی‌گرداند. **از آنجایی که جواب ممکن است خیلی بزرگ باشد باقی‌مانده آن را به $10^9 + 7$ محاسبه کنید.** # مثال ## ورودی نمونه ۱ ``` seas 2 ``` ## خروجی نمونه ۱ ``` 4 ``` در این نمونه ارزش هر زیر رشته به صورت زیر محاسبه می‌شود: + f('s') = 2, f('e') = 1, f('a') = 1 + **se**as => f('s') + f('e') = 3 + **s**e**a**s => f('s') + f('a') = 3 + s**ea**s=> f('e') + f('a') = 2 + s**e**a**s** => f('e') + f('s') = 3 + se**as** => f('a') + f('s') = 3 که در این نمونه بزرگترین ارزش برابر با ۳ است و تعداد زیررشته‌ها با این اندازه ۴ می‌باشد. ## ورودی نمونه ۲ ``` leech 4 ``` ## خروجی نمونه ۲ ``` 2 ``` در این نمونه ارزش هر زیر رشته به صورت زیر محاسبه می‌شود: + f('l') = 1, f('e') = 2, f('c') = 1, f('h') = 1 + **le**e**ch** => f('l') + f('e') + f('c') + f('h') = 5 + **l**e**ech** => f('l') + f('e') + f('c') + f('h') = 5 که در این نمونه بزرگترین ارزش برابر با ۵ است و تعداد زیررشته‌ها با این اندازه ۲ می‌باشد.