https://atcoder.jp/contests/abc156/submissions/10570710
r=0を含むので注意
文章を数式にするととなる。なんとなく前半が式変形できそうという気持ちになる。調べてみると二項係数の和は
に等しいという情報が得られる。
https://mathtrain.jp/nikoubekijo
ただし、nがもあるので工夫せず累乗の計算をすると間に合わない。累乗の高速化として繰り返し二乗法というテクニックがあり、
で答えが求まる。
https://math.nakaken88.com/textbook/cp-binary-exponentiation-and-recursive-function/
組み合わせの計算はnがもあるのでメモ化を使った高速化を適用できないが、素直に
を計算しても最大で
で計算出来るため問題ない。
したがって、が答えになる（花0本=1通りの組み合わせを除外するのを忘れずに）
計算量は
