Tsyfirkin's new student Feofan is much more intelligent and bright than Mitrofanushka. In the first three lessons, he has learned to add positive integers in columns, not very quickly but without mistakes. For this he uses the following algorithm.

1. Feofan adds numbers from right to left: first he adds units, then tens, and so on.
2. He takes the pair of digit in each successive column and adds them.
3. If a 1 is carried from the previous column, Feofan adds it to the obtained sum.
4. He writes the rightmost digit of the sum in the answer line and, if necessary, makes a mark about carrying 1 to the next column.
5. If there are no more columns and there is a 1 carried from the leftmost column, then Feofan writes 1 on the left of the answer.

Feofan needs one second to write one digit or to make a mark about carrying a 1. If at least one of summands is 0 or 1, then Feofan spends one second adding them; if both numbers are greater than 1, then he adds them in two seconds. However, having added two numbers, Feofan remembers the result and can recall it afterwards in one second. If he needs to calculate a + b and he has calculated b + a before, then he also can use the result obtained earlier. Unfortunately, Feofan does not remember all the results at the next lesson and has to calculate and remember them anew.

For example, Feofan adds the numbers 526 and 625 in 12 seconds: he spends four seconds for writing the digits of the answer, two seconds for making marks about carrying over, two seconds for calculating each of the sums 6 + 5 and 2 + 2, and one second for calculating each of the sums 4 + 1 and 5 + 6 (since he remembers from the previous calculations that 6 + 5 = 11).

In the beginning of a new lesson Tsyfirkin writes on the blackboard two k-digit integers and gives Feofan the task of adding them. Tsyfirkin has chosen each of the integers with equal probabilities from the set of positive k-digit integers without leading zeros. Find the mathematical expectation of the time Feofan will need to add the integers.

In the only line you are given the integer k (1 ≤ k ≤ 5000).

Output the expected time of adding two positive k-digit integers with an absolute or relative error of at most 10⁻⁶.