Отдыхая на пляже, Duff случайно нашла странный массив b₀, b₁, ..., b_l - 1, состоящий из l положительных целых чисел. Этот массив был странный, потому что он был необычайно длинным, но зато известно, что существует ещё один массив (возможно, короче), a₀, ..., a_n - 1, такой что b построен из a по фомуле: b_i = a_{i mod n}, где a mod b обозначает остаток деления a на b.

Duff очень хочется узнать число подпоследовательностей b, обладающих следующими свойствами. Пусть b_i1, b_i2, ..., b_ix (0 ≤ i₁ < i₂ < ... < i_x < l) — подпоследовательность. Должны быть выполнены следующие свойства:

• 1 ≤ x ≤ k
• Для каждого 1 ≤ j ≤ x - 1,
• Для каждого 1 ≤ j ≤ x - 1, b_ij ≤ b_ij + 1, то есть эта последовательность неубывающая.

Так как это число может быть достаточно большим, девушке хочется узнать его остаток от деления на 10⁹ + 7.

Duff не программист, а Malek сейчас недоступен. Итак, она попросила Вашей помощи. Пожалуйста, назовите ей это число.