+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- پارسا در شهری زیبا زندگی می‌کند و اصغر از شهر می خواهد دزدی کند. پانورامای شهر را می‌توان به صورت یک رشته \(s\) نمایش داد که هر کاراکتر نشان‌دهنده شکل ساختمان متناظر است. ساختمان‌های مختلف ممکن است شکل یکسانی داشته باشند و بنابراین در رشته با کاراکترهای یکسان نمایش داده می‌شوند. اصغر یک رشته \(p\) را به عنوان برنامه دزدی خود انتخاب کرده است. خوشبختانه این رشته \(p\) به دست پلیس افتاده است. حال آنها می‌خواهند تمام مجموعه ساختمان‌هایی که در خطر هستند را پیدا کنند، اما یک پیچیدگی در راه است. به دستور شهردار جدید، برخی از ساختمان‌ها در شهر باید تخریب شوند. آنها یکی پس از دیگری و به ترتیبی که در رشته \(s\) ظاهر می‌شوند، از چپ به راست، تخریب می‌شوند. این برنامه تخریب در شهر خوب شناخته شده است. دزدی می‌تواند در هر زمانی اتفاق بیفتد: قبل از تمام تخریب‌های برنامه‌ریزی شده، بعد از آنها، یا بین تخریب هر دو ساختمانی که یکی پس از دیگری در برنامه تخریب هستند. با این حال، هیچ تخریبی نمی‌تواند در طول دزدی اتفاق بیفتد. اصغر به طور دقیق طبق برنامه دزدی خود از چپ به راست دزدی می‌کند. او هیچ ساختمانی را به جز آنهایی که تخریب شده‌اند، نمی‌پراند. او فقط می‌تواند کل برنامه را اجرا کند. با این حال، ممکن است تعداد زیادی از مجموعه‌های ساختمان‌ها وجود داشته باشند که در خطر دزدیده شدن هستند. به طور رسمی، در نظر بگیرید رشته \(t\) که ما از \(s\) با حذف کاراکترهای متناظر با ساختمان‌های تخریب شده به دست می‌آوریم. توجه داشته باشید که رشته \(t\) در ابتدا برابر با \(s\) است اما پس از هر تخریب تغییر می‌کند. اصغر می‌تواند یک مجموعه از ساختمان‌ها را دزدیده اگر در یک لحظه از زمان، این مجموعه یک زیررشته از \(t\) را تشکیل دهد و این زیررشته برابر با رشته \(p\) باشد. وظیفه شما این است که دقیقا تعداد مجموعه‌هایی را که در خطر دزدیده شدن هستند، پیدا کنید. # ورودی خط اول ورودی شامل یک رشته غیرخالی \(s\) متشکل از حروف کوچک و بزرگ انگلیسی، ارقام، کاراکترهای `'`, `!`, `_`, `.` و `-` است که ساختمان‌های شهر را از چپ به راست نشان می‌دهد. طول این رشته از \(1,000,000\) تجاوز نمی‌کند. خط دوم ورودی شامل رشته \(p\) است که برنامه دزدی اصغر را نشان می‌دهد. طول این رشته نیز از \(1,000,000\) تجاوز نمی‌کند. خط سوم ورودی شامل یک عدد صحیح \(m (0 \leq m \leq |s|)\) است که طول برنامه تخریب شهردار است. خط بعدی شامل یک دنباله افزایشی از اعداد صحیح \(x_1, x_2, \ldots, x_m (1 \leq x_1 < \ldots < x_m \leq |s|)\) است که شاخص‌های ساختمان‌ها در ترتیبی است که باید تخریب شوند. # خروجی یک عدد صحیح که تعداد مجموعه‌های مختلف ساختمان‌ها که می‌توانند طبق برنامه اصغر دزدیده شوند. # مثال ## ورودی نمونه ۱ ``` aabbcc abc 3 2 4 5 ``` ## خروجی نمونه ۱ ``` 2 ``` توضیحات: پاسخ برای نمونه داده شده \(2\) است زیرا دنباله‌های ممکن از ساختمان‌ها که می‌توانند دزدیده شوند عبارتند از: \(135\) (پس از دو تخریب ساختمان) و \(136\) (پس از تمام سه تخریب ساختمان).