Désamorçage d'un explosif (I)

Une bombe dévastatrice a été placée à Los Angeles par un membre des Maîtres du mal. Black Widow a réussi à la trouver et doit maintenant tenter de la désamorcer.

Une fois la bombe ouverte, c'est un véritable sac de nœuds. Il y a 1000 fils numérotés de 0 à 999, et il faut en couper un seul, le bon, pour arrêter le compte à rebours.

Heureusement, les Avengers ont pu fournir un manuel de désamorçage à Black Widow. Celui-ci indique (il est en russe, nous avons traduit pour vous) : Le numéro du fil à couper peut être déduit du numéro de série de la bombe ainsi :

1. commencez par relever le numéro de série (il est indiqué en entrée du problème sur cette page)
2. coupez le numéro de série en 2. Les trois premiers chiffres forment le nombre U et les 3 derniers le nombre N
3. répétez N fois les opérations 4 et 5 suivantes en partant du nombre U
4. multipliez ce nombre par 13
5. ne conservez que les 3 derniers chiffres.

Une fois cet algorithme terminé, le nombre obtenu est le numéro du fil à couper.

Imaginons que le numéro de série soit 317010. On coupe le nombre en deux : U = 317, N = 10. Il faut donc faire 10 fois (N) les opérations :

• multiplier le nombre U (317) par 13, ce qui donne 4121
• conserver les 3 derniers chiffres, ce qui donne 121
• et on recommence avec 121...

On obtient ainsi :

1. 317 -> 4121 -> 121
2. 121 -> 1573 -> 573
3. 573 -> 7449 -> 449
4. 449 -> 5837 -> 837
5. 837 -> 10881 -> 881
6. 881 -> 11453 -> 453
7. 453 -> 5889 -> 889
8. 889 -> 11557 -> 557
9. 557 -> 7241 -> 241
10. 241 -> 3133 -> 133

Par conséquent, si le numéro de série avait été 317010, il aurait fallu couper le fil 133.

Indiquez à Black Widow le numéro du fil à couper pour valider le défi. Le numéro de série est donné en entrée du problème.