Problem Description

Input Format

The input is given from the standard input in the following format:

$ a $ $ b $ $ c $ $ d $

Four positive integers $ a, b, c, d $ are given in one line.

Output Format

Output the number of palindromic numbers that satisfy the conditions in one line.

Sample Input and Output

Sample Input #1

1001 9999 9 36

Sample Output #1

1

Sample Input #2

1001 4004 49 20

Sample Output #2

1

Sample Input #3

1000000001 9999999999 50 50

Sample Output #3

0

Notes/Hints

We have rejudged the problem. We apologize for the inconvenience. (Added on 01/24 22:16:18)

The partial points cases are correct, but we found that sub2-3.txt is incorrect. We will rejudge after deleting it. (Added on 01/24 22:12:49)

Problem Statement

The substring "1001" in $ square1001 $'s name is a palindromic number.

That is, he likes palindromic numbers.

So, E869120 gave him the following problem:

"There are numbers between $ a $ and $ b $. Among them, how many palindromic numbers are multiples of $ c $ and have a digit sum of $ d $?"

$ square1001 $ tried to solve it by brute force, but couldn't because $ a $ and $ b $ are quite large.

Find the answer to that problem modulo $ 10000 $.

Constraints

• $ a < b $
• $ 2 ≦ |a| = |b| ≦ 80 $ and $ |a|, |b| $ are multiples of 2
• $ 1 ≦ c ≦ 50 $
• $ 1 ≦ d ≦ 720 $
• $ a, b $ are palindromic numbers

Here, $ |a| $ represents the number of digits in $ a $.

Partial Points

If you correctly solve all datasets satisfying $ 1 ≦ a, b ≦ 10,000,000,000 $, you will be awarded 20 points.

If you correctly solve all remaining datasets, you will be awarded 80 points.

Sample Explanation 1

"9999" satisfies the conditions.

Sample Explanation 2

"3773" satisfies the conditions.

Sample Explanation 3

There are no palindromic numbers ending with "0". Problem statement author: E869120

见题面 Input 部分

见题面 Output 部分