Після посадки дерев садівнику потрібно їх пофарбувати. У його розпорядженні є фарба трьох кольорів: біла, синя і помаранчева. Скількома способами він може пофарбувати $N$ дерев, якщо ніякі два однакові кольори не можуть бути поруч?

Вхідні дані

Кількість дерев $N$$(1 ≤ N ≤ 50)$.

Вихідні дані

Кількість способів фарбування.