License Plate 2

Interview

Time limit1sMemory limit512 MB

Summary

Count strings matching a pattern of letter and digit slots, where no two adjacent characters are equal, modulo 1,000,000,009.

Level: Easy3 of 10
Topics: Dynamic programming, Math, Combinatorics, Implementation
Solved: No attempts yet

Problem

Given the format of a license plate in the city of Sangdo, find the number of possible license plates.

The digits that can be used on a plate are 0, 1, 2, ..., 8, 9.
The letters that can be used are a, b, c, d, ..., y, z.
The format of a license plate is at most 1,000,000 characters long and can be represented as a string of c and d.
c is a position for a letter, and d is a position for 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, and k4 are possible. If the format is "dd", then 01, 10, 34, and 69 are possible, but 00, 11, 55, and 66 are not, because the same digit appears twice in a row.

Input

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

Output

Print the number of possible license plates modulo 1,000,000,009 on the first line.

Examples4

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