{"code":"sothosubstr","name":"Một vài ý nghĩ về chuỗi con","description":"* **Rùa 🐢** có một vài ý nghĩ về chuỗi con như sau:\r\n\r\nCho hai chuỗi ký tự $s$ và $t$. Gọi một chuỗi ký tự mới $ss$ bằng $K$ bản copy của chuỗi $s$ gắn liền vào bên phải hoặc bên trái của nhau. Hãy đếm số lần xuất hiện chuỗi $t$ trong chuỗi $ss$.\r\n\r\n- **Định nghĩa** của sự xuất hiện chuỗi:\r\n\r\nChuỗi $A$ xuất hiện trong chuỗi $B$ khi nếu xóa đi bên trái cùng và bên phải cùng xâu $B$ một số lượng ký tự (có thể là $0$) thì các ký tự còn lại ở giữa chính là xâu $A$.\r\n\r\n- **Ví dụ**: Chuỗi `efg` xuất hiện trong chuỗi `abcdefgh` vì có thể xóa `abc` bên trái và `h` bên phải để thu được `abc`.\r\n \r\n

Input

\r\n\r\n- Dòng đầu tiên chứa chuỗi không rỗng $s$. Độ dài không lớn hơn $10^5$.\r\n- Dòng thứ hai chứa chuỗi không rỗng $t$. Độ dài không lớn hơn $10^3$ và độ dài chuỗi $s$.\r\n- Dòng thứ ba chứa một số nguyên $K$. $(1 \\leq K \\leq 10^9)$\r\n\r\n

Output

\r\n\r\nIn ra một số nguyên, là số lần xuất hiện xâu $t$ trong xâu $ss$, được tạo thành bởi $K$ chuỗi $s$ ghép thành.\r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n abab\r\n ab\r\n 3\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 6\r\n ```\r\n \r\n ??? warning \"Note\"\r\n \r\n Chuỗi $ss$ là `abab`$ * 3$ $=$ `abababababab`, ở đây, chuỗi `ab` xuất hiện trong chuỗi $ss$ $6$ lần.\r\n\r\n!!! question \"Test 2\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n aaaa\r\n a\r\n 2\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 8\r\n ```","points":200.0,"partial":true,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}