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

Правила создания колоды в этой игре очень просты. Изначально Вова получает колоду из n карт, а также магическое число k. Порядок карт в колоде строго фиксирован, нельзя её перемешивать. На картах записаны числа: a_i — число на i-й карте в колоде, которую получает Вова.

После этого Вова убирает x (возможно, что x = 0) первых карт из начала колоды и y (возможно, y = 0) карт из конца, и оставшиеся карты составляют колоду Вовы (хотя бы одна карта должна остаться). То есть новая колода Вовы включает в себя карты, которые были на позициях x + 1, x + 2, ... n - y - 1, n - y в колоде, которую он получил.

Новая колода считается правильной тогда и только тогда, когда произведение чисел, записанных на всех картах новой колоды, делится на k нацело. Итак, Вова получил колоду (не обязательно правильную) и число k, и теперь он хочет знать, сколько существует различных способов выбрать x и y так, что колода, полученная после удаления x карт из начала и y карт из конца, является правильной?