403535: GYM101191 H Spells

Rinswind the Wizard knows only one spell. And despite his best efforts, he has failed to learn more: new spells weren't staying in his head for long and were vanishing after 3+5 seconds. Because of that he needs to learn how to derive new spells from the one he already knows. Since the spell he knows is a powerful one, he thinks that this might be a good idea.

The spell may be represented as a string S that consists of lowercase latin letters. Rinswind is allowed to swap two adjacent characters while constructing the new spells. There is a condition that needs to be met in order for the spell to preserve its power: you can't swap characters at positions i и i + 1 if earlier there was a swap of characters at j и j + 1 and j > i. For example, abc can be transformed into abc, acb, bac and bca, but not into cab and cba.

The spell can be pretty long and because of that its description consists of blocks. Each block is represented as a string and a number which shows how many times the string must be repeated.

Rinswind is now busy with pronunciation practice, but he is interested in the possible number of spells he can master after perfecting his construction techniques. Lets help him do this. Don't forget about the fact that Rinswind is unable to learn the new spells and he can only construct them from the initial one.

First line has number N — amount of spell blocks (1 ≤ N ≤ 100).

In the next N lines spell blocks are described in the order they are located within the spell S_i K_i  — string and repeat amount (1 ≤ |S_i| ≤ 10⁴, 1 ≤ K_i ≤ 10⁶).

The only line must contain the number of potential spells modulo 10⁹ + 7.

3
a 1
ng 2
an 1

42