Matej's LED Substitution Board Operation Sequences

Matej introduces his innovative design in the football industry by applying it to the substitution board. The board is composed of m five‐segment LED displays. Each display shows a digit (from 0 to 9) according to a fixed five‐segment pattern. Initially the board shows a valid m-digit number x (with each digit encoded in its LED pattern).

Matej will perform n operations. In each operation he chooses one of the displays and toggles exactly one of its segments; that is, he either turns a segment on (if it was off) or off (if it was on). (Two operation sequences are considered different if at some operation a different display is chosen or if the board state changes differently.)

However, a restriction is imposed: after every k operations the board’s state (i.e. the combination of all m displays) must form a valid number – in other words, each display must show one of the ten allowed LED patterns.

After the n operations are completed, if the final board state is valid (each display shows a proper digit) Matej wants to know, for each valid final state, exactly how many distinct operation sequences (obeying all the restrictions) can lead to that final state.

Note:

• The LED representations (of exactly five segments) for the digits 0 to 9 are fixed. Only these 10 patterns are considered valid.
• Although intermediate states (between checkpoints) may be invalid, at every checkpoint (i.e. after every k operations) and at the end the board must display a valid number.
• Two sequences are counted as different if at some operation they choose a different LED display to toggle or produce a different intermediate board state.

inputFormat

The input consists of two lines.

The first line contains three integers m, n and k:

• m (1 ≤ m ≤ 3) is the number of LED displays.
• n (n ≥ 0) is the total number of operations.
• k (k ≥ 1) is the frequency with which the board must display a valid number (i.e. after every k operations).

The second line contains a string of m digits (possibly with leading zeros) representing the initial board number x.

outputFormat

For each valid final board state (an m-digit number, with possible leading zeros), output a line containing the state and the number of distinct operation sequences that yield it. The final states should be listed in increasing order.

sample

2 2 1
12

00 1
01 1
02 1
03 1
04 1
05 1
06 1
07 1
08 1
09 1
10 1
11 1
12 1
13 1
14 1
15 1
16 1
17 1
18 1
19 1
20 1
21 1
22 1
23 1
24 1
25 1
26 1
27 1
28 1
29 1
30 1
31 1
32 1
33 1
34 1
35 1
36 1
37 1
38 1
39 1
40 1
41 1
42 1
43 1
44 1
45 1
46 1
47 1
48 1
49 1
... (continues for all 100 states)