У Юры есть команда из k разработчиков и список из n заданий, пронумерованных от 1 до n. Юра собирается выбрать некоторые задания, чтобы сделать их на этой неделе. Из-за странных традиций в компании Looksery, номера сделанных заданий должно быть отрезком последовательных целых чисел, содержащим не менее 2 чисел, то есть последовательность вида l, l + 1, ..., r для некоторых 1 ≤ l < r ≤ n.

С каждым заданием i связано целое число a_i, обозначающее количество человекочасов, необходимых для выполнения i-го задания. Разработчики не всегда бывают в себе уверены, и, в общем-то, боятся сложных заданий. Зная это, Юра решил взять самое сложное задание (то, на которое уйдет наибольшее количество человекочасов, из нескольких самых сложных заданий с одинаковы уровнем сложности он выбирает произвольное задание) и сделать его самому. Таким образом, если выбраны задания с номерами [l, r], то разработчикам остается самостоятельно завершить ровно r - l заданий.

Каждый разработчик может провести любое целочисленное количество часов над любым заданием, но когда вся работа завершена, i-му заданию должно быть уделено ровно a_i человекочасов.

И наконец, проблема в том, что разработчик злится, когда он работает больше другого разработчика. Множество заданий [l, r] считается хорошим, если можно найти такое распределение работы, что все задания можно выполнить, а все разработчики работают одинаковое количество времени (количество работы, которую произведёт Юра, не имеет значения ни для него, ни для других разработчиков).

Для примера предположим, что Юра выбрал задания со следующими сложностями: a = [1, 2, 3, 4], а у него в распоряжении три разработчика. Юра берет себе самое сложное, четвертое задание, а разработчикам дает задания со сложностями [1, 2, 3]. Если первый разработчик тратит час на первое задание и час на третье, второй разработчик тратит два часа на второе задание, а третий разработчик тратит два часа на третье задание, то когда вся работа будет завершена, окажется, что каждый разработчик работал ровно два часа, а над каждым заданием работали необходимое время. В качестве ещё одного примера скажем, что если бы на первое задание требовалось два часа, а не один, то тогда было бы невозможно распределить задания способом, описанным выше.

Помимо работы Юра обожает решать задачи. Ему интересно, сколько есть пар (l, r) (1 ≤ l < r ≤ n), таких, что отрезок [l, r] является хорошим? Юра уже решил эту задачу, но времени написать код у него нет. Пожалуйста, помогите Юре и реализуйте решение этой задачи.