Nonogram QR

A simple puzzle is a good way to clear your head.

In a nonogram, you are given the lengths of the runs of consecutive black cells in each row and column, in order, and you complete the picture from these clues. See the figures below.

Figure 1: An unfinished nonogram.

Figure 2: A finished nonogram.

The picture we will draw with nonograms is a QR code. Figure 3 in the notes contains 2,000 QR codes of the following form.

• Decoding a QR code yields a string of digits. Splitting this string on 9 yields a total of 2n strings. Each string encodes the clues given for the rows and columns of an n by n nonogram. The clues are given for the rows from top to bottom, then for the columns from left to right. The encoding rule for each string is as follows.

  • A clue of 0 is encoded as an empty string.

  • Otherwise, the one or more numbers in the clue are encoded in the following form.

    • If the given number x is at most 8, write x-1.
    • If the given number x is greater than 8, write 8 followed by x-9.

  • There is no separator between numbers, and the number of clues is always at most 16.

• Solving the given nonogram produces a QR code. Decoding this QR code yields the data of each QR code.

The data each QR code contains is one of the following two kinds.

• Indicator data. This is always a four-digit number. If the four digits are xxyy, then xx is a row number and yy is a column number, pointing to the QR code at that position. We write this QR code as (xx, yy). For example, (0, 0) is the QR code at the top left, and (0, 1) is the QR code to its right. Row and column numbers start at 0. When you encounter indicator data, move to the corresponding QR code and continue decoding.
• A flag. Anything that is not in the indicator data format is a flag. You must find this string and submit it.

Your task is to start from the QR code at the starting position and find the flag.

Also print the product of all indicator data encountered while finding the flag, modulo 469,762,049. Call this value checkprod.

For example, if you start at (1, 1) and find the flag by following (2, 2) and (3, 3), then checkprod is 0202 * 0303 = 61,206 modulo 469,762,049, which is 61,206. Note that (1, 1) is given at the start rather than found through indicator data, so it is not included.

A subtask number is given as input.

Print the flag on the first line.

Print checkprod on the second line.

Figure 3: A list of QR codes.