Problem description

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 3² + 4² = 5². 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 (A≤a≤b≤B) ∧ (A≤c≤B) oraz a² + b² ≡ c² (mod  M) (czyli liczba a² + b² ma dawać taką samą resztę z dzielenia przez M co liczba c²). 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

3 6 12

5