You are given a string s and a positive integer k. Form the string t by joining k copies of s together. Determine the number of substrings of t that are equal to 'segsi'.

Input

Your first line will contain s, the length of s is less than or equal to 100,000.

Your second line will contain k, (k <= 1,000,000,000).

Output

A single integer representing the number of substrings which are equal to 'segsi'.

Examples

Input 1
siseg
10

Output 1
9

Input 2
segsi
10

Output 2
10