[Login|Register]
Problems

Status

Rank

Problem 1418
Z同学的乌克兰之旅
Time Limit: 1000ms
Memory Limit: 65536kb
Description
Z同学前段时间去了美女如云的乌克兰。
夜幕降临,Z同学在看了一天美女后开始解决自己的住宿问题,他打算玩一个小游戏来选择去住宾馆还是去找当地人借宿。面前有M张当地人的联系方式,前M-1个都是东欧大汉,最后一个是乌克兰妹子!开始所有的联系卡片都朝下,总共操作M轮,第i轮时从第一张开始数,每数i张就将该张翻面(正反颠倒),例如第3轮就将第3、6、9……张翻面。结束时若最后一张面朝上,就去勇敢的找当地妹子借宿,反之去住宾馆。

借宿时城市里有N户人家排成一列,编号从1到N。可以任意选择若干家去敲门询问能否留宿,但是Z同学决定不选择相邻的两家,因为他觉着相邻的两家不可能都是美女,也许是隔壁老王?但是每家门都不敲也不好,毕竟晚上不能睡大街。
所以,请问Z同学是去住宾馆或者是总共有多少种选择方式可以询问借宿。
Input
有多组数据,每组输入M (1 ≤ M ≤ 1000000000), N (1 ≤ N ≤ 100000),二者以空格隔开,含义见题目描述。
M,N均为-1时表示输入结束,你不用处理这个数据。
Output
每组输出一行。若住宾馆,则输出"No girl"(无双引号)。反之输出选择方式的总数,因为结果可能很大,所以请输出对10000007取模后的结果。
Sample Input
1 2
2 4
-1 -1
Sample Output
2
No girl
Hint
本题FB奖: 白书一本.
Source
zqy
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 0.9ms with 1 query(s).