Problem Statement

    We have an undirected graph where each vertex is either black or white and has a mark, which is a non-negative integer. There are no edges that connect vertices of the same color. We are going to play a game with this graph. The rules are simple:
  1. White and black alternate turns. The first turn is white.
  2. During a white turn, we set the mark of each black vertex equal to the sum of the marks of all its neighbors. The marks of the white vertices remain unchanged.
  3. During a black turn, we set the mark of each white vertex equal to the sum of the marks of all its neighbors. The marks of the black vertices remain unchanged.
You are to find the marks of all vertices after N turns.



You are given a vector <string> adj where the j-th character of the i-th element is '1' (one) if there is an edge between vertices i and j, and '0' (zero) otherwise. You are given the coloring of the graph in the string colors, the i-th element of which is the color of the i-th vertex. 'W' denotes white and 'B' denotes black. The initial marks are given in the string marks, the i-th element of which is a digit representing the initial mark of the i-th vertex.



Return a vector <int> where the i-th element is the mark of the i-th vertex modulo 10^9+7 after N turns.

Definition

    
Class:GameOnAGraph
Method:getMarks
Parameters:vector <string>, string, string, int
Returns:vector <int>
Method signature:vector <int> getMarks(vector <string> adj, string colors, string marks, int N)
(be sure your method is public)
    

Notes

-If a vertex whose mark is being calculated has no neighbors, its mark becomes zero.

Constraints

-adj will contain between 1 and 50 elements, inclusive.
-Each element of adj will contain exactly n characters, where n is the number of elements in adj.
-colors and marks will each contain exactly n characters, where n is the number of elements in adj
-Each element of adj will contain only the characters '0' (zero) and '1' (one).
-adj will be symmetric, i.e., adj[i][j] = adj[j][i], for all possible i and j.
-adj[i][i] will be equal to '0', for all possible i.
-colors will contain only the characters 'W' and 'B'.
-There will be no edges that connect vertices of the same color. In other words, for all possible i and j, where colors[i] equals colors[j], adj[i][j] will be '0'.
-marks will contain only digits ('0'-'9').
-N will be between 1 and 10^9, inclusive.

Examples

0)
    
{"0110","1000","1000","0000"}
"WBBW"
"1000"
1
Returns: {1, 1, 1, 0 }
In this case there is only one turn, so both black vertices get their marks from the first white vertex. The marks of the white vertices remain unchanged.
1)
    
{"00000","00000","00000","00000","00000"}
"BBWWW"
"99999"
1
Returns: {0, 0, 9, 9, 9 }
There are no edges in this graph, so all black vertices get their marks nullified.
2)
    
{"01","10"}
"BW"
"56"
2
Returns: {6, 6 }
After the first turn, the black vertex will have the same mark as the white one. After that, both marks will always be equal to 6.
3)
    
{"010101","101010","010101","101010","010101","101010"}
"BWBWBW"
"012345"
10
Returns: {59049, 177147, 59049, 177147, 59049, 177147 }

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.