TopCoder

User's AC Ratio

94.7% (18/19)

Submission's AC Ratio

46.4% (26/56)

Tags

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

Sample Output 1

1305

Sample Input 2

80

Sample Output 2

15369130410361586318799902357993261087282487463803004967244454894616548299221460168232813990391296766308078214049799796880

Hints

Problem Source

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

Subtasks

No. Testdata Range Score
1 0 14
2 1 14
3 2 14
4 3 14
5 4 14
6 5 14
7 6 16

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3
3 1000 65536 262144 4
4 1000 65536 262144 5
5 1000 65536 262144 6
6 1000 65536 262144 7