26644번 - Wielokąty 다국어

Jesteśmy już zmęczeni i nie mamy pomysłu na ciekawe zadanie z historyjką. Twoim zadaniem jest po prostu zliczenie wielokątów wypukłych o krótkich całkowitych bokach bez dodatkowych punktów kratowych. Jeśli wierzchołki wielokąta oznaczymy jako (xi , yi), to muszą być spełnione następujące warunki:

• 1 ≤ x_i ≤ X, 1 ≤ y_i ≤ Y
• Wierzchołki są w punktach kratowych (czyli x_i i y_i są całkowite).
• Na żadnym boku nie leży punkt kratowy poza samymi wierzchołkami.
• Długość każdego boku jest liczbą całkowitą nie większą niż K.
• Wielokąt jest wypukły, prosty, niezdegenerowany (czyli kąty są mniejsze niż 180 stopni, nie ma samoprzecięć, są co najmniej trzy wierzchołki). Oznacza to też, że żadne trzy wierzchołki nie będą współliniowe.

Poniżej widać przykłady niepoprawnych wielokątów. Pierwszy i drugi wielokąt mają punkt kratowy na którymś z boków. Drugi i trzeci nie są wypukłe. Dodatkowo, pierwszy i trzeci mają boki, których długości nie są całkowite.

Wypisz liczbę poprawnych wielokątów modulo 2³². Dwa wielokąty są różne, jeśli istnieje punkt, który jest wierzchołkiem tylko jednego z nich.

Pierwszy i jedyny wiersz wejścia zawiera trzy liczby całkowite X, Y i K (1 ≤ X, Y ≤ 10⁹, 1 ≤ K ≤ 250) – odpowiednio ograniczenia na współrzędne oraz na długość boku.

Zestaw testów dzieli się na następujące podzadania, każde warte co najmniej jeden punkt. Możesz założyć, że każda grupa testów należy do co najmniej jednego z niżej wymienionych podzadań. Zauważ, że informacja ta implikuje, że nie istnieje np. test z X = Y = K = 233, ponieważ nie należy to żadnego z podzadań.

• K ≤ 15
• X, Y ≤ 150
• 2000 ≤ X, Y ≤ 2400, K ≤ 100
• X i Y podzielne przez 10⁶

Wypisz jedną liczbę całkowitą – liczbę wielokątów, spełniających warunki zadania, modulo 2³².

Wyjaśnienie do przykładu: Mamy X = 6, Y = 5, K = 5. Jednym z 42 poprawnych wielokątów jest wielokąt (2, 1),(2, 2),(6, 5),(3, 1), widoczny na obrazku.