题目描述

Diana 买了一台“超长随机字符串生成器”。她原本打算生成一个长度为 $n$ 的长字符串 $s$，然后把它的连续子串当作其他网站的密码。

后来她发现，这个所谓的随机字符串其实一点也不随机：存在一个长度为 $k$ 的字符串 $p$，把 $p$ 无限重复后截取前 $n$ 个字符，就得到了 $s$。也就是说，对所有 $0\le i<n$，都有

Diana 想知道，她一共能够得到多少个不同的非空连续子串。

输入格式

第一行输入一个由小写英文字母组成的字符串 $p$，其长度为 $k$：

第二行输入一个整数 $n$：

输出格式

输出一个整数，表示字符串 $s$ 中不同的非空连续子串数量。

样例

样例 1

abba
7

20

样例 2

a
42

42

样例说明

在第一个样例中，生成的字符串为 abbaabb，其中共有 20 个不同的非空连续子串。