{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e\r\n Palindrome really has many many properties which fascinated us a lot and arouse many interests.\u003cbr/\u003eDo you remember that last summer, the problem about longest palindrome in the inteval?\u003cbr/\u003eToo easy? Maybe you are tired of solving problem about palindrome on one string.\u003cbr/\u003eHere is your another challenge.\u003cbr/\u003eThere are two strings, A and B, and an integer d.\u003cbr/\u003eAnd you are to count the number of triples (i,j,k). that satisfies\u003cbr/\u003e{A.substr(i,k)\u003d\u003dB.substr(j,k), 1\u003c\u003di\u003c\u003dstrlen(A), 1\u003c\u003dj\u003c\u003dstrlen(B), A.substr(i,k) is a palindrome, k is the length of the substring, k\u003e\u003dd}\u003cbr/\u003eA substring of a string T is defined as:\u003cbr/\u003eT.substr(i, k)\u003dTiTi+1...Ti+k-1, 1\u003c\u003di\u003c\u003di+k-1\u003c\u003d|T|. \u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003e\r\n 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.\u003cbr/\u003e1 \u003c\u003d strlen(A), strlen(B) \u003c\u003d 50000\u003cbr/\u003e1 \u003c\u003d d \u003c\u003d min{strlen(A), strlen(B)}\u003cbr/\u003eCharacters of A and B are all lowercase letters. \u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003e\r\n For each case, output an integer indicates the number of the triples (i,j,k). \u003c/p\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cp\u003e\r\n 1\u003cbr/\u003eaba\u003cbr/\u003eaba\u003cbr/\u003e1\u003cbr/\u003eicpc\u003cbr/\u003ecicpc\u003cbr/\u003e2\u003cbr/\u003emyon\u003cbr/\u003eusagi \u003c/p\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cp\u003e\r\n 6\u003cbr/\u003e9\u003cbr/\u003e0 \u003c/p\u003e"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cp\u003e\r\n In the first sample , the 6 triples are\u003cbr/\u003e1,1,1\u003cbr/\u003e1,3,1\u003cbr/\u003e2,2,1\u003cbr/\u003e3,1,1\u003cbr/\u003e3,3,1\u003cbr/\u003e1,1,3\u003cbr/\u003erespectively. \u003c/p\u003e"}}]}