The lock

After rescuing your teammate, a thought snapped into your minds: "what if the terrorists launch an attack against us again?" So you decided that it is time for the "FINAL SHOWDOWN!" and this time WE will be the ones who attack their base. The system administrators of the Faculty of Informatics are part-timers in the National Secrecy Agency, so they moved a couple threads and gained the coordinates of the secret terrorist base. However as soon as the special unit, consisting of the participant of the programming contest reached the base, they encountered a strange numerical lock. Your task is to decide if the lock is breakable or not!

Input

The input is a single line, terminated with an end of line character. The line contains a single positive integer n such that none on its digits are 0.

Rules

The task is to verify if the code is breakable, which means that "is it possible to delete n based on the following rules?"

• Take the first digit of n and denote it by d.
• Choose a number between 1 and d (both endpoints are included), denote it by k and remove the first k characters of n. Naturally you cannot delete more characters than the length of the number.
• Subtract k from the first digit of the remaining number if the resulting number is positive. Otherwise leave the first character of the remaining number as it is.
• Continue the process with this new n until you are able to completely delete the number or you are stuck. Note: the last deletion must be precise, so the task is only solvable if in the last step the first digit of the remaining number is the same as the length of the number. For a more precise explanation, see the example!

Note: usually you can delete the initial number in many different way, but the question only asks if it is possible to delete it or not.

Output

The output is the number 1 if the code is breakable and the number 0 if not.

Example

Explanation

In the first case the number may be deleted by for example choosing 2 at the start (we can choose any number between 1 and 7) and remove the first 2 characters. This way we get 45, but since we removed 2 characters, we need to subtract 2 from 4. So our new number is 25 which we can precisely remove by choosing 2. So the task is completable.
In the second case we can only choose 1 at the start, so if we delete the first digit we get 2345. After subtracting 1 from the first number, our new number is 1345. Again we can only delete 1 digit, so we are left with 345. After subtracting 1 again from 3 we are left with 245. Now we can either remove 1 or 2 digits. If we remove 2 digits then we are left with 5 which we need to lower by 2, so our new number is 3. However based on the rule of precise deletion we cannot get rid of this 3. So we cannot remove 2 digits from 245. If we remove 1 digit, then the remaining number is 45 and after lowering 4 by 1, we get that the new number is 35. From 35 we can remove 1, 2 or 3 digits, however 3 is impossible, since the length of the number is 2. Removing 2 digits is also impossible because of the rule of precise deletion, so we can only remove 1 digit and we are left with 5. After lowering 5 with 1 we have 4 which we cannot remove because of the precise deletion rule.
For the last number (3531211749446117) we only provide a possible solution with the following abbreviations: Dx = deleting x digits, and S = subtracting from the first digit. For S we do not need a parameter, since if the subtraction is possible, then we always subtract the number of deleted digits.
3531211749446127 -D1,S- 431211749446127 -D4- 11749446127 -D1- 1749446127 -D1,S- 649446127 -D4- 46127 -D3- 27 -D2- NULL