{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"Palindrome really has many many properties which fascinated us a lot and arouse many interests.\n\nDo you remember that last summer, the problem about longest palindrome in the inteval?\n\nToo easy? Maybe you are tired of solving problem about palindrome on one string.\n\nHere is your another challenge.\n\nThere are two strings, $A$ and $B$, and an integer $d$.\n\nAnd you are to count the number of triples $(i,j,k)$. that satisfies\n$A.substr(i,k)\u003dB.substr(j,k)$, $1\\leq i\\leq strlen(A)$, $1\\leq j\\leq strlen(B)$, $A.substr(i,k)$ is a palindrome, $k$ is the length of the substring, $k\\geq d$\n\nA substring of a string $T$ is defined as:\n\n$T.substr(i, k)\u003dT_iT_{i+1}\\cdots T_{i+k-1}$, $1\\leq i\\leq i+k-1\\leq |T|$."}},{"title":"Input","value":{"format":"MD","content":"The input file contains several cases, end by `EOF`. For each cases, the first line contains one integer $d$, followed by two lines containing strings $A$ and $B$, respectively.\n\n$1 \\leq strlen(A), strlen(B) \\leq 50000$\n\n$1 \\leq d \\leq min\\{strlen(A), strlen(B)\\}$\n\nCharacters of $A$ and $B$ are all lowercase letters."}},{"title":"Output","value":{"format":"MD","content":"For each case, output an integer indicates the number of the triples $(i,j,k)$."}},{"title":"Sample 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1\naba\naba\n1\nicpc\ncicpc\n2\nmyon\nusagi\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e6\n9\n0\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"MD","content":"In the first sample , the $6$ triples are\n\n$1,1,1$\n\n$1,3,1$\n\n$2,2,1$\n\n$3,1,1$\n\n$3,3,1$\n\n$1,1,3$\n\nrespectively."}}]}