Codeforces ラウンド #271 (ディビジョン 2) D. Flowers (再帰的前処理)_html/css_WEB-ITnose

私たちはマーモットがモグラの昼食のために作った小さなゲームを見ました。さて、マーモットの夕食の時間です。皆さんご存知のように、マーモットは花を食べます。彼は夕食のたびに赤と白の花をいくつか食べます。したがって、ディナーは、いくつかの花のシーケンスとして表現できます。いくつかは白で、いくつかは赤です。

しかし、ディナーを美味しくするには、ルールがあります。マーモットは、白い花をサイズクのグループでのみ食べたいと考えています。 .

今、マーモットは、a の花と b の花の間を何通りの方法で食べることができるか考えています。方法の数は非常に多くなる可能性があるため、modulo1000000007 (109?+?7) と出力します。

入力

入力にはいくつかのテスト ケースが含まれます。

最初の行には 2 つの整数 t と k (1?≤?t) が含まれます。 ,?k?≤?105)、ここで、t はテスト ケースの数を表します。

次の t 行には、i 番目のテストを記述する 2 つの整数 ai およびbi (1?≤?ai?≤?bi?≤?105) が含まれています。 .

出力

t 行を標準出力に出力します。 The-th Lineには、夕食Modulo100000000007（109？+？7）で、MarmotがAIとBiの花の間で食べることができる方法の数を含める必要があります。

3 21 32 34 4

注意

K = 2 および length1 の場合、マーモットは (R) を食べることができます。

K = 2 および length2 の場合、マーモットは (RR) および (WW) を食べることができます。

K = 2 および length3 の場合、マーモット(RRR)、(RWW)、および (WWR) を食べることができます。

K = 2 および長さ 4 の場合、マーモットは、たとえば (WWWW) または (RWWR) を食べることができますが、たとえば (WWWR) を食べることはできません。たとえば、n が k より小さい場合、すべてが R である可能性がある、つまり 1 つの場合のみです。 1からnまではすべてWであり、n番目がRの場合、その数は前のn-1の数になります。 (0 dp[n] = dp[n-1] + dp[n-k]; (n >= k)

れー

??