shunfurh
编程介的小学生
2017-10-29 12:37

Periodic Binary String

  • as
  • string
  • numbers
  • 360
  • each

Problem Description
Teacher Mai has an infinite periodic binary string S with index counting from 0. That means S=TTTT..., where T is the period of string S. For example, T="101", then S="101101101101..."

S[l,r] is the sub-string of S. We define f[l,r] is the value when regarding S[l,r] as a binary number.

Please count the number of binary strings T with length k, where T is the period of string S, satisfying the condition: f[l,r]=x (mod p).

The number can be very large, just output the number modulo 1000000007 (10^9+7).

Input
There are multiple test cases, terminated by a line "0 0 0 0 0".

For each test case, there is a line contains five numbers p (2<p<10^18, p is a prime number) ,x (0<=x<p), l, r (0<=l<=r<=10^18) and k (1<=k<=10^18).

Output
For each test case, output one line "Case #k: ans", where k is the case number counting from 1, ans is the number module 10^9+7.

Sample Input
3 0 1 2 1
233 23 2333 23333 23
233 1 1 2 23
0 0 0 0 0

Sample Output
Case #1: 2
Case #2: 36003
Case #3: 2097152

  • 点赞
  • 回答
  • 收藏
  • 复制链接分享

1条回答

为你推荐