Viết code C++ hay Python hay Pascal

```python
from itertools import combinations

def count_valid_subsets(n, k, S):
# Generate all possible non-empty combinations of the set S
valid_count = 0
for r in range(1, n + 1):
for subset in combinations(S, r):
# Check if the sum of the subset is not divisible by k
if sum(subset) % k != 0:
valid_count += 1
return valid_count

def main():
# Input the size of the set and k value
n = int(input())
k = int(input())

# Input the elements of the set S
S = list(map(int, input().split()))

# Count valid subsets
result = count_valid_subsets(n, k, S)

# Output the result
print(result)

# Run the main function
main()
```

Giải thích chi tiết:

1. Hàm `count_valid_subsets`: Hàm này sẽ đếm số lượng tập con không rỗng của tập `S` mà tổng của các phần tử trong tập con đó không chia hết cho `k`. Để làm điều này, chúng ta sử dụng các tổ hợp từ thư viện `itertools`.

2. Vòng lặp `for r in range(1, n + 1)`: Ở đây, chúng ta sẽ duyệt qua tất cả các kích thước của tập con có thể từ 1 đến `n` (kích thước của tập `S`).

3. Hàm `combinations(S, r)`: Hàm này sẽ tạo ra tất cả các tổ hợp của tập hợp `S` với kích thước `r`.

4. `if sum(subset) % k != 0`: Kiểm tra xem tổng của tập con có chia hết cho `k` hay không. Nếu không chia hết, chúng ta tăng biến đếm `valid_count`.

5. Trong hàm `main`, chúng ta nhận vào kích thước n của tập, giá trị k và các phần tử của tập S từ người dùng. Sau đó, chúng tôi gọi hàm `count_valid_subsets` để tính số lượng tập con hợp lệ và in ra kết quả.

Kết quả trả về sẽ là số lượng các tập con của `S` mà tổng của chúng không chia hết cho `k`.