Halloween has finally arrived and the ghosts on your street have decided to volunteer at your local haunted houses. Each of the ghosts (numbered from to ) will volunteer at **exactly one of the haunted houses** and perform their prepared routine. The ghost will perform **unique** moves in their routine, with the moves each being one of types of moves:

- spook
- hide
- creep
- float

Each move has an associated scare factor, for .

In addition, the ghosts are separated into groups based on the sum of the digits of their number. All ghosts who have the same sum of digits are in the same group. **In order to keep the group happy, at least half of the ghosts in that group must be assigned to the same haunted house.**

On Halloween night, each ghost will arrive at their assigned haunted house in the order of their number. They will ask the other ghosts inside the house if any of them are **currently** planning on performing any of the same moves as them in their routine. To avoid their routines being too similar, all of these ghosts that are currently inside the house (but not outside) will agree to remove that move from their routine.

Once all the ghosts have arrived, the haunted house will open, and the ghosts will perform their routines. Each move a ghost performs contributes the the scariness of the haunted house. The scariness of a haunted house is the sum of the scare factors of all moves performed by any ghost inside the house.

You will be asked questions. For the question, you want to determine the number of ways to assign ghosts to the haunted houses such that each group is happy, and the sum of the scariness of the houses is between and (inclusive). Since this number can be very large, please output it modulo . It may be helpful to know that is prime and .

#### Constraints

for

for

for

#### Input Specification

The first line of input contains integers, .

The next lines of input describe the moves in the ghost's routine. Each line begins with an integer , the number of **unique** moves in the ghosts routine. The next words on the line are the moves the ghost will perform in their routine. Each word will be one of `spook`

, `hide`

, `creep`

, or `float`

. **Each move will only appear once in a ghost's routine.**

The next line of input contains integers,

The next lines of input describe the questions. Each line contains integers, .

#### Output Specification

**This problem is graded with an identical checker. This includes whitespace characters. Ensure that every line of output is terminated with a \n character and that there are no trailing spaces.**

Output lines. On the line, output the number of ways, modulo , to assign ghosts to the haunted houses such that each group is happy, and the sum of the scariness of the houses is between and (inclusive). Two ways are considered different if there is at least one ghost that is assigned to a different house.

#### Sample Input

```
3 1
2 spook float
3 creep spook float
2 hide creep
10 5 7 8
19 41
```

#### Sample Output

`40`

#### Sample Explanation

There are ways to assign ghosts to houses such that the sum of the scare factors is , and ways such that the sum is .

## Comments