Description

数学课上，Jimmy学习了一个新的知识。两数相除，如果得不到整数商，会有两种情况：一种是得到有限小数，另一种是得到无限小数。从小数点后某一位开始依次不断地重复出现前一个或一节数字的十进制无限小数，叫做循环小数，如2.9666..., (在数学中它读作“二点九六，六循环”），定义循环小数的缩写法是将第一个循环节以后的数字全部略去，并将第一个循环节首末用括号括起来。例如：

2.966666... 缩写为 2.9(6)

35.232323…缩写为 35.(23)

Jimmy发现，根据循环小数的特征，很快能算出这个循环小数中小数点后第n位的数字，你也可以吗？

Format

Input

第一行，输入一个整数n(n<=100000)，表示求小数点后的第n位。

第二行，一个字符串，用缩写法表示的一个循环小数。

Output

输出一个整数，求出循环小数中小数点后第n位的数字。

Samples

10
352.19(7)

7

5
7328.(192)

9

Limitation

1s, 1024KiB for each test case.