You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

东东这次又约好了和朋友西西一起去玩剧本杀，在他准备出门赴约之际，妈妈又把他扣了下来（因为东东真的不怎么写作业），又把他的手机锁进了先前那个被七位数字密码锁锁住的箱子，不让东东出去。

可是，东东认为”与其写千篇一律的作业不如体验精彩纷呈的人生“，于是东东选择故技重施，打开密码箱，偷偷拿好手机，悄悄开溜。

可是东东尝试了先前的密码，发现妈妈已经将密码重置，东东仔细看了看密码箱上面的数字，还是不知道怎么推测出密码。于是他将目光投向了屏幕外的你。

聪明的你能否再帮东东破解这密码呢？

Description

给出俩组全由数字组成的字符串分别为 $A$ 、$B$。 令 $B$ 在 $A$ 中出现的次数为 $n$ ,而已知密码是 $e$ 的$n$ 次方的后$7$位数。（若不足七位，则在前面补$0$）

Format

Input

分别输入三个个数 $k$ , $m$ , $e$ ，其中 $k$ ,$m$ 表示接下来$A、B$俩个字符串所含元素的个数。 输入$A$字符串。 输入$B$字符串。(本题保证$B$一定为$A$的子串) （ 1<=m,k <= 1000000, 1<= e <= 1000）

Output

输出一行七位数的密码

Samples

5 2 33
33333
33

1185921

Limitation

8ms, 1024KiB for each test case.