Computation with Stirling Numbers of the Second Kind

In 2016, Jiayuan was very excited after learning about the Stirling numbers of the second kind. Now she wants to compute the value of the following function:

$$f(n)=\sum_{i=0}^n \sum_{j=0}^i S(i,j)\times 2^j \times (j!) $$

Here, \(S(i,j)\) denotes the Stirling numbers of the second kind. They are defined recursively by the relation:

$$S(i,j)=j\times S(i-1,j)+S(i-1,j-1)\quad\text{for } 1\le j\le i-1, $$

with the boundary conditions:

$$S(i,i)=1\quad (i\ge 0) \quad\text{and}\quad S(i,0)=0\quad (i\ge 1). $$

Your task is to help Jiayuan compute \(f(n)\) given an integer \(n\).

inputFormat

The input consists of a single integer \(n\) on one line, where \(n\) is a non-negative integer.

outputFormat

Output a single integer representing the computed value of \(f(n)\).

sample

0

1