Often a problem "A + B" is proposed as a trial at various olympiads in informatics, where according to given integers A and B, it is required to find their sum.

During the city Informatics Olympiad the chairman of the jury decided to prepare tests for this task himself. To do this, he used his original technique, that consisted in the following: first he prepared the correct answers and then picked up the input data corresponding to these answers.

Let the jury chairman choose the number C that consists of n decimal digits and does not start from zero. Now he wants to choose such positive integers A and B that their sum equals to C, and they also consists of n decimal digits and did not start with zero. In addition, the jury chairman tries to find such numbers A and B, that each of them is beautiful. Beautiful in his understanding is a number which notation does not contain two identical consecutive numbers. For example, the number 1272 is considered beautiful, and the number 1227 is not.

Write a program that for a given positive integer C finds the number of pairs of beautiful positive numbers A and B with sum C. Since the number of pairs of beautiful numbers can be large, it is necessary to print the remainder from dividing this number by 109 + 7.

Input

One positive integer C that does not start from zero. The number of digits in С do not exceed 10000.

Output

Print one number - the remainder from dividing the number of pairs of beautiful numbers A and B by number 109 + 7.

Explanations to samples

Number 22 can be represented as a sum of two-digit numbers in three ways: 10 + 12, 11 + 11, 12 + 10. The method 11 + 11 does not fit, because 11 is not beautiful. So the answer for the number 22 is 2.

Number 200 can be represented as a sum of three-digit numbers in one way: 100 + 100. This way does not fit, so the answer for 200 is 0.

Number 1000 cannot be represented as a sum of four-digit numbers, so the answer for 1000 is 0.