License Plate 1

Interview

Time limit1sMemory limit512 MB

Summary

Given a format string of length at most 4 with c for letter and d for digit, count plates where no two adjacent characters are identical.

Level: Easy3 of 10
Topics: Combinatorics, Math, Implementation, Brute force
Solved: No attempts yet

Problem

Given the license plate format used in the city of Sangdo, count the number of possible license plates.

The digits allowed on a plate are 0, 1, 2, ..., 8, 9.
The letters allowed are a, b, c, d, ..., y, z.
A license plate format has at most 4 characters and is written as a string of c and d.
c marks a position holding a letter, and d marks a position holding a digit.
The same letter or digit must not appear twice in a row.

For example, if the format is "cd", then a1, d4, h5, k4 are possible. If the format is "dd", then 01, 10, 34, 69 are possible, but 00, 11, 55, 66 are not, because the same digit appears twice in a row.

Input

The first line gives the license plate format. The length of the format is at most 4, and it consists only of c and d.

Output

Print the number of possible license plates on the first line.

Examples3

Example 1
Input
```
dd
```
Expected output
```
90
```
Example 2
Input
```
cc
```
Expected output
```
650
```
Example 3
Input
```
dcdd
```
Expected output
```
23400
```