8756번 - Dziwna planeta 다국어

Pewnego razu gdzieś tam sobie istniała n-wymiarowa przestrzeń. Znajdowała się tam również pewna dziwna planeta. Jedną z jej przedziwnych cech był jej kształt - n-wymiarowy hipersześcian o jednostkowej długości boku. W każdym wierzchołku planety znajdowało się pewne dziwne miasto.

Terytorium tej planety zostało podzielone między trzy wrogie królestwa. Jednak kilka miast ogłosiło swoją niezależność - nazwijmy je neutralnymi: i-te miasto jest niezależne, jeśli d₁(i) = d₂(i) = d₃(i), gdzie d_j(i) oznacza odległość między i-tym miastem oraz stolicą j-tego królestwa. Wszystkie odległości liczone są przy pomocy metryki miejskiej.

Twoim zadaniem jest obliczenie liczby neutralnych miast. Ze względu na to że wynik może być duży, wystarczy wypisać go modulo 10⁹ + 7.

Wejście zawiera trzy linie. W każdej linii znajdują się współrzędne stolicy kolejnego królestwa w postaci liczby binarnej długosci n (1 ≤ n ≤ 10⁵).

W pierwszym i jedynym wierszu wyjścia powinna się znaleźć jedna liczba całkowita równa liczbie neutralnych miast modulo 10⁹ + 7.