Ацингел — достаточно маленький городок. В этом городке был всего один доктор — Мисс Ада. Она была очень дружелюбной и никто никогда не говорил про неё ничего плохого. Так что кто мог подумать, что Аду найдут мёртвой в собственном доме? Мистер Гаври, известный во всём мире детектив, был назначен найти преступника. Он опросил \(m\) соседей Ады о клиентах, которые посетили её в тот злосчастный день. Давайте пронумеруем этих клиентов от \(1\) до \(n\). Свидетельством каждого соседа является перестановка этих чисел, которая описывает порядок, в котором этот сосед видел клиентов приходящими к Аде.
Однако некоторые факты выглядят достаточно подозрительно — как могло быть, что, согласно некоторым перестановкам некоторые клиенты были замечены утром, а согласно другим — вечером? «Утром некоторые из соседей скорее всего спали! — подумал Гаври, — А вечером слишком темно, чтобы видеть лица людей...». Теперь он хочет удалить из каждой перестановки некоторый префикс и некоторый суффикс (возможно, пустые) так, что оставшиеся части будут не пусты и равны друг другу. Возможно, часть потенциальных преступников пропадёт, но хотя бы не будет противоречий в свидетельствах соседей.
Сколькими способами он может это сделать? Два способа называются разными, если в них отличается оставшаяся общая часть.
Выходные данные
Выведите одно целое число — количество способов удалить из каждой перестановки некоторый префикс и суффикс (возможно, пустые) так, что оставшаяся часть была бы равной и непустой.
Примечание
В первом примере общей частью может быть \([1]\), \([2]\), \([3]\) и \([2, 3]\).
Во втором и третьем примерах можно оставлять только общие части из \(1\) элемента.