今天a_palpitate学了cry数，觉得cry数也太简单了吧(什么？你不知道什么是cry数？如果一个数是素数，且他的每一位都是素数，则这个数是cry数)，于是！小a同学决定发明一种数，叫小a数，小a数的定义是这样的，如果一个数n是cry数，或者他是一个个位数，则小a数为n^n，如果都不是，则这个数先变成各位数之和，再次进行以上判断，现在小a同学一脸得意的站在你面前，他想问你是否他任意说出一个数，你都能回答相应的小a数是多少呢？(小a数可能过大，对答案取模1e9+7)

Format

Input

一个整数n， $1\leq n\leq 1e6$

Output

一个整数

Samples

2

4

11

4

Limitation

1s, 1024KiB for each test case.