Мальчик Филя прочитал в одном научном журнале, что не так давно астрономы открыли новую планету, на которой как и на Земле существует жизнь. Ученые уже установили связь с ее жителями и успели выяснить, что эта планета обращается вокруг своей оси за другое время, поэтому сутки здесь длятся не 24 часа. На ней, так же как и на Земле, время измеряется часами, минутами и секундами. Но количество минут в часе, и секунд в минуте не совпадает с привычными земными.
А именно: в одном часе A минут, в одной минуте B секунд. Также, в одних сутках на этой планете X часов, Y минут Z секунд. То есть когда часы должны показать момент времени X:Y:Z, они показывают 0:0:0, и с этого момента начинается отсчет новых суток
Электронные часы здесь выглядят так же, как и на Земле: на них есть дисплеи для отображения часов, минут и секунд. Каждый из дисплеев содержит минимальное количество десятичных разрядов, которое требуется, чтобы отобразить любое количество часов, минут и секунд в течении суток, соответственно. Когда на дисплее показывается число с меньшим количеством разрядов, то оно дополняется ведущими нулями. В остальном часы на этой планете работают аналогично земным электронным часам.
Филя увлекается нумерологией, поэтому его интересует вопрос: сколько хороших моментов времени на часах этой планеты будет показано с момента времени H1:M1:S1 до момента времени H2:M2:S2 включительно. Филя называет момент времени хорошим, если в нем не содержится цифры c, то есть ни один из дисплеев не содержит (с учетом вышеописанных правил) цифру c.
Входные данные
В первой строке находятся два натуральных числа A, B (1 ≤ A, B ≤ 50) — количество минут в часе и секунд в минуте.
В следующей строке находятся три целых числа X, Y, Z (0 ≤ X ≤ 50, 0 ≤ Y < A, 0 ≤ Z < B) — количество часов, минут и секунд в сутках. Гарантируется, что X, Y, Z одновременно не равны нулю.
В следующей строке находятся три целых числа H1, M1, S1— стартовое время. Гарантируется, что это время, которое часы могут отобразить в течении суток.
В следующей строке находятся три целых числа H2, M2, S2— конечное время время. Гарантируется, что это время, которое часы могут отобразить в течении суток.
Обратите внимание, что моменты времени могут находиться в разных сутках. Также обратите внимание, что моменты времени могут совпадать. В этом случае в интервале находится единственный момент времени.
В следующей строке находится цифра c (0 ≤ c < 10).
Выходные данные
Требуется вывести одно число — количество хороших моментов времени с H1:M1:S1 до H2:M2:S2 включительно.
Пример входных и выходных данных
| Ввод |
Вывод |
3 2
5 0 0
0 0 0
1 0 0
3 |
7 |
4 2
3 1 1
1 0 0
0 0 0
0 |
6 |
50 50
24 0 0
3 0 0
18 15 0
7 |
26956 |