A top secret message containing uppercase letters from 'A' to 'Z' has been encoded as numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

You are an FBI agent and you need to determine the total number of ways that the message can be decoded.

Since the answer could be very large, take it modulo 109 + 7.

Example

For message = "123", the output should be

solution(message) = 3.

"123" can be decoded as "ABC" (1 2 3), "LC" (12 3) or "AW" (1 23), so the total number of ways is 3.

Input/Output

• [execution time limit] 3 seconds (java)

• [memory limit] 1 GB

• [input] string message

  A string containing only digits.

  Guaranteed constraints:

  0 ≤ message.length ≤ 105.

• [output] integer

  The total number of ways to decode the given message.

풀이

int solution(String message) {
    int n = message.length();
    if (n == 0) return 1;

    // 메시지의 각 문자까지 디코딩하는 방법 수를 저장할 배열 생성
    long[] ways = new long[n + 1];
    ways[0] = 1; // 빈 문자열을 디코딩하는 방법은 1가지

    for (int i = 1; i <= n; i++) {
        char currentChar = message.charAt(i - 1);
        
        // 현재 문자가 혼자 디코딩 가능한지 확인
        if (currentChar != '0') {
            ways[i] += ways[i - 1];
        }

        // 현재 문자와 이전 문자가 두 자릿수 숫자로 디코딩 가능한지 확인
        if (i > 1) {
            char previousChar = message.charAt(i - 2);
            int twoDigitNumber = (previousChar - '0') * 10 + (currentChar - '0');
            if (twoDigitNumber >= 10 && twoDigitNumber <= 26) {
                ways[i] += ways[i - 2];
            }
        }

        // 오버플로우를 방지하기 위해 결과를 10^9 + 7 로 나눈다.
        ways[i] %= 1000000007;
    }

    return (int) ways[n];
}