Description

Format

Input

Output

共一行，一个整数，表示所求的纸带分数除以10007所得的余数。

Samples

6 2
5 5 3 2 2 2 
2 2 1 1 2 1

82

15 4
5 10 8 2 2 2 9 9 7 7 5 6 4 2 4
2 2 3 3 4 3 3 2 4 4 4 4 1 1 1

1388

Hint