Интересен факт за човешкия мозък е, че при четене той анализира първата и последната буква на всяка дума, а всички останали просто взима (не задължително в правилен ред) за да конструира значението. Слтедсвие на твоа е, че доста рзабръкани изерчеиня и думи моагт да се чеатт срвантиелно ленсо =)

Ели забеляза, че при разбъркването на определени букви се получава дори по-добър ефект. Например буквите 'и' и 'н' или 'ъ' и 'ь' са доста по-сходни за мозъка, от, да кажем, 'ж' и 'а'. Тя дефинира скала от 1 до 5 на "разлика" между буквите, като еднакви букви имат фактор 1, подобни букви имат отново сравнително малък, а много различни букви имат голям фактор. Така всяка дума може да бъде оценена с някаква стойност – това е сумата от разликите между съседни букви.

Нека, например, тя е дефинирала разликата между 'и' и 'н' да е 2, между 'е' и 'л' да е 4, 'л', и 'и' да е 3, между 'е' и 'н' да е 5 и между 'я' и 'и' да е отново 5. Така думите "а" и "и" ще имат сума нула, "ели" ще има 4 + 3 = 7, "лени" ще бъде с 4 + 5 + 2 = 11, а "лилия" ще е 14. По-дългите думи не задължително са с по-голяма сума от по-къси (примерно "ниниии" ще е с едва 8), но въпреки всичко всяка следваща буква добавя някаква тежест.

Елеонора иска да построи език, който би бил лесно четим дори при много разместени букви. Тя е решила в езика да влязат всички непразни думи, чиито суми са по-малки или равни на N. Можете ли да намерите колко на брой са те? На първия ред на стандартния вход са зададени целите числа N и М – съответно сумата, за която се пита Ели, и броят двойки букви, за които тя е дефинирала конкретен фактор. Всички двойки, които не са изрично дадени, са с фактор 1. Следващите M реда съдържат по една тройка L₁ L₂ F, обозначаваща, че между буквите L₁ и L₂, а както и между L₂ и L₁, разликата е F. Всички букви във входа са главни букви от английската азбука. На стандартния изход изведете едно число – броя думи, съставени от малки латински букви, със сума по-малка или равна на N при тази скала. Тъй като този брой може да е много голям го изведете по модул 1,000,000,007.

• 1 ≤ N ≤ 1,000,000,000
• 1 ≤ M ≤ 325
• 1 ≤ F ≤ 5
• Всяка двойка букви във входа ще бъде дадена най-много веднъж.

Примерен Вход	Примерен Изход
20 10 E L 3 E O 1 O N 2 O R 4 R A 4 I N 5 E N 2 N T 3 T W 3 W I 5	470059518