using System; using static System.Console; using System.Linq; using System.Collections.Generic; class Program { static long NN => long.Parse(ReadLine()); static int[] NList => ReadLine().Split().Select(int.Parse).ToArray(); static string[] SList(long n) => Enumerable.Repeat(0, (int)n).Select(_ => ReadLine()).ToArray(); public static void Main() { Solve(); } static void Solve() { var c = NList; var (h, w, k, p) = (c[0] + 1, c[1] + 1, c[2], c[3]); var fr = SList(k); var map = new int[h, w]; for (var i = 0; i < h; ++i) for (var j = 0; j < w; ++j) map[i, j] = -1; for (var i = 0; i < k; ++i) { var s = fr[i].Split(); map[int.Parse(s[0]), int.Parse(s[1])] = i; } var bitmax = 1 << k; var ans = new HugeInt(6); var maxb = 0; for (var b = 0; b < bitmax; ++b) { if (Popcount(b) != p) continue; var dp = new HugeInt[h, w]; for (var i = 0; i < h; ++i) for (var j = 0; j < w; ++j) { dp[i, j] = new HugeInt(6); if (i == 0 && j == 0) dp[i, j] = HugeInt.Sum(dp[i, j], 1); if (map[i, j] >= 0 && ((b >> map[i, j]) & 1) == 0) continue; if (i > 0) dp[i, j] = HugeInt.Sum(dp[i, j], dp[i - 1, j]); if (j > 0) dp[i, j] = HugeInt.Sum(dp[i, j], dp[i, j - 1]); } if (dp[h - 1, w - 1].IsLarge(ans)) { ans = dp[h - 1, w - 1]; maxb = b; } } WriteLine(HugeInt.Mod(ans, 1_000_000_007)); for (var i = 0; i < k; ++i) if (((maxb >> i) & 1) == 1) WriteLine(fr[i].Split()[2]); } /// /// 10^27以上の大きい値どうしの計算をO(logN)で行う /// class HugeInt { static int div = 1 << 30; public List Digits; public HugeInt(int length) { Digits = new List(length); for (var i = 0; i < length; ++i) Digits.Add(0); } public bool IsLarge(HugeInt b) { for (var i = Digits.Count - 1; i >= 0; --i) { if (Digits[i] > b.Digits[i]) return true; if (Digits[i] < b.Digits[i]) return false; } return false; } public override string ToString() { var c = new List(Digits.Count); var flg = false; for (var i = Digits.Count - 1; i >= 0; --i) { if (Digits[i] > 0) flg = true; if (flg) c.Add((char)(Digits[i] + '0')); } if (c.Count == 0) c.Add('0'); return string.Concat(c); } public static HugeInt Sum(HugeInt a, int b) { var ans = new HugeInt(a.Digits.Count); var add = (long)b; for (var i = 0; i < a.Digits.Count; ++i) { var sum = a.Digits[i] + add; if (sum > div) { ans.Digits[i] = (int)(sum - div); add = 1; } else { ans.Digits[i] = (int)sum; add = 0; } } return ans; } // public static HugeInt Rem(HugeInt a, int b) // { // var ans = new HugeInt(a.Digits.Count); // for (var i = 0; i < a.Digits.Count; ++i) ans.Digits[i] = a.Digits[i]; // ans.Digits[0] -= b; // for (var i = 0; i < ans.Digits.Count; ++i) // { // if (ans.Digits[i] < 0) // { // var d = ans.Digits[i] / 10; // ans.Digits[i] += d * 10; // if (ans.Digits[i] < 0) // { // ++d; // ans.Digits[i] += 10; // } // ans.Digits[i + 1] -= d; // } // } // return ans; // } public static HugeInt Sum(HugeInt a, HugeInt b) { var ans = new HugeInt(a.Digits.Count); var add = 0; for (var i = 0; i < a.Digits.Count; ++i) { var sum = (long)a.Digits[i] + b.Digits[i] + add; if (sum > div) { ans.Digits[i] = (int)(sum - div); add = 1; } else { ans.Digits[i] = (int)sum; add = 0; } } return ans; } public static HugeInt Div(HugeInt a, int d) { var ans = new HugeInt(a.Digits.Count); var rem = 0L; for (var i = a.Digits.Count - 1; i >= 0; --i) { rem = rem * div + a.Digits[i]; ans.Digits[i] = (int)(rem / d); rem = rem % d; } return ans; } public static long Mod(HugeInt a, long m) { var ans = 0L; for (var i = a.Digits.Count - 1; i >= 0; --i) { ans = (ans * div + a.Digits[i]) % m; } return ans; } } static int Popcount(long n) { var c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555); c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333); c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f); c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff); c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff); c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff); return (int)c; } }