დაწერეთ პროგრამა, რომელიც დაადგენს, თუ რამდენი N სიგრძის ისეთი სტრინგის შედგენა შეიძლება, რომ სტრინგი შედგებოდეს მხოლოდ 'a', 'b' და 'c' სიმბოლოებისაგან და ამასთანავე არ შეიცავდეს "ab" ქვესტრინგს.

შესატანი მონაცემები: ერთი მთელი რიცხვი N (1<=N<=25), რომელიც აღნიშნავს სტრინგის სიგრძეს.

გამოსატანი მონაცემები: ერთი მთელი რიცხვი - შესაბამისი სტრინგების რაოდენობა.

მაგალითები

შესატანი მონაცემები
2
                  დაკოპირება

გამოსატანი მონაცემები
8
                  დაკოპირება

შენიშვნა

განმარტება: შესაძლო 8 ვარიანტი 2 სიგრძის სტრინგისთვის - aa, bb, cc, ba, bc, ca, cb, ac.