【CZYZOI 2017.04.16 B】 刷漆

内存限制: 128 MiB 时间限制: 1000 ms
标准输入输出

题目描述

Czy做完了所有的回答出了所有的询问,结果是,他因为脑力消耗过大而变得更虚了:)。帮助Czy恢复身材的艰巨任务落到了你的肩上。

正巧,你的花园里有一个由 NN 块排成一条直线的木板组成的栅栏,木板从左到右依次标号 11NN 。这 NN 块木板中,有 MM 块木板前面放着一桶油漆。油漆有不同的颜色,每种颜色可以由一个大写字母表示( AAZZ )。而你要求Czy用他的油漆刷子给栅栏刷上油漆。

已知Czy会选择一个前方放有油漆桶的木板开始他的任务。刷子蘸上油漆后,他开始随机地沿着栅栏走,他不会走出栅栏的范围。随机地走表示Czy会沿着他选择的方向一直走,然后随机在任何时候改变方向。沿着栅栏走只有两个方向,向前和向后。

你发现Czy刷油漆的过程总是符合下列规则:

每个油漆桶里装着无限多的油漆;

刷子上每次只有一种颜色的油漆,每次蘸油漆都会完全替换刷子上的油漆颜色;

当Czy走到一个油漆桶前,他会首先用刷子蘸这个油漆桶里的油漆;

Czy每走过一个木板都会将这个木板刷成当前刷子上的油漆颜色。

已知木板可以被多次刷上油漆,每次都会完全覆盖之前的颜色。当所有木板都被刷上了油漆的时候,Czy才能停下来(当然他也可以继续刷到他想停下来为止)。你看着Czy在栅栏前来回舞动,突然想知道Czy停下来的时候栅栏有多少种可能的不同油漆方案。定义当至少有一块木板颜色不同时,两种油漆方案被视为是不同的。

请你输出不同的油漆方案数对 109+910^9+9 取模的值。

输入格式

输入的第一行包含两个整数 NNMM

接下来 MM 行,每行两个整数 xxyy ,表示第 yy 块木板前面有一个装着颜色为 xx 的油漆的油漆桶。

输出格式

输出一行,包含一个整数,表示不同的油漆方案数对 109+910^9 + 9 取模的结果。

样例

输入样例

6 2
A 2
B 6

输出样例

4

数据范围与提示

对于 30%30\% 的数据,1MN1001 \le M \le N \le 100

对于 100%100\% 的数据, 1MN1000001 \le M \le N \le 100000

xxAAZZ 之间的大写字母;1yN1 \le y \le N