Goão and Stairs
By João Guilherme Madeira Araújo, Noic 
Brazil
By João Guilherme Madeira Araújo, Noic Brazil
Goão Juilherme is a student at Educational Organization Farias Brito. Since he is often missing classes, his supervisor Parcelo Mena asks him constantly to go to his office to scold him. Farias Brito is a quite eldritch school, it has far more stairs than floors, and some stairs go directly from a floor to another many levels above. Goão doesn't like changes, so he decides he wants to use only the same route to get to Parcelo's office, however he doesn't want to do the same thing everyday. Goão then resolves he will walk up the stairs in different ways, sometimes he will jump two steps and then go up only one or he can walk up one step and jump two and so on. Juilherme now needs your help to determine the route that he can use the highest amount of times before he has to repeat the way he walks up a stair. Since he has a finite memory, he only cares about the amount modulo 109 + 9.
Note: To walk up a stair, the sum of the sizes of Goão's jumps must be equal to the amount of steps in the stair.
The input begins with three integers n (n ≤ 10000), m (m ≤ 100000) and k (k ≤ 1000), respectively the number of floors, the number of stairs and the number of Goão's different jump sizes. The following line contain k numbers, Juilherme's jumps heights. The last m lines contain three integers, a, b and c (0 ≤ a ≠ b ≤ n - 1, 1 ≤ c ≤ 1000), describing that a stair connects floors a and b and has c steps, Juilherme always starts at floor 0 and Mena's office is at floor n - 1.
Output the number of times Goão can use the desired route mod 109 + 9.
| Input Sample | Output Sample |
|
8 9 2 |
3 |