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 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 ≤ W < 666³⁶.

Output

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