서버가 모두 마비되고 나서야 이를 알아차린 NIA 서버 관리자는 급히 서버를 복구하였고, 승현이가 공격하면서 남긴 로그들을 이용해서 범인을 찾으려고 합니다.

그는 NIA 서버에 접속한 사람이 승현이밖에 없다는 사실을 어레짐작하고 있었으나, 이를 증명할 수는 없었습니다. 그래서 아래와 같은 자신이 만든 유사도 공식을 통해 승현이를 추궁해 승현이가 자신이 범인이라는 것을 자백하게 하려고 합니다.

NIA 서버 관리자는 아래와 같은 두 개의 문자열을 가지고 있습니다. 이 두 문자열은 모두 알파벳 대문자로만 이루어져 있습니다.

1. a_1..N : 승현이의 스마트폰 고유 식별 문자열입니다.
2. b_1..N : 승현이의 스마트폰이 NIA 서버 로그에 남겨 놓은 문자열입니다. 승현이의 스마트폰은 보안을 위해 NIA 서버 로그에 자신의 고유 식별 문자열을 그대로 남겨두지는 않습니다.

관리자가 만든 유사도 공식은 아래와 같습니다.

문자열 a, b와 이들의 길이 N이 주어질 때, 유사도 S를 구하는 프로그램을 작성하세요. 단 답이 커질 수 있으니 1,000,000,009 (10⁹ + 9)로 나눈 나머지를 출력합니다.

입력

• 첫째 줄에 문자열의 길이 N(1≤N≤100,000)이 주어집니다.
• 이후 2개 줄에 문자열 a_1..N와 b_1..N가 주어집니다.

출력

첫째 줄에 유사도 S를 1,000,000,009 (10⁹ + 9)로 나눈 나머지를 출력합니다.

입출력 예

입력

3
AAB
CAA

출력

9

출처:GENIUSainta.com