Making the Number N

Interview

Time limit1sMemory limit256 MB

Summary

Count how many digit-by-digit sequences build the number N when each new digit is attached to the left or right end.

Level: Medium5 of 10
Topics: Dynamic programming, String, Combinatorics, Brute force
Solved: No attempts yet

Problem

While writing numbers in his notebook, Junha realized how numbers can be built.

He saw that by writing one digit first and then repeatedly attaching digits to the left or right of the number built so far, he can make any number N.

In other words, to make a number N, he writes one digit first and then repeats the following two actions.

Write a digit on the left of the number.
Write a digit on the right of the number.

Junha wonders how many ways there are to make a given number N. Write a program to find this out. Two ways are the same if the numbers produced at each step of the writing process are all the same in order.

During the writing process, a number may begin with 0.

Input

A non-negative integer N is given. (0 ≤ N ≤ 10,000,000)

Output

Print the number of ways to make N.

Examples2

Example 1
Input
```
521
```
Expected output
```
4
```
Example 2
Input
```
9111
```
Expected output
```
4
```