重复数字块

题目描述

把只含数字的字符串 S 原样连续拼接 k 次，得到长十进制串，求其表示的非负整数 mod m。S 可以含前导零，前导零仍占拼接位数。

输入格式

一行输入 S、k、m，满足 1≤|S|≤100000、1≤k≤10^18、1≤m≤10^9。

输出格式

输出拼接结果的标准余数。

样例

输入

12 3 7

输出

0