Column Permutation Addition

We are given three strings a, b, c each of length \( n \) (possibly with leading zeros). They are arranged in three rows and \( n \) columns as follows:

a
b
c

We can permute (i.e. rearrange) the \( n \) columns. After a permutation, let \( x, y, z \) be the integers obtained by reading each row from left to right. We require that:

[ x + y = z]

with the additional condition that none of the integers \( x, y, z \) has a leading zero (i.e. the leftmost column in each row must have a nonzero digit).

Output the number of distinct column arrangements (i.e. distinct as sequences of columns; note that if some columns are identical, swapping them does not count as a new arrangement) modulo \(10^9+7\).

inputFormat

The first line contains an integer \( n \) (the number of columns). The following three lines each contain a string of length \( n \) representing a, b, and c respectively.

outputFormat

Output a single integer: the number of valid distinct column arrangements modulo \(10^9+7\).

sample

1
1
2
3

1