+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- اگر به رفتار استف‌های کدکاپ ۳ در طول مسابقه دقت کرده‌باشید، درمی‌یابید که *همه استفا عاشق مصطفی هستند*. در کدکاپ ۳ به هر کس ژتونی برای نهار داده شده که روی آن، رشته‌ای از حروف کوچک انگلیسی نوشته شده‌است. محمود که یکی از استف‌های زحمت‌کش مسابقات است عقیده دارد از بین همه استف‌های عاشق مصطفی، مصطفی خودش عاشق استفی است که رشته نوشته شده روی ژتونش بیشترین درجه تطابق و طول تطابق با رشته خودش را داشته باشد. از این رو او می‌خواهد درجه تطابق و طول تطابق رشته‌ خودش را با رشته مصطفی حساب کند. درجه تطابق و طول تطابق دو رشته به شکل زیر به دست می‌آید: رشته مصطفی را با $s$ و رشته محمود را با $t$ نشان می‌دهیم، طول هر دوی این رشته‌ها برابر $n$ است. فرض کنید یک گراف دو بخشی با $2n$ رأس داریم که رأس‌های بخش اول متناظر با کاراکترهای رشته‌ی $s$ و رأس‌های بخش دوم متناظر با کاراکترهای رشته‌ی $t$ است. به ازای هر دو اندیس $i$ و $j$ ($1 \le i, j \le n$) که کاراکتر $i$-ام از رشته‌ی $s$ و کاراکتر $j$-ام از رشته‌ی $t$ با یک‌دیگر برابر باشد یک یال بین رأس‌های متناظر این دو کاراکتر در گراف می‌گذاریم. طول تطابق رشته‌های $s$ و $t$ را برابر تعداد یال‌های **بزرگ‌ترین** تطابق در این گراف، و درجه تطابق رشته‌های $s$ و $t$ را برابر تعداد بزرگ‌ترین تطابق‌های این گراف می‌نامیم. یک تطابق در گراف یک زیرمجموعه از یال‌های آن گراف است که هیچ دو یالی از آن در رأسی مشترک نیستند. دو تطابق را متفاوت فرض می‌کنیم اگر مجموعه‌ی یال‌های آن‌ها متفاوت باشد. حال محمود با دادن رشته مصطفی و رشته خودش به شما، از شما می‌خواهد که طول تطابق و باقی‌مانده درجه تطابق رشته خودش با رشته مصطفی به $10^9 + 7$ را برای او بدست آورید. # ورودی در خط اول $s$، که رشته مصطفی است، و در خط دوم رشته $t$، که رشته محمود است، به شما داده می‌شود. دقت کنید که هر دو رشته‌ فقط از حروف کوچک انگلیسی تشکیل شده است. $$ 1 \le |s| , |t| \le 200\ 000$$ # خروجی در یک خط دو عدد جدا شده با فاصله از هم چاپ کنید که عدد اول طول تطابق دو رشته و عدد دوم باقی‌مانده درجه تطابق دو رشته به $10^9 + 7$ است. # مثال ## ورودی نمونه ۱ ``` salam szszs ``` ## خروجی نمونه ۱ ``` 1 3 ``` توضیح: در نمونه اول طول تطابق ۱ بوده (متناظر با رشته‌ `s`) و تعداد زیر دنباله‌های رشته محمود که با رشته مصطفی مطابق هستند و طولشان نیز یک می‌باشد برابر ۳ است. ## ورودی نمونه ۲ ``` mostafa estafah ``` ## خروجی نمونه ۲ ``` 5 2 ``` ## ورودی نمونه ۳ ``` ab ba ``` ## خروجی نمونه ۳ ``` 2 1 ```

حل سؤال در بانک سؤالات