Counting Nested Subset Triangles

Given a set ( S = {1, 2, \dots, n} ) and an integer ( k ), we want to select ( \frac{1}{2}k(k+1) ) subsets of ( S ), denoted by ( A_{i,j} ) for ( 1 \le j \le i \le k ), and arrange them in a triangle as follows:

[ \begin{matrix} A_{1,1}\ A_{2,1} & A_{2,2}\ A_{3,1} & A_{3,2} & A_{3,3}\ \vdots & \vdots & \vdots & \ddots\ A_{k,1} & A_{k,2} & A_{k,3} & \cdots & A_{k,k} \end{matrix} ]

In addition, these subsets must satisfy the following nesting conditions:

[ A_{i,j} \subseteq A_{i,j-1} \quad \text{and} \quad A_{i,j} \subseteq A_{i-1,j} ]

for all valid ( i ) and ( j ) (with the natural interpretation that conditions for indices out of range are ignored). Two selections of subsets

( A = { A_{1,1}, A_{2,1}, \dots, A_{k,k} } \quad \text{and} \quad B = { B_{1,1}, B_{2,1}, \dots, B_{k,k} } )

are considered different if there exists any ( i, j ) such that ( A_{i,j} \neq B_{i,j} ).

It can be shown that for each element ( x \in S ), its membership in the subsets is independent of other elements, and due to the constraints imposed by the triangle structure, the choices per element are equivalent to selecting a binary sequence ( (p_1, p_2, \ldots, p_k) ) such that ( p_1 \in {0,1} ) (since row 1 has only one element) and for ( i \ge 2 ) we have ( p_i \in {0,1} ) with ( p_i \le p_{i-1} ). There are exactly ( k+1 ) such valid sequences (one for each possible number of leading ones, from 0 to ( k )).

Thus, for each element in ( S ) there are ( k+1 ) independent choices, and the total number of ways to select the subsets is

[ \text{Answer} = (k+1)^n \pmod{1000000007}. ]

inputFormat

The input consists of a single line containing two integers n and k (\(1 \le n, k \le 10^9\)).

outputFormat

Output a single integer, the value of \((k+1)^n\) modulo \(1000000007\).

sample

2 1

4