{"code":"cses1112","name":"CSES - Required Substring | Xâu con bắt buộc","description":"Nhiệm vụ của bạn là tính toán số lượng xâu độ dài $n$ có một từ khóa độ dài $m$ được cho xuất hiện như xâu con của chúng. Tất cả các xâu bao gồm các kí tự `A`-`Z`.\r\n\r\n

Input

\r\n\r\n- Dòng đầu vào đầu tiên có một số nguyên $n$: độ dài của xâu đáp án. \r\n- Dòng thứ hai có từ khóa độ dài $m$.\r\n\r\n

Output

\r\n\r\n- In số lượng xâu chia lấy dư cho $10 ^ 9 + 7$.\r\n\r\n

Constraints

\r\n\r\n- $1 \\leq n \\leq 1000$\r\n- $1 \\leq m \\leq 100$\r\n\r\n

Example

\r\n!!! question \"Test 1\"\r\n ???+ \"Input\"\r\n 6\r\n ABCDB\r\n\r\n ??? success \"Output\"\r\n 52\r\n\r\n

Note

\r\n\r\nXâu đáp án sẽ có dạng `ABCDB`$x$ hoặc $x$`ABCDB` trong đó $x$ là bất kỳ ký tự nào giữa `A`-`Z`.","points":1900.0,"partial":true,"time_limit":1.0,"memory_limit":524288,"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}}