E. Сон
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Однажды Вася лежал в кровати и для того, чтобы быстрее заснуть, наблюдал за своими электронными часами.

Вася живет в странной стране, где в сутках h часов, а в каждом часе m минут. Часы показывают время в десятичной системе счисления в формате H:M, где строка H всегда имеет фиксированную длину, равную количеству цифр в десятичной записи числа h - 1, для этого, при необходимости, добавляются лидирующие нули. Строка M имеет аналогичный вид, и ее длина всегда равна количеству цифр в записи числа m - 1. Например, если h = 17, m = 1000, то время равное 13 часам и 75 минутам будет отображаться как «13:075».

Вася наблюдал за часами с момента h1 часов m1 минут до h2 часов m2 минут включительно, а затем он заснул. Теперь он просит вас подсчитать, сколько раз он видел момент, в который на часах переключилось не менее k цифр одновременно.

Например, при переключении 04:19  →  04:20 изменяется две цифры, при 23:59  →  00:00 — четыре цифры.

Считайте, что Вася наблюдал за часами строго меньше суток. Обратите внимание, что последние значения, которые увидел Вася на часах до того, как заснуть, — это «h2:m2». То есть момент, в который время «h2:m2» переключается на следующее значение, Вася не видит.

Входные данные

В первой строке входного файла записаны через пробел три целых числа h, m и k (2 ≤ h, m ≤ 109, 1 ≤ k ≤ 20). Во второй строке записаны разделенные пробелом целые числа h1, m1 (0 ≤ h1 < h, 0 ≤ m1 < m). В третьей строке записаны разделенные пробелом целые числа h2, m2 (0 ≤ h2 < h, 0 ≤ m2 < m).

Выходные данные

Выведите единственное число — сколько раз Вася увидел момент переключения не менее k цифр одновременно.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout (также вы можете использовать спецификатор %I64d).

Примеры
Входные данные
5 5 2
4 4
2 1
Выходные данные
3
Входные данные
24 60 1
0 0
23 59
Выходные данные
1439
Входные данные
24 60 3
23 59
23 59
Выходные данные
0
Примечание

В первом примере Вася увидит следующие моменты времени: 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·60 = 1440, но из них Вася не увидел одно переключение 23:59 00:00.

В третьем примере Вася уснул сразу после того, как начал смотреть на часы, значит он не увидел ни одного переключения.