Ever heard of paragliding? It's a recreational sport in which one jumps off an elevated position, and then soars through the sky equipped with a 'paraglider' (a parachute of sorts). Although air currents might help you out, gravity will relentlessly pull you towards the ground eventually.

As all good sports, paragliding has a group of enthusiasts in Slovakistan, who call themselves 'Klub Slovakistanských Paraglidistov' (KSP). And as all real enthusiast groups, KSP organizes club activities - group tours to the most prestigious paragliding centers, where all members of the club can paraglide to their hearts' content in the most luxurious mountain ranges. Of course, every upcoming tour must be more awesome than the last, and so the selection of the right destination is key. It will be extra important this year, as the Slovakistan paragliding superstar Syseľ agreed to come along. With his dedication and love for the sport, he is recognized on the worldwide paragliding scene.

In his bestseller autobiography the members of KSP have read that Syseľ enjoys long flights the most - such that the difference of the heights of the mountain he jumps from and lands on is greater than m. In the context of an exclusive interview he mentioned that what he most dislikes about paragliding is the need to climb up onto a mountain after every jump; hence, he usually likes to jump from a tall mountain, land on a smaller one, and immediately jump again from this smaller mountain, and so on. If he does this s-1 times, he is satisfied. Lastly from an intercepted phone call KSP members concluded that Syseľ likes to paraglide after lunch, but only in the eastwards direction, as when he paraglides to the west the sun shines into his eyes.

KSP does not want to disappoint Syseľ, and hence they are looking for such a mountain range which has the most possible trips which satisfy Syseľ. Help them!

Task

Every mountain range consisting of n mountains can be described as an array of n numbers, representing the heights of these mountains from west to east.

A trip is an arbitrary sequence of several, not necessarily neighbouring mountains, which satisfies Syseľ if and only if it contains exactly s mountains, and between each two consecutive mountains in this sequence the difference in elevation is greater than m - that is if a mountain's height is x, and the nearest mountain to the east on the trip has a height of y, then x-y>m.

For a given mountain range consisting of n mountains and the values of m and s, find the number of trips which exist in this mountain range that satisfy Syseľ.

Input

There are multiple test cases - their number 1 ≤ T ≤ 70 will be on the first line.

The first line of each test case contains the integers 1 ≤ n ≤ 10⁵, 0 ≤ m ≤ 10¹⁸ and 2 ≤ s ≤ 20: the number of mountains in the mountain range, the required difference in elevation, and the number of mountains in a trip which satisfies Syseľ.

The second line of each test case contains n numbers - the heights of the mountains in the mountain range, from west to east. The heights of mountains are positive integers not greater than 10¹⁸.

The sum of n within one input file does not exceed 400,000.

Output

For each test case output the string "Case x: y", where x is the number of the test case, starting from 1, and y is the number of trips in the mountain range that satisfy Syseľ, modulo 10⁹+7. We consider two trips distinct if there exists at least one mountain which belongs to one trip but not the other.

Example

Input:
3
4 0 2
5 4 3 1
4 1 2
5 4 3 1
8 3 3
11 15 15 10 10 7 1 1
Output:
Case 1: 6
Case 2: 4
Case 3: 14

In the first case, any pair of mountains is a trip which satisfies Syseľ. In the second case, the pairs of mountains with heights (5,4) and (4,3) no longer have a great enough elevation difference.