Partuki and Haverta are playing a game. Partuki places several groups of coins in front of Haverta, and asks her to select one or more of the groups. The groups must be selected so that counts of coins in them do not share any common divisors greater than 1. For example, you could choose a group of 4 coins, a group of 3 coins, and a group of 2 coins because 4, 3 and 2 share no common divisors greater than 1. However, you could not chose a group of 4 coins and a group of 2 coins because 4 and 2 share the common divisor 2.
You are given a int[] groups, each element of which is the number of coins in a single group. Determine the number of different ways in which Haverta can make a valid selection, and return this number modulo 10000003.
