Subset Complexity Sum

You are given N line segments on a real number line. The i-th segment covers all points from l_i to r_i (inclusive). For any subset of these segments, define its union as the set of all points covered by at least one segment in the subset. The complexity of a subset is defined as the K-th power of the number of connected components in the union. Formally, if a subset yields c connected components then its complexity is \[ \text{complexity} = c^{K}. \]

Your task is to compute the sum of the complexities for all 2^N subsets of the given segments (including the empty subset). Note that the union of an empty subset is empty and its complexity is considered to be 0 (you may assume K \ge 1 so that 0K=0).

Since the answer can be very large, output it modulo \(10^9+7\).

inputFormat

The first line contains two integers N and K (1 \le N \le 15, K \ge 1), the number of segments and the exponent respectively. Each of the next N lines contains two integers l_i and r_i representing the endpoints of the i-th segment (l_i \le r_i).

outputFormat

Output a single integer: the sum of complexities of all subsets modulo \(10^9+7\).

sample

2 2
1 3
2 4

3