• Праздник у вирусов
  HOLIDAY AT VIRUSES

Описание
Однажды летом на нашу планету упал метеорит, на котором прилетели неизвестные земной науке вирусы. При проходе метеорита через плотные слои атмосферы выжили всего N вирусов (0<N<300). Земля вирусам очень понравилась, и они решили здесь обосноваться. 

Каждый вирус порождает в день M потомков. Каждый вирус живёт бесконечно долго. (Например, если на Землю прилетели 3 вируса, то уже на следующий день их будет 3+3M)

У вирусов наступает праздник "Х" если сумма цифр их популяции делится на X. 

Задача
Вам нужно определить, сколько праздников "Х" отметят вирусы за K (K<100) дней.

Технические требования:

Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT

Во входном файле задано четыре целых числа: N, M, K, X.
В выходном файле должно быть выведено количество праздничных дней.

Примеры:

INPUT.TXT
2  2  1  4

OUTPUT.TXT
1