Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

C. Magic Five

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThere is a long plate *s* containing *n* digits. Iahub wants to delete some digits (possibly none, but he is not allowed to delete all the digits) to form his "magic number" on the plate, a number that is divisible by 5. Note that, the resulting number may contain leading zeros.

Now Iahub wants to count the number of ways he can obtain magic number, modulo 1000000007 (10^{9} + 7). Two ways are different, if the set of deleted positions in *s* differs.

Look at the input part of the statement, *s* is given in a special form.

Input

In the first line you're given a string *a* (1 ≤ |*a*| ≤ 10^{5}), containing digits only. In the second line you're given an integer *k* (1 ≤ *k* ≤ 10^{9}). The plate *s* is formed by concatenating *k* copies of *a* together. That is *n* = |*a*|·*k*.

Output

Print a single integer — the required number of ways modulo 1000000007 (10^{9} + 7).

Examples

Input

1256

1

Output

4

Input

13990

2

Output

528

Input

555

2

Output

63

Note

In the first case, there are four possible ways to make a number that is divisible by 5: 5, 15, 25 and 125.

In the second case, remember to concatenate the copies of *a*. The actual plate is 1399013990.

In the third case, except deleting all digits, any choice will do. Therefore there are 2^{6} - 1 = 63 possible ways to delete digits.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/17/2018 21:10:46 (d3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|