존 농부의 소 N마리는 각각 길이가 K인 비트 문자열을 할당받았다. 이 비트 문자열은 모두 0이 아니며, 서로 다른 소들이 동일한 비트 문자열을 할당받을 수 있다.

자카드 유사도 공식 = \frac{|A \cap B|}{|A \cup B|}

두 비트 문자열의 자카드 유사도(Jaccard similarity)는 비트 단위로 교집합에서 1로 설정된 비트의 수를 그들의 비트 단위 합집합에서 1로 설정된 비트의 수로 나눈 값으로 정의된다. 예를 들어, 비트 문자열 11001과 11010의 자카드 유사도는 \frac{2}{4}다.

각 소에 대해, 자신의 비트 문자열과 N마리 소의 비트 문자열 간의 자카드 유사도의 합을 출력하시오.

단, 결과를 10^9+7로 나눈 나머지를 출력한다.
구체적으로, 합이 \frac{a}{b}라는 유리수로 표현된다면(단, a와 b는 서로소), [0,10^9+7) 범위에서 bx-a가 10^9+7로 나누어떨어지는 고유한 정수 x를 출력하시오.

#8188 upload - done - how_to_reg -

자카드 유사도 timer 1s memory 1024MB

#8188

자카드 유사도 1s 1024MB