CF327C Magic Five

There 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.

N/A

N/A

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.