다항식의 나머지 연산

계수가 0 또는 1로만 이루어진 특수한 다항식들의 집합을 생각하자. 이 집합에서 정의되는 덧셈, 뺄셈, 곱셈은 모두 결과 계수를 2로 나눈 나머지를 취한다.

덧셈. 두 다항식을 일반적인 방법으로 더한 뒤, 각 계수를 2로 나눈 나머지를 취한다. $(0+0)\bmod 2=0$, $(0+1)\bmod 2=1$, $(1+0)\bmod 2=1$, $(1+1)\bmod 2=0$ 이므로, 결과 다항식의 각 차수 계수는 두 다항식의 해당 계수에 대한 XOR 연산 결과와 같다.

$(x^6 + x^4 + x^2 + x + 1) + (x^7 + x + 1) = x^7 + x^6 + x^4 + x^2$

뺄셈. 뺄셈도 마찬가지로 $(0-0)\bmod 2=0$, $(0-1)\bmod 2=1$, $(1-0)\bmod 2=1$, $(1-1)\bmod 2=0$ 이므로, 이 집합에서 뺄셈은 덧셈과 완전히 동일하다(계수 간 XOR).

$(x^6 + x^4 + x^2 + x + 1) - (x^7 + x + 1) = x^7 + x^6 + x^4 + x^2$

곱셈. 두 다항식을 일반적인 방법으로 곱한 뒤, 각 계수를 2로 나눈 나머지를 취한다.

$(x^6 + x^4 + x^2 + x + 1)(x^7 + x + 1) = x^{13} + x^{11} + x^9 + x^8 + x^6 + x^5 + x^4 + x^3 + 1$

나머지. 두 다항식 $f(x)$와 $g(x)$의 곱을 $h(x)$로 나눈 나머지는, 위 방법으로 $f(x)g(x)$를 구한 뒤 그 결과를 $h(x)$로 나눈 나머지이다.

$(x^6 + x^4 + x^2 + x + 1)(x^7 + x + 1) \bmod (x^8 + x^4 + x^3 + x + 1) = x^7 + x^6 + 1$

표기법. 어떤 다항식의 최고차항의 차수를 $d$라 하면, 계수가 0 또는 1이므로 그 다항식은 정수 $d+1$과 길이 $d+1$인 비트스트링의 쌍으로 유일하게 나타낼 수 있다. 비트스트링은 최고차항의 계수부터 상수항의 계수까지 차례로 나열한다. 다항식의 차수는 1000보다 작다.

예를 들어 $x^7 + x^6 + 1$은 다음과 같이 표기된다.

8 1 1 0 0 0 0 0 1

여기서 8은 비트의 총 개수이며, 최고차항의 차수 7에 1을 더한 값이다. 이어지는 8개의 비트 1 1 0 0 0 0 0 1은 각각 $x^7, x^6, x^5, x^4, x^3, x^2, x^1, x^0$의 계수이다.

이제 위 성질을 만족하는 세 다항식 $f(x)$, $g(x)$, $h(x)$가 이 형식으로 주어질 때, $f(x)g(x)$를 $h(x)$로 나눈 나머지를 계산하라.

입력은 여러 개의 테스트 케이스로 이루어진다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 각 테스트 케이스마다 세 줄에 걸쳐 위에서 설명한 형식으로 $f(x)$, $g(x)$, $h(x)$가 순서대로 주어진다.

각 테스트 케이스마다, $f(x)g(x)$를 $h(x)$로 나눈 나머지를 위에서 설명한 형식으로 한 줄에 출력한다. 나머지가 영다항식(zero polynomial)인 경우에는 1 0으로 출력한다.