Ones

Time limit1sMemory limit1024 MB

Summary

Given N ones and a repdigit of M copies of digit d, divide the first by the second and output the digit sum of the quotient, or NESIDALO if it is not an integer.

Level: Medium7 of 10
Topics: Number theory, Math, Implementation
Solved: No attempts yet

Statement

Ugnė and Jūratė enjoy collecting mascots with various numbers on them. Jūratė only collects mascots with numbers made of the same digit. Ugnė collects mascots with numbers made of ones.

One day, while studying division, the girls noticed that if they divide some of Ugnė's numbers by Jūratė's numbers, the result can be a number with an interesting shape. For example, 111 111 111 / 9 = 12 345 679.

The girls wondered what other sequences of numbers can be produced and what the sums of their digits are. The numbers may be very big, and it is too complicated for the girls to do the division by hand. You are asked to help.

You are given Ugnė's number and Jūratė's number. Divide Ugnė's number by Jūratė's number, compute the result, and find the sum of the digits of the result.

Input

On the first line, one integer N is given: the number of digits in Ugnė's number. Ugnė's number consists of N ones.

On the second line, two integers M and d are given. Jūratė's number is the digit d repeated M times.

Output

Output the sum of the digits of the division result. If the division result is not an integer, output NESIDALO (Lithuanian for "not divisible").

Constraints

$1 \le N \le 500\,000\,000$

$1 \le M \le 1\,000\,000$

$1 \le d \le 9$

Examples2

Example 1
Input
```
9
1 9
```
Expected output
```
37
```
Example 2
Input
```
6
2 4
```
Expected output
```
NESIDALO
```