Define S is a set {1,2,3,4...k}.

Define function

Define the cost of f(S) is the minimum call times of f() when you get it.

        If we have called f(S) before , we can cost 0 to get f(S) directly after that.

Please calculate the cost of f(S)  . (mod 10⁹+7)

For first test case ,the cost of f({1,2}) is 5
f({1,2}) = f(Ø) + f({1}) + f({2})
f({2}) = f{Ø}
f({1}) = f{Ø}
so the cost of f({1,2}) is 5

NYOJ