Một mạch điện sử dụng tụ điện giống hệt nhau có cùng một giá trị ~C~. Các tụ điện có thể được mắc nối tiếp hoặc song song để tạo thành các đơn vị, và sau đó chúng có thể được mắc nối tiếp hoặc song song với các tụ điện khác hoặc các đơn vị khác để tạo thành đơn vị lớn hơn, và cứ như vậy cho đến khi có một mạch cuối cùng. Sử dụng thủ tục đơn giản với ~n~ tụ điện giống hệt nhau, chúng ta có thể làm cho các mạch có các tổng điện dung khác nhau. Ví dụ, với ~n = 3~, mỗi tụ có giá trị ~60\mu F~, chúng ta có thể có được ~7~ tổng giá trị điện dùng khác nhau.

Gọi ~D(n)~ là số lượng tổng giá trị điện dung khác nhau có thể có được khi sử dụng ~n~ tụ điện có giá trị bằng nhau và các thủ tục đơn giản mô tả ở trên.

Input

Số nguyên dương ~n \leq 18~

Output

Giá trị ~D(n)~

Sample Input 1

1

Sample Output 1

1

Sample Input 2

2

Sample Output 2

3

Sample Input 3

3

Sample Output 3

7

Note

Chú ý: khi mắc tự điện ~C_1, C_2, \dots~ song song, tổng điện dùng ~C_t = C_1 + C_2 + \dots~, trong đó khi mắc nối tiếp, tổng điện dùng được xác định bởi ~\frac{1}{C_T} = \frac{1}{C_1} + \frac{1}{C_2} + \dots~

Link đề bài gốc: Circuit