Поликарп очень любит геометрические прогрессии. Так как ему только три года, он любит прогрессии только длины три. Также у него есть любимое целое число k и последовательность a, состоящая из n целых чисел.
Он хочет узнать: сколько подпоследовательностей длины три можно выбрать из a так, чтобы они образовывали геометрическую прогрессию со знаменателем k.
Подпоследовательностью длины три называются три таких индекса i1, i2, i3, что 1 ≤ i1 < i2 < i3 ≤ n. То есть подпоследовательности длины три — это такие тройки элементов, которые необязательно идут подряд в последовательности, но их индексы строго возрастают.
Геометрическая прогрессия со знаменателем k — это последовательность чисел вида b·k0, b·k1, ..., b·kr - 1.
Поликарпу всё ещё три года, поэтому он не может посчитать это количество самостоятельно. Помогите ему сделать это.
Примечание
В первом примере ответ четыре, так как в качестве первого элемента можно выбрать любую из двух единиц, в качестве второго — любую из двух двоек, а третий элемент подпоследовательности обязательно должен равняться четырём.