假设有两个非空字符串 $A$ 和 $B$（$|A|, |B| \le 500$），它们由大写英文字母组成，以及两个整数 $n$ 和 $m$，满足 $1 \le n, m \le 10^{15}$。
令字符串 $A^n$ 为 $n$ 个字符串 $A$ 的拼接。令字符串 $B^m$ 为 $m$ 个字符串 $B$ 的拼接。你的任务是找到 $A^n$ 和 $B^m$ 的最长公共子序列的长度。
输入格式
第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 10^{15}$)。 第二行包含一个非空字符串 $A$，长度不超过 $500$。 第三行包含一个非空字符串 $B$，长度不超过 $500$。 两个字符串均由大写英文字母组成。
输出格式
输出一个整数：$A^n$ 和 $B^m$ 的最长公共子序列的长度。
样例
样例输入 1
10 10 AB BA
样例输出 1
19
样例输入 2
100000000 100000000 A AB
样例输出 2
100000000