A - 隠れた言葉

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君は、隠れた言葉を探す遊びが好きです。例えば、「じきゅうりょく」の中には「きゅうり」という言葉が隠れています。

高橋君は今、長さ N の文字列の中に隠れた言葉を探そうとしています。隠れた言葉の候補を列挙するためにまず、この文字列の「部分文字列」の個数を計算してみることにしました。

文字列 S の「部分文字列」とは、文字列 S に含まれるある区間を取り出した文字列のことです。例えば、「すぬけ」の部分文字列は「す」「ぬ」「け」「すぬ」「ぬけ」「すぬけ」の 6 つです。「すけ」や「ぬす」などは部分文字列ではないことに注意してください。

また、文字列 S には同じ文字が 2 回以上現れないことが分かっています。そのため「しょうぼうしょ」における「しょ」のように、異なる場所から取り出した文字列が一致することはありません。


入力

入力は以下の形式で標準入力から与えられる。

N
  • 1 行目には、文字列の長さを表す整数 N (1 ≦ N ≦ 1000) が与えられる。

出力

長さ N の文字列の「部分文字列」の個数を 1 行に出力せよ。出力の末尾に改行を入れること。


入力例1

1

出力例1

1

入力例2

2

出力例2

3

入力例3

3

出力例3

6

問題文中で示した「すぬけ」の例の通り、6 つの部分文字列があります。


入力例4

4

出力例4

10