의식

어느 고대 교단은 규소 석판에 새겨진 두 개의 성스러운 수를 숭배한다. 하나는 큰 성수(Great Sacred Number), 다른 하나는 작은 성수(Small Sacred Number)이다. 작은 성수는 666이며, 이 교단의 한 주(週)를 이루는 날의 수이기도 하다.

사제들은 매일 아침 큰 성수를 남김없이 신전 벽에 적는다. 낮 동안에는 비밀 규칙에 따라 몇몇 자리의 숫자를 지우고, 남은 숫자들을 그날 밤 동안 벽에 남겨 둔다. 다음 날 아침이 되면 다시 전체 수를 적고 의식을 반복한다.

비밀 규칙은 두 부분으로 이루어져 있다. 숫자를 지운 뒤 남은 숫자들을(원래 순서를 그대로 유지한 채 왼쪽에서 오른쪽으로 읽었을 때) 다음 두 조건을 모두 만족해야 한다.

1. 회문(팰린드롬)을 이루어야 한다. 즉 첫 번째 숫자와 마지막 숫자가 같고, 두 번째 숫자와 뒤에서 두 번째 숫자가 같으며, 이런 식으로 좌우 대칭이어야 한다.
2. 하나의 수로 보았을 때 666으로 나누어떨어져야 한다. 남은 수는 앞이나 뒤에 0이 올 수 있지만, 적어도 한 자리는 남아 있어야 한다(모든 숫자를 지울 수는 없다).

두 지우기 방식은 남기는 자리(위치)들의 집합이 다르면 서로 다른 것으로 본다. 남은 수가 같더라도 남긴 위치가 다르면 다른 방식이다. 사제들은 매일 한 번도 사용한 적 없는 새로운 방식을 써야 한다. 사제들의 창의력은 완벽하므로, 결국 가능한 모든 유효한 방식을 정확히 한 번씩 사용하게 된다. 더 이상 쓸 수 있는 새로운 유효한 방식이 남지 않는 첫날, 세상은 끝난다.

사제들은 첫 번째 방식을 그 주의 1일째에, 다음 방식을 2일째에, 그다음을 3일째에 사용하는 식으로 진행한다. 한 주는 1부터 666까지 번호가 매겨진 666일로 이루어지며, 그 뒤에는 다시 처음부터 반복된다. 큰 성수가 주어질 때, 사제들이 마지막 유효한 방식을 수행하는 요일, 즉 그 뒤에 세상이 끝나게 되는 요일을 구하여라.

유효한 방식이 모두 $N$가지라면, 답은 $((N - 1) \bmod 666) + 1$이며 1 이상 666 이하의 값이다.

한 줄에 큰 성수 $G$가 앞자리 0 없이 10진수 숫자열로 주어진다. $G$의 자릿수는 1 이상 66636 이하이다.

사제들이 마지막 유효한 방식을 수행하는 요일(그 뒤에 세상이 끝나게 되는 요일)을 1 이상 666 이하의 정수 하나로 출력한다.