不同子串个数

题目背景

因为NOI被虐傻了,蒟蒻的YJQ准备来学习一下字符串,于是它碰到了这样一道题:

题目描述

给你一个长为N的字符串,求不同的子串的个数 我们定义两个子串不同,当且仅当有这两个子串长度不一样 或者长度一样且有任意一位不一样。 子串的定义:原字符串中连续的一段字符组成的字符串

输入输出格式

输入格式


第一行一个整数N 接下来一行N个字符表示给出的字符串

输出格式


一行一个整数,表示不一样的子串个数

输入输出样例

输入样例 #1

5
aabaa

输出样例 #1

11

输入样例 #2

3
aba

输出样例 #2

5

说明

请使用64位整数来进行输出 (具体来说,C++和C选手请使用long long 类型,pascal选手请使用Int64) 由于输入文件过大,请使用 高效的读入方法(具体的,c++和c选手请不要使用cin,pascal选手不需要管) 对于30%的数据,$N\le 1000$ 对于100%的数据,$N\le 10^5$