### PROBLEM LINK:

**Author:** Full name

**Tester:** Full name

**Editorialist:** Oleksandr Kulkov

### DIFFICULTY:

CAKEWALK

### PREREQUISITES:

Basic combinatorics, rational numbers

### PROBLEM:

You’re given number N. You have to find co-prime numbers P \geq 0 and Q > 0 such that P/Q is equal to probability of number composed of N digits to be a palindrome.

### QUICK EXPLANATION:

Output 1 and 10^{\lfloor N / 2 \rfloor}.

### EXPLANATION:

Since leading zeroes are allowed, you can just pick each digit independently which will give you total of 10^N ways to compose the N-digit number. Now how much palindromes you can obtain? If N is even, you can pick first N/2 digits arbitrarily (it can be done in 10^{N/2} ways) and duplicate them to make a palindrome:

For odd N you can pick first (N-1)/2 digits and the middle digit (10^{(N+1)/2} ways) and then duplicate them in similar manner:

You can generalize for arbitrary N that you can compose a palindrome in 10^{\lceil N/2 \rceil} ways. Thus the rational number we seek for is:

Thus we have to output 1 and 10^{\lfloor N / 2 \rfloor}.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.