The life of a squirrel is a mysterious one. A typical squirrel experiences exactly ~E~ events in their lifetime. Recently, scientists have discovered that there are ~N~ different types of events and have categorized them from ~1~ to ~N~. Each event can lead directly to several different types of events. For example, hunting for acorns could potentially lead to getting chased by a dog.

Unfortunately, not every squirrel will live a happy life. Scientists have devised the following conditions which determine the happiness of a squirrel:

• A squirrel must find at least one good shelter, which scientists have defined as an event of type ~2~.
• A squirrel must find at least one partner, which is defined as an event of type ~3~.
• A squirrel must have access to exactly ~K~ supplies of acorns. Scientists have defined the event of finding ~1~ supply of acorns as an event of type ~4~. This means that a squirrel must encounter an event of type ~4~ exactly ~K~ times in their lifetime to become happy.

The squirrel must fulfill all three conditions in order to live a happy life, and the order in which the conditions are satisfied does not matter. The life of a squirrel always starts with its birth and ends with its death. These events are described as type ~1~ and ~N~ respectively.

Using the required conditions for a happy squirrel life, how many distinct ways can a squirrel end up living a happy life? Two lives are considered to be different if there is at least one event in the ~E~ events where there are two different types of events happening at a specific moment (all events have the same duration). Since the answer could get very large, output the answer modulo ~998\,244\,353~.

Constraints

For this problem, you will NOT be required to pass all the samples in order to receive points. In addition, you must pass all previous subtasks to earn points for a specific subtask.

For all subtasks:

~5 \le N \le 45~
~5 \le E \le 10^9~
~0 \le K \le 8~
Only input where no events will lead directly to event type ~1~, and no events are directly led from event type ~N~ is allowed.

Subtask 1 [6%]

~5 \le N \le 9~
~5 \le E \le 9~
~K = 0~

Subtask 2 [17%]

~5 \le E \le 100~
~K = 0~

Subtask 3 [14%]

~5 \le E \le 100~
~0 \le K \le 1~

Subtask 4 [19%]

~0 \le K \le 2~

Subtask 5 [21%]

~0 \le K \le 5~

Subtask 6 [23%]

No additional constraints.

Input Specification

The first line of input contains ~3~ integers, ~N~, ~E~, and ~K~, representing the number of types of events, the number of events in a lifetime, and the number of supplies a squirrel needs.

The next ~N~ lines each contain a string of ~N~ characters. Each character is either 0 or 1. The ~j^{th}~ character on the ~i^{th}~ line describes the link from the ~i^{th}~ to the ~j^{th}~ event type. A 0 indicates that the ~i^{th}~ event type will never lead to the ~j^{th}~ event type, and a 1 indicates that the ~i^{th}~ event type can directly lead to the ~j^{th}~ event type.

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, on a single line, the total number of distinct ways a squirrel can live a happy life, modulo ~998\,244\,353~.

Sample Input 1

5 5 0
01100
00110
01011
00001
00000

Sample Output 1

1

Sample Explanation 1

There is only one way where a squirrel can live a happy life:

• The squirrel is born (event type ~1~), finds a partner (event type ~3~), finds a shelter (event type ~2~), finds another partner (event type ~3~), and finally dies (event type ~5~).

Note that any squirrels that find a supply of acorn will never live a happy life.

Sample Input 2

5 7 2
01000
00110
01011
00101
00000

Sample Output 2

3

Sample Explanation 2

There are three possible ways a squirrel can live a happy life:

• The squirrel is born (event type ~1~), finds a shelter (event type ~2~), finds a partner (event type ~3~), finds its first supply of acorn (event type ~4~), finds another partner (event type ~3~), finds its second supply of acorn (event type ~4~), and finally dies (event type ~5~).
  
• The squirrel is born (event type ~1~), finds a shelter (event type ~2~), finds its first supply of acorn (event type ~4~), finds a partner (event type ~3~), finds another shelter (event type ~2~), finds its second supply of acorn (event type ~4~), and finally dies (event type ~5~).
  
• The squirrel is born (event type ~1~), finds a shelter (event type ~2~), finds its first supply of acorn (event type ~4~), finds a partner (event type ~3~), finds its second supply of acorn (event type ~4~), finds another partner (event type ~3~), and finally dies (event type ~5~).