小 X 发现,店里总共有 n 种甜品,而他想挑选其中的 k 种,并按照一定的顺序来品尝。
每种甜品都有一个美味值 a_i,小 X 吃甜品的顺序是有讲究的,他不想使连续两种甜品之间的美味值相差太小,不然他将无法品味出两种甜品之间的差别;但他也不想使连续两种甜品之间的美味值相差太大,否则他将受不了这巨大的味觉冲击。他十分纠结,不知道该如何选择,于是他向你求助。
你要从 n 种甜品中选择 k 种甜品,并且第 i 种甜品( i \in [ 2 , k ] )需要满足如下两个条件:
第 i 种甜品的美味值必须大于等于第 i-1 种甜品的 l 倍。
第 i 种甜品的美味值必须小于等于第 i-1 种甜品的 r 倍。
问现在你有多少种方案?k 种甜品的美味值之和最大为多少?
因为答案太大,所以两个问题你都需要对 1000000007(10^9+7) 取模。