Task DescriptionDiscussion (0)

On the first line of the standard input are given the integers N and M – the maximal value of a word (1 ≤ N ≤ 1,000,000,000) and the number of character pairs, for which Elly has defined a difference. All not mentioned pairs have distance equal to one. Each of the next M lines contains a triple L1 L2 F, meaning that the distance between letters а ≤ L1, L2 ≤ z is 1 ≤ F ≤ 5. The distance from L1 to L2 is the same as the distance from L2 to L1.

Print one sole integer on the standard output– the number of words, consisting of lowercase English letters, whose value is not greater than N. Since this number can be quite large, output the reminder of the number when divided by 1,000,000,007.

Notes:

In tests worth 50 points N will not be greater than 1,000,000.

Each pair of letters in the input will be given at most once.

Trivia:some of the words are: ”elleonora”,”entwine”,”aaaaaaaaaaaaaaaaaaaaa”.

Task :: Reading

Interesting fact about the human brain is that, when reading, it analyses the first and last letter of each word,taking all other not necessarily in the right order to construct the meaning. As a conesqunece, a senetnce whit amlost no corerct word can be raed easliy. ☺

Elly has noticed that shuffling certain letters gives even better result! For example the characters “l” and “i”, “a” and “o” are much similar, than, let’s say, “x” and “m”. She defines a scale from 1 to 5 of difference between letters, where similar ones have low value, and very different have high value. Equal letters have a value of one. In this manner each word can be given a value – the sum of all differences between adjacent letters.

Imagine she has defined the differences between “e” and “l” as 3, between “l” and “y” as 2, between “i” and “l” as 1. Then the word “elly” has value of 3 + 1 + 2 = 6 (remember, that equal letters have distance of 1). The word “lily” has value of 4 and “i” have value of zero =). Longer words are not necessarily with larger value than shorted – consider “lilii” (which is the Bulgarian plural of “lily”) – it has value of only 4, but “elle” (which means “she” in French) has a value of 7. However, each additional letter adds at least one to the value of the word.

Elleonora wants to construct a language that would be easily readable even with huge number of misplaced letters. She has decided to include all non-empty words with values less than or equal to N. Can you help her by finding how many are they?

Elly has noticed that shuffling certain letters gives even better result! For example the characters “l” and “i”, “a” and “o” are much similar, than, let’s say, “x” and “m”. She defines a scale from 1 to 5 of difference between letters, where similar ones have low value, and very different have high value. Equal letters have a value of one. In this manner each word can be given a value – the sum of all differences between adjacent letters.

Imagine she has defined the differences between “e” and “l” as 3, between “l” and “y” as 2, between “i” and “l” as 1. Then the word “elly” has value of 3 + 1 + 2 = 6 (remember, that equal letters have distance of 1). The word “lily” has value of 4 and “i” have value of zero =). Longer words are not necessarily with larger value than shorted – consider “lilii” (which is the Bulgarian plural of “lily”) – it has value of only 4, but “elle” (which means “she” in French) has a value of 7. However, each additional letter adds at least one to the value of the word.

Elleonora wants to construct a language that would be easily readable even with huge number of misplaced letters. She has decided to include all non-empty words with values less than or equal to N. Can you help her by finding how many are they?

**INPUT:**

On the first line of the standard input are given the integers N and M – the maximal value of a word (1 ≤ N ≤ 1,000,000,000) and the number of character pairs, for which Elly has defined a difference. All not mentioned pairs have distance equal to one. Each of the next M lines contains a triple L1 L2 F, meaning that the distance between letters а ≤ L1, L2 ≤ z is 1 ≤ F ≤ 5. The distance from L1 to L2 is the same as the distance from L2 to L1.

**OUTPUT:**

Print one sole integer on the standard output– the number of words, consisting of lowercase English letters, whose value is not greater than N. Since this number can be quite large, output the reminder of the number when divided by 1,000,000,007.

Notes:

In tests worth 50 points N will not be greater than 1,000,000.

Each pair of letters in the input will be given at most once.

Input:

Output:

**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

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

Output:

**470059518**

Trivia:some of the words are: ”elleonora”,”entwine”,”aaaaaaaaaaaaaaaaaaaaa”.

Submit Solution

Available Languages

Task info

Name: | Reading |

Time: | 2 sec. |

Memory: | 32 MB |

#Tests: | 10 |

AddedBy: | Gorgi... |

Source: | 9th NATIONAL AUTUMN TOURNAMENT IN INFORMATICS AND |

Task Ratings

Difficulty: | 5 (4 votes) |

Quality: | 3.8 (5 votes) |

Acceptance Rate

Recent Submissions

Fastest Solutions

User | Time |
---|---|

Seterplus | 4.188 s. |

lukatiger | 4.282 s. |

aashishsharma | 4.413 s. |

D.Ostojic | 4.422 s. |

nigo92 | 4.563 s. |

Amtrix | 5.077 s. |

dsabolic | 6.985 s. |

CodeBreaker | 7.698 s. |

vebgor | 10.477 s. |

Solved By