룬 알고리즘

대부분의 은행 카드에는 카드 번호라고 부르는 16자리 숫자가 적혀 있다. 16자리 숫자라면 아무거나 올바른 카드 번호가 되는 것은 아니고, 카드 번호는 룬 알고리즘(Luhn algorithm)을 만족해야 한다. 룬 알고리즘은 다음과 같이 동작한다.

1. 마지막 자리부터 세어 뒤에서 두 번째, 뒤에서 네 번째처럼 한 자리씩 건너뛴 자리의 숫자를 두 배로 만든다.
2. 두 배로 만든 값이 10 이상이면 그 값의 각 자리 숫자를 더해 한 자리 수로 바꾼다.
3. 이렇게 얻은 16개의 수를 모두 더한다.
4. 더한 값이 10으로 나누어떨어지면 올바른 카드 번호다.

예를 들어 카드 번호가 1234567890123452이면 각 단계는 다음과 같다.

마지막 줄의 수를 모두 더하면 60이고, 60은 10으로 나누어떨어지므로 이 카드 번호는 올바르다.

주어진 카드 번호가 올바른지 판정하라.

첫째 줄에 카드 번호를 나타내는 16자리 숫자가 주어진다. 맨 앞자리가 0일 수도 있으므로 숫자를 문자열로 읽어야 16자리가 그대로 남는다.

주어진 번호가 올바른 카드 번호이면 DA를, 그렇지 않으면 NE를 출력한다.