There is a binary string of length stored on disk .
Then, there are operations. In the -th operation, a disk is chosen, and the string on that disk is copied to disk , producing . However, during the copying process, up to bits may be flipped (i.e., errors occur in at most positions).
You are given all the final binary strings , each of length . Your task is to determine how many possible sequences could result in this final configuration.
Since the answer can be large, you only need to find the answer modulo .
输入格式
The first line of the input contains three integers , , (, , ), described in the statement. It is guaranteed that is a multiple of .
Each of the next lines contains a hexadecimal string of length . Each character of is one of - or -, where , , , .
Each bit in the hexadecimal representation corresponds to consecutive bits in the binary string . Specifically, for each bit , it can be proved that there exists a unique tuple satisfying and . Bits in the binary string satisfy .
输出格式
Print an integer — the number of valid sequences modulo .
