TopCoder

Thumb a

User's AC Ratio

90.0% (9/10)

Submission's AC Ratio

40.0% (14/35)

Description

傑倫與伊林非常喜歡上高中生物課,而生物老師孔智慧有一個「序列長度」問題,希望兩位同學幫忙計算。

孔老師觀察出昆蟲體內存有許多過去從未被發現的奇特結構序列,這些結構序列是由一組元素組成,而且每一個元素在每一個結構序列中最多僅會出現一次。

例如,當有 {A, B} 2 個不同組成元素時,則可以組成A、B、A-B、B-A等4 種結構序列,這4 種結構序列的長度總和為6。而當有 {A, B, C} 3 個不同組成元素時,則可以組成A、B、C、A-B、B-A、A-C、C-A、B-C、C-B、A-B-C,A-C-B、B-A-C、B-C-A、C-A-B、C-B-A 等15 種結構序列,而這15 種結構序列的長度總和為33。

由於預期陸續會有含新組成元素的結構序列被發現,孔老師因此希望傑倫與伊林幫忙計算看看當不同組成元素有n 個時,所有可能的不同結構序列長度總和為何?聰明的你(妳)請寫一個程式幫傑倫與伊林來回答這個問題。

Input Format

輸入一行只有一個正整數n (1 ≤ n ≤ 1000),代表不同組成元素。

Output Format

輸出一個整數,即所有可能結構序列的總長度。

Sample Input

輸入檔範例 1
5

輸入檔範例 2
80

Sample Output

輸出範例 1
1305

輸出範例 2
15369130410361586318799902357993261087282487463803004967244454894616548299221460168232813990391296766308078214049799796880

Hints

Problem Source

原TIOJ1477 / 96北市賽
建中校內培訓第五次模擬考試。
Problem Setter:hallogameboy、peter50216

Subtasks

For Testdata: 0 ~ 0, Score: 14
For Testdata: 1 ~ 1, Score: 14
For Testdata: 2 ~ 2, Score: 14
For Testdata: 3 ~ 3, Score: 14
For Testdata: 4 ~ 4, Score: 14
For Testdata: 5 ~ 5, Score: 14
For Testdata: 6 ~ 6, Score: 16
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 65536
1 1000 65536 65536
2 1000 65536 65536
3 1000 65536 65536
4 1000 65536 65536
5 1000 65536 65536
6 1000 65536 65536