Numerology X44677

Nine Zynoulus is a numerologist, who sees the number 666 and other palindromes everywhere. She thinks that palindromes which are divisible by 666, like $66603330666$ or $666$ itself, are very important; we call them VIN (Very Important Numbers). Recently, when browsing ancient Measharan inscriptions, she has seen a quite long number $W$, which does not let her sleep easily. She spends her nights counting ways of removing some digits in $W$ such the remaining number is a VIN. For example, for $W = 6666666$ she could erase each single $6$ digit (in 7 ways), or she could erase four digits (in ${7 \choose 4} = 35$ ways), thus she would get 42 ways. Her intuiton tells her that the number of ways is divisible by 666, so she returns to 1 after counting each 666th way. Please write a program which will let her verify her intuition.

Input

Input is a single integer $W$, $1 \leq W < 666^{36}$.

Output

Return a single number $x$, $0 \leq x < 666$, which is the number of ways modulo 666.