CF113E.Sleeping

One day Vasya was lying in bed watching his electronic clock to fall asleep quicker.

Vasya lives in a strange country, where days have h hours, and every hour has m minutes. Clock shows time in decimal number system, in format H:M, where the string H always has a fixed length equal to the number of digits in the decimal representation of number h - 1. To achieve this, leading zeros are added if necessary. The string M has a similar format, and its length is always equal to the number of digits in the decimal representation of number m - 1. For example, if h = 17, m = 1000, then time equal to 13 hours and 75 minutes will be displayed as "13:075".

Vasya had been watching the clock from _h_1 hours _m_1 minutes to _h_2 hours _m_2 minutes inclusive, and then he fell asleep. Now he asks you to count how many times he saw the moment at which at least k digits changed on the clock simultaneously.

For example, when switching 04:19  →  04:20 two digits change. When switching 23:59  →  00:00, four digits change.

Consider that Vasya has been watching the clock for strictly less than one day. Note that the last time Vasya saw on the clock before falling asleep was "h2:m2". That is, Vasya didn't see the moment at which time "h2:m2" switched to the next value.

一天，瓦西娅躺在床上看着他的电子钟，想尽快入睡。

瓦西娅生活在一个奇特的国家，那里的一天有 $h$ 个小时，每小时有 $m$ 分钟。该电子钟采用十进制显示时间，格式为 H:M，其中字符串 H 的长度恒等于数字 $h-1$ 的十进制表示的位数；若不足，则在前面补零。字符串 M 的格式类似，其长度恒等于数字 $m-1$ 的十进制表示的位数。例如，若 $h = 17$、$m = 1000$，则时间为 13 小时 75 分钟时，将显示为 "13:075"。

瓦西娅从 $h_1$ 小时 $m_1$ 分钟开始观看时钟，一直持续到（包含）$h_2$ 小时 $m_2$ 分钟为止，然后入睡。现在他请你计算：在他观看期间，有多少次他看到了时钟上至少 $k$ 个数字同时发生变化的瞬间。

例如，从 04:19 切换到 04:20 时，有两位数字发生变化；从 23:59 切换到 00:00 时，有四位数字发生变化。

请注意：瓦西娅观看时钟的时间严格小于一整天。另外，瓦西娅入睡前所看到的最后一个时刻是 "h2:m2"，即他并未看到时间 "h2:m2" 切换至下一时刻的那个瞬间。

The first line of the input file contains three space-separated integers h, m and k (2 ≤ h, m ≤ 109, 1 ≤ k ≤ 20). The second line contains space-separated integers _h_1, _m_1 (0 ≤ _h_1 < h, 0 ≤ _m_1 < m). The third line contains space-separated integers _h_2, _m_2 (0 ≤ _h_2 < h, 0 ≤ _m_2 < m).

输入文件的第一行包含三个以空格分隔的整数 $h$、$m$ 和 $k$（$2 \le h, m \le 10^9$，$1 \le k \le 20$）。第二行包含两个以空格分隔的整数 $h_1$、$m_1$（$0 \le h_1 < h$，$0 \le m_1 < m$）。第三行包含两个以空格分隔的整数 $h_2$、$m_2$（$0 \le h_2 < h$，$0 \le m_2 < m$）。

Print a single number — the number of times Vasya saw the moment of changing at least k digits simultaneously.

Please do not use the %lld specificator to read or write 64-bit integers in C++. It is preferred to use the cin stream (also you may use the %I64d specificator).

输出一个整数——即瓦西娅观察到至少有 k 位数字同时发生变化的时刻的次数。

在 C++ 中，请勿使用 %lld 特定格式说明符来读取或写入 64 位整数。推荐使用 cin 流（当然，您也可以使用 %I64d 格式说明符）。

In the first example Vasya will see the following moments of time: 4:4 0:0  →  0:1  →  0:2  →  0:3  →  0:4 1:0  →  1:1  →  1:2  →  1:3  →  1:4 2:0  →  2:1  →  2:2  →  2:3  →  2:4. Double arrow () marks the sought moments of time (in this example — when Vasya sees two numbers changing simultaneously).

In the second example k = 1. Any switching time can be accepted, since during switching of the clock at least one digit is changed. Total switching equals to 24·60 = 1440, but Vasya have not seen one of them — the switching of 23:59 00:00.

In the third example Vasya fell asleep immediately after he began to look at the clock, so he did not see any change.

在第一个例子中，瓦西娅将看到以下时刻：4:4 0:0  →  0:1  →  0:2  →  0:3  →  0:4 1:0  →  1:1  →  1:2  →  1:3  →  1:4 2:0  →  2:1  →  2:2  →  2:3  →  2:4。双箭头（）标记了所求的时刻（本例中即瓦西娅同时看到两个数字发生变化的时刻）。

在第二个例子中，$k = 1$。任意一个翻转时刻均可被接受，因为钟表翻转时至少有一位数字会发生变化。总的翻转次数为 $24 \cdot 60 = 1440$，但瓦西娅未看到其中一次——即 23:59 00:00 的翻转。

在第三个例子中，瓦西娅刚一开始看钟就睡着了，因此他没有看到任何变化。