public class GooseInZooDivTwo {
public int count(string[] field, int dist) {
int w = field[0].Length;
int h = field.Length;
int mod = 1000000007;
var points =
from i in Enumerable.Range(0, h)
from j in Enumerable.Range(0, w)
where field[i][j] == 'v'
select new { r = i, c = j, id = i * w + j };
DisjointSet set = new DisjointSet(w * h);
int groupNum = points.Count();
if (groupNum == 0) return 0;
foreach (var p1 in points) {
foreach (var p2 in points) {
int d = Math.Abs(p1.c - p2.c) + Math.Abs(p1.r - p2.r);
if (d <= dist) {
if (!set.isSameSet(p1.id, p2.id)) {
set.unionSet(p1.id, p2.id);
groupNum--;
}
}
}
}
int ans = 1;
for (int i = 0; i < groupNum; i++) {
ans = (ans * 2) % mod;
}
return (ans + mod - 1) % mod;
}
}