import strutils, sequtils, algorithm proc popcount[T: int64|int](a: T): cint {.importc: "__builtin_popcountl", nodecl, nosideeffect.} const MOD = 1_000_000_00+7 proc powmod(b, e: int64): int64 = if e==0: result = 1 elif e==1: result = b elif e mod 2 == 0: result = powmod(b*b mod MOD, e div 2) else: result = b*powmod(b, e-1) mod MOD var fac: seq[int64] inv: seq[int64] proc make(n: int) = fac = @[1'i64] inv = @[1'i64] for i in 1..int: result = cmp(p[0], q[0]) if result==0: result = cmp(p[1], q[1]) var dp = newSeqWith(1 shl k, 1'i64) for bits in 0..<(1 shl k): var cur_y = 0 cur_x = 0 for p in abi: if (bits and (1 shl p[2]))>0: let dy = p[0]-cur_y dx = p[1]-cur_x dp[bits] = dp[bits]*cmb(dy+dx, dy) mod MOD cur_y = p[0] cur_x = p[1] dp[bits] = dp[bits]*cmb((h-cur_y)+(w-cur_x), h-cur_y) mod MOD for i in 0..