문제
크기 $N$인 집합 $A = \{A_1, A_2, \cdots, A_N\}$와 정수 $K$가 주어집니다. $A$의 부분집합 $S$가 좋은 집합이라는 것은 다음 조건을 모두 만족시킴을 의미합니다.
- $S$에는 두 개 이상의 수가 포함되어 있습니다.
- $S$의 서로 다른 두 원소 $a, b \in S$에 대해서, $a + b$는 $K$의 배수가 아닙니다.
좋은 집합의 개수를 출력하세요.
출력
첫 줄에 좋은 집합의 개수를 출력하세요. 단, 수가 매우 커질 수 있으니 1ドル,000円,000円,007円 (= 10^9+7)$로 나눈 나머지를 출력하세요. 1ドル,000円,000円,007円$은 소수입니다.
좋은 집합의 목록은 다음과 같습니다.
- $\{1, 2\}$
- $\{1, 2, 3\}$
- $\{1, 3\}$
- $\{1, 3, 4\}$
- $\{1, 4\}$
- $\{2, 3\}$
- $\{2, 3, 5\}$
- $\{2, 5\}$
- $\{3, 4\}$
- $\{3, 4, 5\}$
- $\{3, 5\}$
- $\{4, 5\}$
W3sicHJvYmxlbV9pZCI6IjI4NDM1IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViYzMwXHVjMjE4IFx1ZDUzY1x1ZDU1OFx1YWUzMCIsImRlc2NyaXB0aW9uIjoiPHA+XHVkMDZjXHVhZTMwICROJFx1Yzc3OCBcdWM5ZDFcdWQ1NjkgJEEgPSBcXHtBXzEsIEFfMiwgXFxjZG90cywgQV9OXFx9JFx1YzY0MCBcdWM4MTVcdWMyMTggJEskXHVhYzAwIFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC4gJEEkXHVjNzU4IFx1YmQ4MFx1YmQ4NFx1YzlkMVx1ZDU2OSAkUyRcdWFjMDAgPHN0cm9uZz5cdWM4OGJcdWM3NDAgXHVjOWQxXHVkNTY5PFwvc3Ryb25nPlx1Yzc3NFx1Yjc3Y1x1YjI5NCBcdWFjODNcdWM3NDAgXHViMmU0XHVjNzRjIFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWJhYThcdWI0NTAgXHViOWNjXHVjODcxXHVjMmRjXHVkMGI0XHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU2OVx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4kUyRcdWM1ZDBcdWIyOTQgXHViNDUwIFx1YWMxYyBcdWM3NzRcdWMwYzFcdWM3NTggXHVjMjE4XHVhYzAwIFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YzViNCBcdWM3ODhcdWMyYjVcdWIyYzhcdWIyZTQuPFwvbGk+XHJcblx0PGxpPiRTJFx1Yzc1OCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YjQ1MCBcdWM2ZDBcdWMxOGMgJGEsIGIgXFxpbiBTJFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsICRhICsgYiRcdWIyOTQgJEskXHVjNzU4IFx1YmMzMFx1YzIxOFx1YWMwMCBcdWM1NDRcdWIyZDlcdWIyYzhcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVjODhiXHVjNzQwIFx1YzlkMVx1ZDU2OVx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHVjMTM4XHVjNjk0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWM4MTVcdWMyMThcdWM3NTggXHVhYzFjXHVjMjE4ICROJFx1YWNmYyBcdWJiMzhcdWM4MWNcdWM3NTggXHVjODE1XHVjMjE4ICRLJFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC4gJCgyIFxcbGUgTiwgSyBcXGxlIDEwMFxcLDAwMCkkPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDAgJE4kXHVhYzFjXHVjNzU4IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjODE1XHVjMjE4ICRBXzEsIEFfMiwgXFxjZG90cywgQV9OJFx1Yzc3NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC4gJCgxIFxcbGUgQV9pIFxcbGUgMTBeOSkkPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWM4OGJcdWM3NDAgXHVjOWQxXHVkNTY5XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWMxMzhcdWM2OTQuIFx1YjJlOCwgXHVjMjE4XHVhYzAwIFx1YjllNFx1YzZiMCBcdWNlZTRcdWM5YzggXHVjMjE4IFx1Yzc4OFx1YzczY1x1YjJjOCAkMVxcLDAwMFxcLDAwMFxcLDAwNyAoPSAxMF45KzcpJFx1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YzEzOFx1YzY5NC4gJDFcXCwwMDBcXCwwMDBcXCwwMDckXHVjNzQwIFx1YzE4Y1x1YzIxOFx1Yzc4NVx1YjJjOFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4iLCJzYW1wbGVfZXhwbGFpbl8xIjoiPHA+XHVjODhiXHVjNzQwIFx1YzlkMVx1ZDU2OVx1Yzc1OCBcdWJhYTlcdWI4NWRcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YzJiNVx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4kXFx7MSwgMlxcfSQ8XC9saT5cclxuXHQ8bGk+JFxcezEsIDIsIDNcXH0kPFwvbGk+XHJcblx0PGxpPiRcXHsxLCAzXFx9JDxcL2xpPlxyXG5cdDxsaT4kXFx7MSwgMywgNFxcfSQ8XC9saT5cclxuXHQ8bGk+JFxcezEsIDRcXH0kPFwvbGk+XHJcblx0PGxpPiRcXHsyLCAzXFx9JDxcL2xpPlxyXG5cdDxsaT4kXFx7MiwgMywgNVxcfSQ8XC9saT5cclxuXHQ8bGk+JFxcezIsIDVcXH0kPFwvbGk+XHJcblx0PGxpPiRcXHszLCA0XFx9JDxcL2xpPlxyXG5cdDxsaT4kXFx7MywgNCwgNVxcfSQ8XC9saT5cclxuXHQ8bGk+JFxcezMsIDVcXH0kPFwvbGk+XHJcblx0PGxpPiRcXHs0LCA1XFx9JDxcL2xpPlxyXG48XC91bD5cclxuIn0seyJwcm9ibGVtX2lkIjoiMjg0MzUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJBdm9pZGluZyBNdWx0aXBsZXMiLCJkZXNjcmlwdGlvbiI6IjxwPkEgc2V0ICRBID0gXFx7QV8xLCBBXzIsIFxcY2RvdHMsIEFfTlxcfSQmbmJzcDtvZiBzaXplICROJCBhbmQgYW4gaW50ZWdlciAkSyQgYXJlIGdpdmVuLiBBIHN1YnNldCAkUyQgb2YgJEEkIGlzIGNhbGxlZCBhIDxzdHJvbmc+Z29vZCBzZXQ8XC9zdHJvbmc+IGlmIGl0IHNhdGlzZmllcyBhbGwgb2YgdGhlIGZvbGxvd2luZyBjb25kaXRpb25zLjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPiRTJCBjb250YWlucyBhdCBsZWFzdCB0d28gZWxlbWVudHMuPFwvbGk+XHJcblx0PGxpPkZvciBhbnkgdHdvIGRpZmZlcmVudCBlbGVtZW50cyAkYSwgYiBcXGluIFMkLCAkYSArIGIkIGlzIG5vdCBhIG11bHRpcGxlIG9mICRLJC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5QcmludCB0aGUgbnVtYmVyIG9mIGdvb2Qgc2V0cy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHRoZSBudW1iZXIgb2YgaW50ZWdlcnMgJE4kIGFuZCB0aGUgaW50ZWdlciAkSyQgZGVzY3JpYmVkIGluIHRoZSBzdGF0ZW1lbnQsIHNlcGFyYXRlZCBieSBhIHNwYWNlLiAkKDIgXFxsZSBOLCBLIFxcbGUgMTAwXFwsMDAwKSQ8XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zICROJCBkaWZmZXJlbnQgaW50ZWdlcnMgJEFfMSwgQV8yLCBcXGNkb3RzLCBBX04kLCBzZXBhcmF0ZWQgYnkgYSBzcGFjZS4gJCgxIFxcbGUgQV9pIFxcbGUgMTBeOSkkPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+UHJpbnQgdGhlIG51bWJlciBvZiBnb29kIHNldHMgaW4gdGhlIGZpcnN0IGxpbmUuIFNpbmNlIHRoZSBudW1iZXIgY2FuIGJlIGh1Z2UsIHByaW50IHRoZSByZW1haW5kZXIgd2hlbiBkaXZpZGVkIGJ5ICQxXFwsMDAwXFwsMDAwXFwsMDA3ICg9IDEwXjkrNykkLiAkMVxcLDAwMFxcLDAwMFxcLDAwNyQgaXMgYSBwcmltZSBudW1iZXIuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCIsInNhbXBsZV9leHBsYWluXzEiOiI8dWw+XHJcblx0PGxpPlRoZSBsaXN0IG9mIGdvb2Qgc2V0cyBpcyBhcyBmb2xsb3dzOlxyXG5cdDx1bD5cclxuXHRcdDxsaT4kXFx7MSwgMlxcfSQ8XC9saT5cclxuXHRcdDxsaT4kXFx7MSwgMiwgM1xcfSQ8XC9saT5cclxuXHRcdDxsaT4kXFx7MSwgM1xcfSQ8XC9saT5cclxuXHRcdDxsaT4kXFx7MSwgMywgNFxcfSQ8XC9saT5cclxuXHRcdDxsaT4kXFx7MSwgNFxcfSQ8XC9saT5cclxuXHRcdDxsaT4kXFx7MiwgM1xcfSQ8XC9saT5cclxuXHRcdDxsaT4kXFx7MiwgMywgNVxcfSQ8XC9saT5cclxuXHRcdDxsaT4kXFx7MiwgNVxcfSQ8XC9saT5cclxuXHRcdDxsaT4kXFx7MywgNFxcfSQ8XC9saT5cclxuXHRcdDxsaT4kXFx7MywgNCwgNVxcfSQ8XC9saT5cclxuXHRcdDxsaT4kXFx7MywgNVxcfSQ8XC9saT5cclxuXHRcdDxsaT4kXFx7NCwgNVxcfSQ8XC9saT5cclxuXHQ8XC91bD5cclxuXHQ8XC9saT5cclxuPFwvdWw+XHJcbiJ9XQ==