비밀번호 보호

최근 웹사이트에 계정을 만들면서 비밀번호 관리자로 무작위 비밀번호를 생성했다. 제약 조건 중 하나는 비밀번호에 본인의 이름이나 성이 포함되지 않아야 한다는 것이었다. 여기서 '포함된다'는 말은 이름이나 성과 같은 문자열이 비밀번호의 연속된 부분 문자열로 들어 있다는 뜻이다. 처음 만든 비밀번호는 이 조건을 만족하지 못했다. 이런 일이 얼마나 자주 일어날 수 있는지 알고 싶다.

예를 들어 이름이 ali라면 california에는 이름이 부분 문자열로 들어 있지만 applied에는 없다. applied에는 ali가 부분 수열로는 나타나지만 연속된 부분 문자열은 아니기 때문이다.

이 조건은 포괄적 or이다. 이름을 포함하거나, 성을 포함하거나, 둘 다 포함하면 무효이다.

무작위로 생성된 비밀번호 중 이름 또는 성을 연속된 부분 문자열로 포함하는 비밀번호의 개수를 구하라. 비밀번호는 소문자 알파벳으로만 이루어진다.

첫째 줄에 무작위로 생성되는 비밀번호의 길이 $n$ ($1 \le n \le 10^7$)이 주어진다. 둘째 줄에 확인할 이름이 소문자 알파벳 $x$자로 주어진다 ($1 \le x \le 128$). 셋째 줄에 확인할 성이 소문자 알파벳 $y$자로 주어진다 ($1 \le y \le 128$).

무효인 비밀번호의 개수, 즉 이름이나 성을 포함하는 비밀번호의 개수를 출력한다. 답이 매우 클 수 있으므로 1,000,000,007로 나눈 나머지 중 가장 작은 음이 아닌 값을 출력한다.