题目描述

当数字的位数高达上百位时，这样庞大的数字在计算机中的计算已经完全不能用简单的加减乘除来实现了，但是有时候对于这种高精度数字的处理也是编程中必不可缺的。

任意输入一个数字 $n (99999 < n < 999999)$，计算 $n ^ n$（即连续n个n相乘）计算之后，最后的3位数字是多少。

题目格式

输入

一个数字 $n (99999 < n < 999999)$。

输出

计算 $n ^ n$，输出最后的3位数字是多少？

题目样例

123456

856

题目提示

1、C++的同学需要自己手写高精度。 2、Python的同学可以直接算。