Magic Trick

Interview

Time limit1sMemory limit512 MB

Summary

Given a string of letters, decide whether swapping two cards (or doing nothing) can always be identified from the resulting arrangement.

Level: Easy3 of 10
Topics: String, Hash map, Greedy, Implementation
Solved: No attempts yet

Problem

You are performing a magic trick with a special deck of cards.

You lay the cards out in a row from left to right, face up. Each card has a lower-case letter on it. Two cards with the same letter are indistinguishable. You select an audience member to perform an operation on the cards. You will not see what operation they perform.

The audience member can do one of two things: they can select any two cards and swap them, or leave the cards untouched.

In order for the trick to succeed, you must correctly guess what the audience member did. Either you guess that the audience member did nothing, or you point at the two cards the audience member swapped.

Given a string that represents the initial arrangement of the cards, can you guarantee that you will always be able to guess the audience member's operation correctly, no matter what operation they perform?

Input

The input consists of a single line containing the string $s$ ( $1 \le |s| \le 50$ ), which represents the initial arrangement of the cards, in the order they appear in the row. The string contains only lower-case letters ('a' to 'z').

Output

Output a single line with $1$ if you can guarantee that you will always be able to guess the audience member's operation correctly, or $0$ otherwise.

Examples2

Example 1
Input
```
robust
```
Expected output
```
1
```
Example 2
Input
```
icpc
```
Expected output
```
0
```