[python] o(N log N) solution by using DP,  group by remainer
(This solution has been corrected, thanks to friends in the comment area)\n\n# Intuition\n\nThis problem can be solved using DP. \nConsider a subproblem.\nGiven
(This solution has been corrected, thanks to friends in the comment area)\n\n# Intuition\n\nThis problem can be solved using DP. \nConsider a subproblem.\nGiven an increasing array,  like arr = [1,2,3,5,6]\nwhat is the number of subsequence that every two number in this subsequence difference is not 1 ? \n\nWe can use DP, and have the following formula, dp[i] means number of subsequence that end with ith number. \nWe have\n\ndp[-1] = 1\ndp[0] = 2\nif arr[i] == arr[i-1] + 1:  dp[i] = dp[i-1] + dp[i-2]\nelse:  dp[i] = 2*dp[i-1]\n\nBy solving this sub problem,  we can move on to this problem\n\nUPD:  Thanks for reminder, if there are duplicates,  since the duplicate only affect the final result,  we can use another dic to store the frequency,  and times the pow(2,fre[num]) - 1\n\n\n# Approach\n\n1, sort the array (UPD:  and count the frequency)\n2, group the array by the module of value,  you can assume that two number with different module can always exist together\n3, For each group,  this can be converted into the sub problem I mentioned about.  Since each group is independent,  the final answer is just the product of all group answers. \n4, minus the final answer by 1 to exclude the all-empty subsequece. \n\n\n# Complexity\n- Time complexity:  O(n lg n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution(object):\n    def beautifulSubsets(self, nums, k):\n        """\n        :type nums: List[int]\n        :type k: int\n        :rtype: int\n        """\n        M = 10**9 + 7\n        \n        n = len(nums)\n        nums.sort()\n        \n        dic = {}\n        fre = {}\n\n\n\n        for num in nums:\n            if num not in fre:  fre[num] = 0\n            fre[num] += 1\n\n            if num % k not in dic:  dic[num%k] = []\n            if fre[num] == 1:   dic[num%k].append(num//k)\n\n\n\n        \n        ans = 1\n        \n        for key in dic:\n            temp = dic[key]\n            dp = [0]*len(temp) + [1]\n            dp[0] = pow(2,fre[key+temp[0]*k],M)\n\n                  \n            for i in range(1,len(temp)):\n\n\n                dp[i] += dp[i-1]\n                if temp[i]==temp[i-1] + 1:\n                    dp[i] +=  dp[i-2] * (pow(2,fre[key+temp[i]*k],M) - 1)\n                else:\n                    dp[i] += dp[i-1] * (pow(2,fre[key+temp[i]*k],M) - 1)\n                    \n                dp[i] %= M\n                    \n            ans *= dp[len(temp)-1]\n            ans %= M\n\n\n            \n        return (ans - 1)%M\n            \n                \n            \n            \n            \n```
['Python']