시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 512 MB | 5 | 5 | 5 | 100.000% |
You are a director of a very successful theatre. Above all, you like William Shakespeare, even despite his inclination for bloody endings. It was said about some of his plays – like “Hamlet” and “King Lear” – that if they had just one more act, it would be necessary to start murdering people from the first rows of the audience.
Right now, you are close to developing a grudge for Shakespeare for not including this final act. It is because of the 2k people that have just come to your theatre. These are k pairs of celebrities – football players, models, YouTube streamers – who seem not to fully grasp the idea of theatre plays. Each pair is very likely to start a heated argument during the play, disrupting the performance entirely. But there is a solution – it is up to you to assign seats to people, and if a pair is not given adjacent seats, fight is much less likely.
The auditorium consists of n rows with m seats in each one. Some places are already booked by “normal” viewers, whom you do not want to reseat. There are k pairs of celebrities, and to every celebrity you must assign a seat, such that no pair occupies two adjacent spots (we consider two seats adjacent only if they share a common side, i.e. one is next to or behind the other). To cheer yourself up, compute the total number of ways you can do it – it is usually a very large number, so it is enough to compute its remainder modulo 109 + 7. Two assignments are considered distinct if any celebrity is given a different seat. Please note that we distinguish all the celebrities (consider them not identical).
The first line of input contains the number of test cases z (1 ≤ z ≤ 100). The descriptions of the test cases follow.
The first line of each test case contains three positive integers n, m, k (1 ≤ n · m ≤ 144, 1 ≤ k ≤ mn/2) – the number of rows, seats in a row, and celebrity pairs. The next n lines describe the rows – each one is a string of characters ‘X
’ and ‘.
’, where ‘.
’ denotes a free seat, ‘X
’ – an occupied (unavailable) seats. You may assume that there are at least 2k free seats.
For each test case, output a single number – the number of possible assignments of seats to celebrities such that no pair is given adjacent seats, modulo 109 + 7.
2 2 2 2 .. .. 4 4 3 X.X. .... .X.. ...X
8 347040
In the first example, all ways of assigning seats are presented below (‘A
’ and ‘a
’ denote seats assigned to the first pair, ‘B
’ and ‘b
’ — to the second):
AB Ab ab aB BA bA ba Ba ba Ba BA bA ab aB AB Ab