Problem description


Trójki pitagorejskie inaczej
(pitagorejskie-inaczej)
Memory limit: 64 MB
Time limit: 4.00 s

Wszyscy dobrze znamy słynne twierdzenie Pitagorasa. Przypomnijmy jednak formułkę znaną z lekcji matematyki: W trójkącie prostokątnym suma kwadratów długości przyprostokątnych jest równa kwadratowi długości przeciwprostokątnej. Bla, bla, bla. A teraz naucz się na pamięć!

A tak na poważnie: w tym zadaniu rozważać będziemy tak zwane trójki pitagorejskie – tzn. całkowitoliczbowe długości przyprostokątnych i przeciwprostokątnych spełniających twierdzenie Pitagorasa. Na przykład: trójka (3,4,5) jest trójką pitagorejską, bo 32 + 42 = 52. Inna, również popularna trójka pitagorejska to: (5,12,13).

Zadanie polega na wyznaczeniu liczby trójek Pitagorejskich (a,b,c), w których A ≤ a ≤ b ≤ c ≤ B. Naprawdę takie proste? Niestety nie, ponieważ całość będzie liczona modulo M. Dokładniej więc, należy wyznaczyć liczbę takich (a,b,c), że (AabB) ∧ (AcB) oraz a2 + b2 ≡ c2 (mod  M) (czyli liczba a2 + b2 ma dawać taką samą resztę z dzielenia przez M co liczba c2). Powodzenia.

Napisz program, który: wczyta liczby A, B oraz M, opisujące parametry problemu, wyznaczy liczbę trójek pitagorejskich według treści powyżej i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym (jedynym) wierszu wejścia znajdują się trzy liczby naturalne A, B oraz M, pooddzielane pojedynczymi odstępami i określające kolejno: początek i koniec przedziału, w którym mają być zawarte elementy szukanych trójek oraz dzielnik M, przez który będzie wykonywane dzielenie przy obliczaniu reszty z dzielenia.

Wyjście

W pierwszym i jedynym wierszu wyjścia należy wypisać jedną liczbę całkowitą – liczbę różnych trójek pitagorejskich dla parametrów z wejścia.

Ograniczenia

0 ≤ A ≤ B < M ≤ 100 000.

Przykład

Input Output Explanation
3 6 12
5

Trójki pitagorejskie, o których mowa w tym przypadku to: (3,4,5), (3,6,3), (4,6,4), (5,6,5), (6,6,6).