En un plano cartesiano acotado se pueden elegir dos tipos de ternas:

• ~1:~ ~(0;a)~,~(0;b)~,~(c;0)~
• ~2:~ ~(0;d)~,~(e;0)~,~(f;0)~

Donde ~a~, ~b~, ~c~, ~d~, ~e~ y ~f~ son números enteros ~(0 \leq a,b,c,d,e,f \leq N)~. Imprima la suma de las áreas módulo ~1234567891~ de todos los triángulos isósceles que se pueden formar usando dichas ternas que se encuentran en dicho plano.

Entrada

La única línea de la entrada contiene un entero ~N (0 \leq N \leq 10^6)~.

Salida

La salida consta de una línea con la respuesta al problema dado.

Ejemplo de Entrada

3

Ejemplo de Salida

7