17255번 - N으로 만들기

준하는 노트에 수를 적다가 수가 만들어지는 방식을 깨달았다.

처음에 어떤 숫자 하나를 적고 만들어진 수의 왼쪽이나 오른쪽에 숫자를 계속 붙이면 어떤 수 N이든 만들 수 있다는 것이다.

다시 말해 어떤 수 N을 만들기 위해서는, 처음에 어떤 숫자를 하나 적고 아래의 두 가지 행동을 반복한다.

1. 수의 왼쪽에 숫자를 하나 적는다.
2. 수의 오른쪽에 숫자를 하나 적는다.

준하는 어떤 수 N을 만드는 방법의 수가 몇 가지인지 궁금해졌다. 이를 알아내는 프로그램을 작성해주자. 숫자를 적는 과정에서 나온 수가 순서대로 모두 같다면 같은 방법이다.

단, 숫자를 적는 과정에서 수는 0으로 시작할 수 있다.

음이 아닌 정수 N이 주어진다. (0 ≤ N ≤ 10,000,000)

N을 만드는 방법의 수를 출력한다.