Problem Description

Given a string $ S $ consisting of lowercase English letters.

A string $ T $ consisting of lowercase English letters or . with a length between 1 and 3 (inclusive) is said to match $ S $ if it satisfies the following condition:

• Let the length of $ T $ be $ K $. There exists a contiguous substring of $ S $ of length $ K $ such that by replacing each . in $ T $ with any lowercase English letter, it matches this substring of $ S $.

Find the number of strings consisting of lowercase English letters or . with a length between 1 and 3 (inclusive) that match $ S $.

Input Format

The input is given from the standard input in the following format:

$ S $

Output Format

Output the number of strings consisting of lowercase English letters or . with a length between 1 and 3 (inclusive) that match $ S $.

Sample Input and Output

Sample Input #1

ab

Sample Output #1

7

Sample Input #2

aa

Sample Output #2

6

Sample Input #3

aabbaabb

Sample Output #3

33

Notes/Hints

Constraints

• $1 \leq |S| \leq 100$
• $ S $ consists of lowercase English letters

Sample Explanation 1

The strings that match $ S $ are as follows: a, b, ., .., .b, a., ab, totaling 7 possibilities. - a matches the first character of $ S $. - b matches the second character of $ S $. - . can be replaced with a to match the first character of $ S $. - .. can be replaced with ab to match the first two characters of $ S $. - .b can be replaced with ab to match the first two characters of $ S $. - a. can be replaced with ab to match the first two characters of $ S $. - ab matches the first two characters of $ S $.

Sample Explanation 2

The strings that match $ S $ are a, ., .., .a, a., aa, totaling 6 possibilities.

见题面 Input 部分

见题面 Output 部分