Chuỗi Fibonacci được định nghĩa như sau:

~F_1 = x~

~F_2 = y~

~F_i = F_{i-1} + F_{i-2}~

Trong đó ~x, y~ là hai ký tự được cho trước, phép toán cộng được hiểu là phép toán ghép chuỗi.

Ví dụ: ~x~ = 'A' và ~y~ ='B' thì khi đó ta có dãy gồm 6 chuỗi Fibonacci như sau:

1. ~F_1~ = 'A'
2. ~F_2~ = 'B'
3. ~F_3~ = 'BA'
4. ~F_4~ = 'BAB'
5. ~F_5~ = 'BABBA'
6. ~F_6~ = 'BABBABAB'

Cho biết hai ký tự ~x, y~ và số nguyên dương ~n~. Hãy in ra chuỗi Fibonacci thứ ~n~.

Đầu vào

• Dòng đầu tiên là hai ký tự ~x~ và ~y~ cách nhau 1 dấu cách.

• Dòng tiếp theo là số nguyên dương ~n~.

Đầu ra

• In ra chuỗi Fibonacci thứ ~n~.

Ví dụ: