斐波那契字符串

题目

描述

现定义“斐波那契字符串”：S[n]=S[n-1]+S[n-2]( n >= 3 ，+为连接两个字符串，例如"as"+"sd"的值为"assd")
若S[n]的长度大于m，则忽略除了首尾的所有字符，讲S[n]缩成一个长度为2的仅保留首尾字符的字符串。若给出n( 1 <= n < 1000)与m( 2 <= m < 1000),求S[n]。

输入

输入仅包含两行，第一行包含两个 空格分隔的整数，n( 1 <= n < 1000)和m( 2 <= m < 1000)
第二行包含两个由空格分开且不包含空格的字符串S[1]和S[2]。

输出

仅有一行输出，包含一个字符串S[n]。

样例输入

5 4
a b

样例输出

ab