POLSKI SPOJ

Być może przed rozwiązaniem tego zadania chciał(a)byś przeczytać jego prostrzą wersję.

Kwadracik jest to kwadrat o boku o długości k, podzielony na k² równych komórek, tak jak to przedstawiono na rysunku poniżej dla k=3.

W każdej komórce Kwadracika znajduje się liczba z przedziału [a,b].

Twoim zadaniem jest napisać program zliczający liczbę wszystkich takich różnych Kwadracików, dla których suma liczb w każdym kwadracie składającym się z 4 komórek i znajdującym się w Kwadraciku jest równa n.

Wejście

W pierwszej linii liczba testów t (1 ≤ t ≤ 10000).

W każdej z następnych t linii znajdują się cztery liczby całkowite: k a b n.

Testy podzielone będą na różne stopnie trudności. Każdy test warty jest taką samą ilość punktów. Ograniczenia na poszczególne testy:

• t = 20, 2 ≤ k ≤ 3, 0 ≤ a ≤ b ≤ 10, 0 ≤ n ≤ 40
• t = 50, 2 ≤ k ≤ 3, 0 ≤ a ≤ b ≤ 100, 0 ≤ n ≤ 400
• t = 20, 4 ≤ k ≤ 5, 0 ≤ a ≤ b ≤ 5, 0 ≤ n ≤ 20
• t = 100, 2 ≤ k ≤ 3, 0 ≤ a ≤ b ≤ 500, 0 ≤ n ≤ 2000
• t = 500, 2 ≤ k ≤ 3, 0 ≤ a ≤ b ≤ 5*10⁴, 0 ≤ n ≤ 2*10⁵
• t = 10000, 2 ≤ k ≤ 5, 0 ≤ a ≤ b ≤ 5*10⁸, 0 ≤ n ≤ 2*10⁹

Każde ograniczenie dotyczy 2 testów. Jest ich zatem 12.

Wyjście

Dla każdego testu należy wypisać liczbę oznaczającą ilość Kwadracików spełniających dany warunek modulo 10⁹+7.

Przykład

Wejście:

5
3 0 9 1
2 1 2 4
3 1 2 5
4 1 3 6
5 1 3 8

Wyjście:
8
1
8
74
1383

Wyjaśnienie:

Oto Kwadraciki spełniające warunek dla pierwszych trzech testów:

1 0 1 | 1 0 1 | 1 0 0 | 0 1 0 | 0 1 0 | 0 0 1 | 0 0 0 | 0 0 0
0 0 0 | 0 0 0 | 0 0 1 | 0 0 0 | 0 0 0 | 1 0 0 | 1 0 1 | 0 1 0
1 0 1 | 0 1 0 | 1 0 0 | 1 0 1 | 0 1 0 | 0 0 1 | 0 0 0 | 0 0 0

1 1
1 1 

2 1 2 | 2 1 2 | 2 1 1 | 1 2 1 | 1 2 1 | 1 1 2 | 1 1 1 | 1 1 1
1 1 1 | 1 1 1 | 1 1 2 | 1 1 1 | 1 1 1 | 2 1 1 | 2 1 2 | 1 2 1
2 1 2 | 1 2 1 | 2 1 1 | 2 1 2 | 1 2 1 | 1 1 2 | 1 1 1 | 1 1 1

Podziękowania

• Bartek - autor oryginalnego zadania
• Mitch Schwartz - inicjator utworzenia rozszerzonej wersji zadania
• Min_25 - twórca zadań z głównego SPOJa będących częściami, które złożyły się w to zadanie oraz twórca testów