Informatica Online Judge

  I am Coder [0725 / 02D5]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 25   Total Tried : 32


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[]

Background

GSHS의 최강, 경곽 유일무이의 정보올림피아드 동아리이자 스펙터클 간지 철철 멋있고 잘생긴 사람들만 가입할 수 있다는 슈퍼 초 울트라 액션 서스펜스 동아리인 나는 코더다에 들어올려면 다음 문제를 풀어야 한다.

“두 p진법의 수 n, r이 주어졌을 때 nCr을 p로 나눈 나머지를 구하여라!!!!” (단, p는 소수)

경곽 최강간지동아리 나는 코더다에 들어가고 싶은 태호를 도와 문제를 풀자!

Input

첫 번째 줄에 한 소수 p(1 <= p <= 1000 )와 두 정수 L1, L2( 1 <= L1, L2 <= 150000)가 입력된다. 
두 번째 줄에는 L1개의 정수 a_1, a_2, ... a_L1이 입력된다. (0 <= a_k <= p-1)
세 번째 줄에는 L2개의 정수 b_1, b_2, ... b_L2이 입력된다. (0 <= b_k <= p-1)

Output

주어진 두 p진법의 수를 각각 n, r이라고 했을 때, nCr을 p로 나눈 나머지를 구하여라.

IO Example

입력 1
2 4 3
1 1 0 1
1 0 1

출력 1
1 ( 1101(2) -> 13, 101(2) -> 5, 13C5 = 1287 = 1(mod 2) )

입력 2
5 6 4
1 0 1 2 4 3
1 0 3 2

출력 2
2 ( 101243(5) -> 3323, 1032(5) -> 142, 3323C142 = 19922....36092 = 2 (mod 5) )

* 출제 : 29th 권태호

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]