逆元使ってn_C_k（を10**9+7で割った余り）を高速で求める、それはそうみたいな問題なんだけど、流石にテンプレをペタって貼り付けてn=10**5,kを1~10**5まで計算するのはしんどい（factorialの都合上）
n_C_k-1からn_C_nまでを一気に求める問題であれば、以下のような実装でまあなんとかなる。（色々杜撰なのは多めにみてね）
n = 10, k = 3なら、2C0, 3C1,...,9C7まで求めることになる
import math mod = 10**9+7 n,k = map(int,input().split()) #n_C_kのn,k a = math.factorial(k-1)%mod b = math.factorial(k-1)%mod c = 1 fact = [0]*(n-k+1) <s>#fact[j]は、n_C_(j+k-1)を表す</s> for i in range(k-1, n): if i == k-1: fact[0] = (a*pow(b*c, mod-2, mod))%mod else: a = a*i%mod #前の結果を再利用 c = c*(i-k+1)%mod #前の結果を再利用 fact[i-k+1] = (a*pow(b*c, mod-2, mod))%mod
i番目の鍵を使うか？でDPを行う。また、dp[i][j]について、iは「i番目までの鍵を見た（使った、使わないは無視）」、jは0から2**n-1までの値を取り、「二進数に直した時にビットが立っているところは、宝箱が空いている」とみなす。
例えば宝箱が3つあり、dp[3][6]であれば、「3番目の鍵まで見て、6→110、つまり箱1,2が空いている状態において、最小のコスト」が入るようにする。
dp[i][j]の遷移についてだが、まずi番目の鍵を使わないのであれば、開く箱はi-1番目の鍵を見た時と変化がないので、dp[i][j] = dp[i-1][j]となる。
i番目の鍵を使うのであれば、
dp[i][j|key[i][1]] = min(dp[i][j|key[i][1]],dp[i][j]+key[i][0]) #j|key[i][1]はor演算子を使っている。dp[i][j]までで開いている箱に、新たに鍵iを使った時に開く箱の状態に遷移した時、その鍵を使った方が最適かどうかを判断している。
という式で遷移が書ける。
最後にdp[m-1][2**n-1]を出力してあげればいい。（全部開けられないかの判断もここでする）
計算量は、鍵1~mを開けるか否かについてと、それについての0~2**n-1通りの箱の開き方があるのでO(m*(2**n))。
これ1000人も通してたってマ？
いもす法で前から見ていくのだが、区間全部の累積和を取るのではなく、「爆発の及ぶ範囲」の端と橋をプラス、マイナスしておいて、今見ているところの累積和s[i]がモンスターの体力h[i]以上であれば爆発せずに次へ、小さかったら足りない分だけ爆発させて右端（爆発の及ばないところ）にマイナスし、s[i+1]にs[i]で与えた分だけ増やす、という方式を繰り返す。
例で言えば、例えば爆発の及ぶ距離が左右に2、爆発のダメージを2として、
[1,2,5,9,11]
という位置にいるモンスターが
[10,12,8,14,9]
という体力を持っていたとしよう。
s = [0,0,0,0,0,0]（一つ多く取っておく。s[i]にi番目のモンスターに与える累積ダメージが後々入ることになる）
まず、最初に1にいるモンスターを左端と見て、ここを爆発させると位置2,5のモンスターも巻き添えを食らう。位置1にいるモンスターを倒すには10のダメージ（爆発5回）が必要で、これを表した状態は、
s = [10,0,0,-10,0,0]
となる。
次に進む前にs[1] += s[0] をするので、
s = [10,10,0,-10,0,0]
となる。
次に、距離2にいるモンスターに着目すると、現在与えられているダメージはs[1]=10で、倒しきるのにあとダメージが2（爆発が1）必要である。
ここを左端にして爆発させると、巻き添えを食らうモンスターは位置5のみ。（位置5はもう倒してるけどそれは放っておく）
というわけで、一回爆発させた状態を表現した配列sは、
s = [10,12,0,-12,0,0]
となる。
次に進む前にs[2] += s[1] をするので、
s = [10,12,12,-12,0,0]
となる。
次は距離5にいるモンスターだが、s[2] > h[2] = 8なのでもう爆発させる必要がない。
というわけで次に進むので、s[3] += s[2]をして
s = [10,12,12,0,0,0]
となる。（ここで、s[3]の累積ダメージが0になっていることに着目したい。s[3]を見るまでs[3]に入っていた値は累積ダメージを表現していなかったが、前から累積和をとることによって、s[3]を見る時にはうまく帳尻があう（正確なダメージが入る）事になる）
次に距離9にいるモンスターに注目する。現状、累積ダメージは0なので、7回の爆発（ダメージ14）が必要である。この爆発で、距離11にいるモンスターも巻き添えを食らうので、配列sは
s = [10,12,12,14,0,-14]
となる（配列の要素を一つ余分に取っておいたのがここでうまく作用する）
次に進むので、s[4] += s[3]をして、
s = [10,12,12,14,14,-14]
となる。
最後にs[4]だが、s[4] > h[4] = 9なのでもう爆発の必要はない。よってs[5] += s[4]をして、
s = [10,12,12,14,14,0]
となり、これで全部倒し切って終わり。O(N)で十分間に合う（ぶっちゃけ計算量的には前処理のソートの方が支配的）
