Para los azucareros del centro un número natural ~N~ es trinominal si cada dígito en él, excepto el primero y el último, son estrictamente menores que los dos dígitos adyacentes o estrictamente mayor que ellos. Por ejemplo, el número ~176934~ cumple dicha propiedad.

Escriba un programa que encuentre la cantidad de números trinomiales de ~N~ cifras.

Entrada

La primera línea de la entrada estándar contiene un único número entero, ~N (3 \leq N \leq 22)~.

Salida

En una línea de la salida estándar, el programa debe mostrar un número entero, la cantidad de números trinomiales de ~N~ dígitos.

Ejemplo de Entrada

7

Ejemplo de Salida

693129