Ritual

An ancient order worships two sacred numbers carved on a silicon slab: the Great Sacred Number and the Small Sacred Number. The Small Sacred Number is 666, which is also the number of days in the order's week.

Every morning the priests write the Great Sacred Number in full on the temple wall. During the day, following a secret rule, they erase the digits in some of its positions and leave the rest on the wall for the night. The next morning the whole number is written again and the ritual repeats.

The secret rule has two parts. After the erasing, the digits that remain (kept in their original order and read from left to right) must satisfy both of the following:

1. They form a palindrome: the first digit equals the last, the second equals the second to last, and so on.
2. Read as a single number, it is divisible by 666. The remaining number may have leading or trailing zeros, but at least one digit must remain (the priests may not erase every digit).

Two erasing patterns are considered different when the set of kept positions differs, even if the resulting number is the same. Each day the priests must use a pattern that has never been used before. Their creativity is perfect, so they will eventually use every valid pattern exactly once. On the first day when no unused valid pattern remains, the world ends.

The priests use their first pattern on day 1 of the week, the next on day 2, the next on day 3, and so on. The week consists of 666 days numbered from 1 to 666, after which it repeats from the start. Given the Great Sacred Number, find the weekday on which the priests carry out their last valid pattern, that is, the weekday after which the world ends.

If there are $N$ valid patterns in total, the answer is $((N - 1) \bmod 666) + 1$, a value between 1 and 666.

One line containing the Great Sacred Number $G$ as a string of decimal digits with no leading zero. The number of digits of $G$ is between 1 and 66636.

Print a single integer between 1 and 666: the weekday on which the priests perform their last valid pattern (the weekday after which the world ends).