楼上17行，100%的代码，我感觉跟我的思路差不多呀，但是我就超时了，谁能给我分析分析为啥速度差这么多？

# encoding: utf-8

import sys

res_dict = {}
max_key = 0


def search(length, k):
  global max_key
  res_dict[0] = 1
  if max_key >= length:
    return res_dict[length]
  else:
    start = max_key
  start = max(1, start)
  for length_tmp in range(start, length + 1):
    res_dict[length_tmp] = res_dict[length_tmp-1]
    if length_tmp - k >= 0:
      res_dict[length_tmp] += res_dict[length_tmp-k]
    res_dict[length_tmp] %= (1e9+7)
  max_key = length
  return res_dict[length]


line = [int(val) for val in sys.stdin.readline().strip().split(' ')]
t = line[0]
k = line[1]
for group_idx in range(t):
  line = [int(val) for val in sys.stdin.readline().strip().split(' ')]
  a = line[0]
  b = line[1]
  if k == 0:
    print 1
    continue
  count = 0
  for length in range(a, b+1):
    count += search(length, k)
  print int(count % (1e9+7))