Mystical Number Challenge

In the charming town of Lánqiáo the annual Children's Day is a magical event. Every year on this day, a mysterious number spirit makes an appearance and offers a delightful challenge to the children. This year, the challenge is as follows:

Find two distinct integers \(x\) and \(y\) with \(1 \le x < y \le n\) (and in our problem \(n = 20240601\) though the input can be any integer satisfying \(1 \le n \le 20240601\)) such that:

[ x^x + y^y \equiv 0 \pmod{6421} ]

The computation \(x^x\) means raising \(x\) to the power of \(x\) and then taking the result modulo \(6421\). The children who successfully count the number of valid pairs \((x,y)\) will receive the grand gift prepared by the number spirit!

Your task is to help the children by calculating the total number of valid pairs \((x,y)\) that satisfy the above congruence.

inputFormat

The input consists of a single integer \(n\) (where \(1 \le n \le 20240601\)). You are to consider all integers from \(1\) to \(n\). In the official challenge, \(n\) is set to 20240601.

outputFormat

Output a single integer: the number of pairs \((x,y)\) with \(1 \le x < y \le n\) such that \(x^x + y^y\) is divisible by \(6421\).

sample

1

0