Cho tập $S={1,2,\dots,n}$ gồm $n$ phần tử và số nguyên $k$ . Bây giờ cần chọn từ $S$ một số tập con $A_{i,j}$ ( $A\subseteq S$ , $1\le j\le i\le k$ ) rồi xếp thành hình tam giác cạnh $k$ như hình dưới đây (do đó tổng cộng chọn ra $\dfrac{1}{2}k(k+1)$ tập con).

Ngoài ra, các tập con được chọn phải thỏa mãn:

$A_{i,j}\subseteq A_{i,j-1}$ và $A_{i,j}\subseteq A_{i-1,j}$ .

Với hai phương án chọn:

• Phương án $A={A_{1,1},A_{2,1},\dots,A_{k,k}}$

• Phương án $B={B_{1,1},B_{2,1},\dots,B_{k,k}}$

chỉ cần tồn tại chỉ số $i,j$ thỏa mãn $A_{i,j}\neq B_{i,j}$ thì phương án $A$ và phương án $B$ được coi là hai phương án khác nhau.

Hỏi có bao nhiêu cách chọn khác nhau, đáp án lấy modulo $1,000,000,007$ .

Dữ liệu vào

Đầu vào gồm một dòng chứa hai số nguyên $n$ và $k$ .

Trong đó $1\le n,k\le 10^9$ .

Dữ liệu ra

In ra một dòng chứa một số nguyên là số phương án modulo $1,000,000,007$ .

Ví dụ

Input

2 2

Output

16