그다지 무작위가 아님

하나의 음이 아닌 정수를 입력으로 받아 또 다른 음이 아닌 정수를 출력으로 생성하는 특정한 "난수 생성기"가 있다(RNG). 하지만 여러분은 이 RNG가 사실 전혀 무작위적이지 않다는 것을 알고 있다! 이 생성기는 고정된 수 K를 사용하며, 항상 다음 세 연산 중 하나를 수행한다.

• 확률 A/100로: 입력과 K의 비트 단위 AND를 반환한다

• 확률 B/100로: 입력과 K의 비트 단위 OR를 반환한다

• 확률 C/100로: 입력과 K의 비트 단위 XOR를 반환한다

(RNG는 A, B, C의 값에 따라 매번 연산을 선택하는 방식에서는 실제로 무작위적이라고 가정해도 된다.)

여러분에게는 이 RNG의 복사본이 N개 있으며, 한 기계의 출력이 직렬로 연결된 다음 기계의 입력이 되도록 배치했다. 첫 번째 기계에 X를 입력으로 제공하면, 직렬로 연결된 마지막 기계의 출력의 기댓값은 얼마인가?

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1 GB. 1 ≤ T ≤ 50. 0 ≤ A ≤ 100. 0 ≤ B ≤ 100. 0 ≤ C ≤ 100. A+B+C = 100.

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ N ≤ 10. 0 ≤ X ≤ $10^{4}$. 0 ≤ K ≤ $10^{4}$.

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ N ≤ $10^{5}$. 0 ≤ X ≤ $10^{9}$. 0 ≤ K ≤ $10^{9}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어지며, 각 테스트 케이스는 여섯 정수 N, X, K, A, B, C가 있는 한 줄로 이루어진다. 이들은 각각 기계의 수, 최초 입력, 모든 기계에서 모든 비트 단위 연산의 대상이 되는 고정된 수, 그리고 비트 단위 AND, OR, XOR 연산의 확률에 100을 곱한 값을 나타낸다.

각 테스트 케이스마다 "Case #x: y"을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작), y는 최종 출력의 기댓값이다. y의 절대 오차 또는 상대 오차가 정답의 10^{-9} 이내이면 정답으로 간주한다. 이것이 무엇을 의미하는지와 허용되는 실수 형식에 대한 설명은 FAQ을 참고한다.

예제 테스트 케이스 #1에서, AND 또는 OR가 일어나면 최종 출력은 5이고, XOR가 일어나면 0이다. 따라서 5을 얻을 확률은 (0.1 + 0.5)이고, 0을 얻을 확률은 0.4이다. 그러므로 최종 출력의 기댓값은 5 * 0.6 + 0 * 0.4 = 3이다.

예제 테스트 케이스 #2에서, 최종 출력은 확률 0.72로 5이고, 그 외에는 0이다.