问题描述

高桥君喜欢寻找隐藏的单词游戏。例如，在“じきゅうりょく”中隐藏了单词“きゅうり”。

现在，高桥君想要在长度为 $N$ 的字符串中寻找隐藏的单词。为了列举隐藏的候选单词，他决定首先计算这个字符串的“子字符串”的数量。

字符串 $S$ 的“子字符串”是指从字符串 $S$ 中选取某个区间而得到的字符串。例如，"すぬけ"的子字符串有"す"、"ぬ"、"け"、"すぬ"、"ぬけ"和"すぬけ"这6个。请注意，"すけ"或者"ぬす"等不是子字符串。

另外，已知字符串 $S$ 中不会出现重复的字符超过2次。因此，不会出现从不同位置提取的字符串相匹配的情况，例如在“しょうぼうしょ”中的“しょ”。

输入

输入以以下格式从标准输入中给出：

$N$

• 第一行包含一个整数 $N (1 \leq N \leq 1000)$，表示字符串的长度。

输出

输出长度为 $N$ 的字符串的“子字符串”的数量。输出末尾需要有换行符。

示例输入1

1

示例输出1

1

示例输入2

2

示例输出2

3

示例输入3

3

示例输出3

6

正如问题描述中给出的“すぬけ”的例子，有6个子字符串。

示例输入4

4

示例输出4

10