12866번 - 피노키오

인간의 염색체는 [‘A’, ‘C’, ‘G’, ‘T’] 네 가지 알파벳으로 대표되는 네 가지 염기로 이루어져 있다. 힘들게 의경에 붙었지만, 고급시계에 빠져버린 준서는 자기 대신 복무를 해줄 피노키오를 만들려고 한다.

준서는 길이가 L인 염기열을 가지고 있는데, 이 염기열에서 각 1개씩의 ‘A’, ‘C’, ‘G’, ‘T’ 염기를 빼내어 합성하면 하나의 피노키오를 만들 수 있다. 자신이 직접 가는 것은 아니지만, 좋은 게 좋은 거라고 준서는 이 중 가장 일을 잘할 것 같은 피노키오를 만들려고 한다. 같은 염기더라도 염기열의 어디에 위치해 있느냐에 따라서 조금씩 다르므로, 완전히 같은 위치의 네 염기로 이루어진 게 아니라면 서로 다른 성질의 피노키오가 된다. 준서의 편안한 고급시계 생활을 위해 만들 수 있는 피노키오의 종류가 총 몇 개나 되는지 알려주자.

첫 줄에 문자열의 길이 L(1 ≤ L ≤ 1,000,000)이 주어진다. 둘째 줄에 길이 L의 문자열 S가 주어진다. 모든 문자는 ‘A’, ‘C’, ‘G’, ‘T’ 중 하나이다.

한 줄에 가능한 피노키오의 종류를 1,000,000,007로 나눈 나머지를 출력한다.