Linguist
Marisya, unlike Stepan, studies at the linguistic faculty of RuNU and clearly isn't fond of mathematics or anything related to it. Like all her fellow students, she has a strong aversion to numbers where the absolute difference between any two consecutive digits exceeds 1 (such are the quirks of linguists).
Stepan urgently needs to identify all the numbers he can use without distressing Marisya. However, time is running short before their meeting, so at the very least, he needs to count the number of N-digit positive integers that he can safely use during their encounter.
Input
The input consists of a single line containing the integer N (1 ≤ N ≤ 20).
Output
Output a single line with the count of N-digit positive integers that Stepan can use without causing any distress to Marisya.