5318 - 数论：费马小定理：求和

求 （1^n+2^n.....11^n） % p ,其中 n= 2019^{2019}

Input

输入1个正素数p，p不超过200范围

Output

输出1个整数

Examples

Input

101

Output

39
Time Limit 1 second
Memory Limit 128 MB
Discuss Stats
上一题 下一题