No.1181 Product Sum for All Subsets
タグ : / 解いたユーザー数 153
作問者 :
PCTprobability
/ テスター :
leafirby
問題文
(21:24 問題文を更新しました.)
$1$以上$K$以下の整数からなる要素数$N$の数列$S$を考えます．
そのような数列$S$と，集合$\{1,2,...N\}$の真部分集合$T$の組み合わせとして考えられるものは$K^N \times (2^N-1)$通りありますが，そのすべてに対する$\displaystyle \prod_{i \in T}S_i$の和を求めてください．
ただし，答えが非常に大きくなる場合があるので答えを$10^9+7$で割ったあまりを出力してください．
また，空集合の全要素の積は$1$とします．
入力
$N\ K$
$1 \le N \le 2×10^5$
$1 \le K \le 10^{18}$
入力は全て整数
出力
最後に改行してください。
サンプル
サンプル1
入力
2 2
出力
16
便箋上，$G$を，$S_i({i\in T})$からなる集合とします．
$S=\{1,1\}$のとき，$G$として考えられるものは，$\{1\},\{1\},\{\}$の$3$つがあり，それぞれ全要素の積は$1,1,1$です．
$S=\{1,2\}$のとき，$G$として考えられるものは，$\{1\},\{2\},\{\}$の$3$つがあり，それぞれ全要素の積は$1,2,1$です．
$S=\{2,1\}$のとき，$G$として考えられるものは，$\{2\},\{1\},\{\}$の$3$つがあり，それぞれ全要素の積は$2,1,1$です．
$S=\{2,2\}$のとき，$G$として考えられるものは，$\{2\},\{2\},\{\}$の$3$つがあり，それぞれ全要素の積は$2,2,1$です．
従って，答えは$3+4+4+5=16$です．
サンプル2
入力
4 3
出力
5265
サンプル3
入力
3435 2835
出力
618988899
$10^9+7$で割った余りを出力してください．
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。