The Book Game
Problem
You are given an array A of K integers where Ai denotes page number of a book. To compute the score, you can either add or multiply the last digit of the page numbers.
You have to find the maximum score you can get. Since the score can be quite large, output the score modulo 1000000007
Note: The book contains N pages. Also, you need to follow the order in which the page numbers are given in the array. Initially, your score is 0.
Input format :
- First line: Two space seperated integers N and K.
- Next line: K space seperated integers denoting the page numbers.
Output format :
- Output the maximum score you can get. Print it modulo 1000000007
Input Constraints
- 1≤N≤109
- 1≤K≤106
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation
Last digit of all page numbers are: 2, 5, and 3.
Initial score = 0
We add 2 to the score which now becomes 2, multiply with 5 making the score 10, finally we multiply with 3 making the score 30 which is the maximum score.
Output 30 % (10^9+7) = 30.
