Diana 在某个奇怪的网站上买了一个长随机字符串生成器。她计划生成一个长度为 $n$ 的长字符串 $s$，然后将其连续子串用作其他奇怪网站的密码。

很快她发现，生成的长度为 $n$ 的字符串 $s$ 根本不是随机的，而是一个长度为 $k$ 的字符串 $p$ 重复多次后截断到长度 $n$ 得到的。即对于所有 $0 \le i \le n - 1$，都有 $s[i] = p[i \bmod k]$。

Diana 想知道她能从生成的字符串中得到多少种不同的密码。请帮助她计算字符串 $s$ 中不同非空子串的数量。

输入格式

第一行包含一个由 $k$ 个小写英文字母组成的字符串 $p$ ($1 \le k \le 1000$)。 第二行包含一个整数 $n$ ($k \le n \le 10^9$)。

输出格式

输出 $s$ 中不同非空子串的数量。

样例

样例输入 1

abba
7

样例输出 1

20

样例输入 2

a
42

样例输出 2

42

说明

在第一个样例中，生成的字符串是 abbaabb。它包含 20 个不同的非空子串：a, b, aa, ab, ba, bb, aab, abb, baa, bba, aabb, abba, baab, bbaa, abbaa, baabb, bbaab, abbaab, bbaabb, abbaabb。