Tobby has a very special number, when this number is divided by 7 the remainder is 0. Every time that Tobby thinks about this property, he says: WOW, this is a wonderful number! As everybody knows Tobby is not a common pet, he is smart and curious, so he decides to modify the original number as follows: Tobby writes the number in its binary representation, then he chooses two indexes and make a swap operation of the values of those positions, and then he does several other similar operations for a while. Tobby does not remember the total number of operations that he performed, he just remembers the positions in the binary representation that were swapped at some point and he also remembers that the most significant bit was never swapped. Now Tobby wants to recover the original number, but Tobby is a busy pet and so he does not have time for that. Can you help him? Input The input has several test cases. Each test case has three lines, the first line contains a single integer n (7 ≤ n ≤ 260), the modified number. The second line contains an integer k (2 ≤ k ≤ 20) representing the amount of positions that were swapped and the third line contains k different integers in increasing order, the positions (relative to the least significant bit) of the number that were swapped (zero-indexed). Output Print a single integer: the recovered number which is divisible by 7. If there are several answers, then print the maximum possible value. Explication: In the first sample the original number (without swaps) is 91 Tobby remembers that in sometime the positions 0, 1, 2, 4 and 5 were swapped. Suppose that Tobby did the follow swap operations: 6 5 4 3 2 1 0 = indexes 1 0 1 1 0 1 1 = 91 swap(0, 2, 1011 ̄01 ̄1) → 1 0 1 1 1 1 0 = 94 swap(4,5,1 ̄0 ̄11110) → 1 1 0 1 1 1 0 = 110 swap(0,1,11011 ̄1 ̄0) → 1 1 0 1 1 0 1 = 109 swap(2,4,11 ̄01 ̄101) → 1 1 1 1 0 0 1 = 121 swap(0,1,11110 ̄0 ̄1) → 1 1 1 1 0 1 0 = 122 swap(2,4,11 ̄11 ̄010) → 1 1 0 1 1 1 0 = 110 swap(0, 5, 1 ̄10111 ̄0) → 1 0 0 1 1 1 1 = 79 Note that Tobby can swap the same index many times, note also that the position 6 was never swapped. Sample Input 79 5 01245 21 2 03
2/2 65791 16 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1152921504606846975 5 13 39 40 58 59 Sample Output 91 28 130816 1152921504606846975