სამსიმბოლოიანი სტრიქონი

დროის ლიმიტი: 1 წმ

მეხსიერების ლიმიტი: 64 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout


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

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

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




მაგალითები

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

შენიშვნა

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