#P18175. Counting Strings

Counting Strings

Counting Strings

给定一个长度为 nn 的字符串 ss,下标从 1 开始。

称非空字符串 tt 被 ss 提及,当且仅当存在整数 l,rl,r,使得

$$1\le l\le r\le n,\qquad\gcd(l,r)=1,\qquad s[l..r]=t.$$

其中 s[l..r]s[l..r] 是从第 ll 个字符到第 rr 个字符组成的连续子串。

求所有被提及的不同非空字符串的长度之和。

一个字符串只要有一次出现的两端下标互素就符合条件,即使它还在其他不互素的位置出现,也只计入一次。这里按字符串内容去重,不按出现位置计数。

输入格式

第一行一个整数 nn,满足 1≤n≤1000001\le n\le100000。

第二行一个长度恰为 nn 的字符串 ss,仅包含小写英文字母。

输出格式

输出一个整数,表示所求的长度之和。答案不取模,需要使用 64 位整数。

样例

输入:

4
abca

输出:

14

被提及的不同字符串为 a、ab、abc、abca、bc、ca,长度之和为 1+2+3+4+2+2=141+2+3+4+2+2=14。