問題文
高桥喜欢玩寻找隐藏单词的游戏。例如,“黄瓜”一词隐藏在“jikyuryoku”中。
高桥君现在长高了 我正在尝试查找字符串 N 中的隐藏单词。为了枚举隐藏的候选单词,我决定首先计算该字符串中“子字符串”的数量。
文字列 S 的“子字符串”是一个字符串 S 中包含的某个区间中提取的字符串。例如,“Snuke”的子串是“su”、“nu”、“ke”、“sunu”、“nuke”、“snuke”。 6 一。请注意,“suke”和“nusu”等单词不是子字符串。
另外,字符串 S 具有相同的字符 众所周知,它出现的次数不会超过 2 次。因此,从不同位置提取的字符串,例如“shobosho”中的“sho”,永远不会匹配。
入力
输入是按以下格式从标准输入给出的。
N
- 1 行包含一个表示字符串长度的整数。 字符串 N (1 ≦ N ≦ 1000) 。 表示
出力
长度 小于或等于 N 中“子字符串”的数量 在 1 行输出。在输出末尾插入换行符。
入力例1
1
出力例1
1
入力例2
2
出力例2
3
入力例3
3
出力例3
6
如问题中“Snuke”的例子所示, 有6 子字符串。
入力例4
4
出力例4
10